数据结构中的单链表如何理解(数据结构,编程语言)

数据结构——单链表

一、单链表简介

1、单链表简介

单链表设计要点：
A、类模板，通过头结点访问后继结点。
B、定义内部结点类型，用于描述链表中的结点的数据域和指针域。
C、实现线性表的关键操作

2、单链表中结点的定义

structNode:publicObject{Tvalue;//数据域Node*next;//指针域};

3、单链表的内部结构

头结点不存储实际的数据元素，用于辅助数据元素的定位，方便插入和删除操作。

4、单链表中头结点的定义

mutable Node m_header;

5、单链表类基本结构

template<typenameT>classLinkedList:publicList<T>{protected:structNode:publicObject{Tvalue;//数据域Node*next;//指针域};Nodem_header;intm_length;public:LinkedList();virtual~LinkedList();boolinsert(intindex,constT&value);boolremove(intindex);boolset(intindex,constT&value);boolget(intindex,T&value)const;intlength()const;intfind(constT&value)const;voidclear();};

二、单链表的操作

1、单链表的插入操作

在目标位置处插入数据元素流程如下：
A、从头结点开始，提供current指针定位到目标位置
B、从堆空间申请新的Node结点
C、将新结点插入目标位置，并连接相邻结点的逻辑关系。

boolinsert(intindex,constT&value){//判断目标位置是否合法boolret=(0<=index)&&(index<=m_length);if(ret){//创建新的结点Node*node=newNode();if(node!=NULL){//初始化当前结点为头结点Node*current=&m_header;//遍历到目标位置for(inti=0;i<index;i++){current=current->next;}//修改插入结点的值node->value=value;//将当前位置的下一个结点作为插入结点的下一个结点node->next=current->next;//将要插入结点作为当前结点的下一个结点current->next=node;m_length++;//链表结点长度加1}else{THROW_EXCEPTION(NoEnoughMemoryException,"Noenoughmemmory...");}}else{THROW_EXCEPTION(IndexOutOfBoudsException,"Parameterindexisinvalid...");}returnret;}

2、单链表的删除操作

在目标位置删除数据元素的流程：
A、从头结点开始，通过current指针定位到目标位置
B、使用toDel指针指向要被删除的结点
C、删除结点，并连接相邻结点的逻辑关系

boolremove(intindex){//判断目标位置是否合法boolret=(0<=index)&&(index<m_length);if(ret){//当前结点指向头结点Node*current=&m_header;//遍历到目标位置for(inti=0;i<index;i++){current=current->next;}//使用toDel指向要删除的结点Node*toDel=current->next;//将当前结点的下一个结点指向要删除结点的下一个结点current->next=toDel->next;m_length--;//链表结点长度减1deletetoDel;//释放要删除的结点的堆空间}else{THROW_EXCEPTION(IndexOutOfBoudsException,"Parameterindeisinvalid...");}returnret;}

3、设置目标结点的值

设置目标结点的值的流程如下：
A、从头结点开始，通过current指针定位到目标位置
B、修改目标结点的数据域的值

boolset(intindex,constT&value){//判断目标位置是否合法boolret=(0<=index)&&(index<m_length);if(ret){//将当前结点指向头结点Node*current=&m_header;//遍历到目标位置for(inti=0;i<index;i++){current=current->next;}//修改目标结点的数据域的值current->next->value=value;}else{THROW_EXCEPTION(IndexOutOfBoudsException,"Parameterindeisinvalid...");}returnret;}

4、获取目标结点的值

boolget(intindex,T&value)const{//判断目标位置是否合法boolret=(0<=index)&&(index<m_length);if(ret){//当前结点指向头结点Node*current=&m_header;//遍历到目标位置for(inti=0;i<index;i++){current=current->next;}//获取目标结点的数据域的值value=current->next->value;}else{THROW_EXCEPTION(IndexOutOfBoudsException,"Parameterindeisinvalid...");}returnret;}//重载版本Tget(intindex)const{Tret;get(index,ret);returnret;}

5、获取单链表的长度

intlength()const{returnm_length;}

6、单链表的清空操作

voidclear(){//遍历删除结点while(m_header.next){//要删除的结点为头结点的下一个结点Node*toDel=m_header.next;//将头结点的下一个结点指向删除结点的下一个结点m_header.next=toDel->next;deletetoDel;//释放要删除结点}m_length=0;}

三、单链表的优化

1、单链表中头结点的缺陷

structNode:publicObject{Tvalue;//数据域Node*next;//指针域};mutableNodem_header;

由于单链表在构建时必须先创建头结点，头结点在创建时必须调用具体类型的构造函数，如果具体类型的构造函数抛出异常，则单链表对象将构建失败，并会传递具体类型构造函数的异常。

classTest{public:Test(){throw0;}};intmain(){LinkedList<Test>l;return0;}

因此，为了确保模板类的健壮性，需要对头结点的创建进行优化，即在创建单链表对象时不调用具体类型的构造函数。

mutablestruct:publicObject{charreserved[sizeof(T)];//占位空间Node*next;}m_header;

创建的匿名的头结点m_header的内存布局与Node对象的内存布局完全一样，并且不会调用具体类型T的构造函数。

2、目标位置定位的代码优化

单链表的操作中经常会定位到目标位置，因此可以将此部分代码独立构建一个函数。

Node*position(intindex)const{//指针指向头结点Node*ret=reinterpret_cast<Node*>(&m_header);//遍历到目标位置for(inti=0;i<index;i++){ret=ret->next;}returnret;}

3、链表的元素查找操作

为List模板类增加一个find操作：
virtual int find(const T& value)const = 0;
顺序存储结构的线性表SeqList模板类的find实现如下：

intfind(constT&value)const{intret=-1;//遍历线性表for(inti=0;i<m_length;i++){//如果找到元素，退出循环if(m_array[i]=value){ret=i;break;}}returnret;}

链式存储结构的线性表的find操作如下：

intfind(constT&value)const{intret=-1;//指向头结点Node*node=m_header.next;inti=0;while(node){//找到元素，退出循环if(node->value==value){ret=i;break;}else{node=node->next;i++;}}returnret;}

4、时间复杂度分析

在实际工程开发中，时间复杂度只是效率的一个参考指标。对于内置基础类型，顺序存储结构实现的线性表与链式存储结构实现的线性表的效率基本相同。对于自定义类类型，顺序存储结构实现的线性表比链式存储结构实现的线性表效率要低，原因在于顺序存储结构实现的线性表要设计大量的数据元素的复制，如果自定义类型的拷贝耗时严重，则效率会很低。
顺序存储结构实现的线性表的插入和删除操作涉及大量对象的复制操作，链式存储结构实现的线性表的插入和删除操作只涉及指针的操作，不会涉及数据对象的复制。
顺序存储结构实现的线性表的数据访问支持随机访问，可直接定位数据对象。链式存储结构实现的线性表的数据访问必须顺序访问，必须从头开始访问数据对象，无法直接定位。
因此，顺序存储结构实现的线性表适合数据类型的类型相对简单，不涉及深拷贝，数据元素相对固定，访问操作远多于插入和删除的场合。链式存储结构实现的线性表适合数据元素的类型复杂，复制操作耗时，数据元素不稳定，需要经常插入和删除操作，访问操作较少的场合。

5、单链表的遍历

通常遍历链表的方法时间复杂度为O（n^2）

for(inti=0;i<ll.length();i++){ll.get(i);}

通过使用游标的方法将遍历链表的时间复杂度优化为O（n）：
A、在单链表的内部定义一个游标（Node* m_current）
B、遍历开始前将游标指向位置为0的数据元素
C、获取游标指向的数据元素
D、通过结点中的next指针移动游标
提供一组遍历相关成员函数，以线性时间复杂度遍历链表：

boolmove(intpos,intstep=1){boolret=(0<=pos)&&(pos<m_length)&&(0<step);if(ret){m_current=position(pos);m_step=step;}returnret;}boolend(){returnm_current==NULL;}Tcurrent(){if(!end()){returnm_current->value;}else{THROW_EXCEPTION(InvalidOperationException,"InvalidOperation...");}}boolnext(){inti=0;while((i<m_step)&&(!end())){m_current=m_current->next;i++;}return(i==m_step);}

使用游标遍历链表的方法：

for(ll.move(0);!ll.end();ll.next()){cout<<ll.current()<<endl;}

6、单链表的翻转

单链表反转有递归和非递归两种算法。
单链表翻转的递归实现：

Node*reverse(Node*list){Node*ret=NULL;//如果单链表为空if(list==NULL||list->next==NULL){ret=list;}else{Node*guard=list->next;ret=reverse(list->next);guard->next=list;list->next=NULL;}returnret;}

单链表翻转的非递归实现：

Node*reverse(Node*header){Node*guard=NULL;//链表翻转后的头结点Node*current=reinterpret_cast<Node*>(header);//当前结点Node*prev=NULL;//前一结点while(current!=NULL){Node*pNext=current->next;//下一结点if(NULL==pNext)//如果是单结点链表{guard=current;}current->next=prev;//当前结点的下一个结点指向前一结点,实现翻转prev=current;//将前一结点移到当前结点位置current=pNext;//将当前结点后移}returnguard;}

四、单链表的实现

template<typenameT>classLinkedList:publicList<T>{protected:structNode:publicObject{Tvalue;//数据域Node*next;//指针域};mutablestruct:publicObject{charreserved[sizeof(T)];//占位空间Node*next;}m_header;intm_length;intm_step;Node*m_current;protected:Node*position(intindex)const{//指针指向头结点Node*ret=reinterpret_cast<Node*>(&m_header);//遍历到目标位置for(inti=0;i<index;i++){ret=ret->next;}returnret;}public:LinkedList(){m_header.next=NULL;m_length=0;m_step=1;m_current=NULL;}virtual~LinkedList(){clear();}boolinsert(intindex,constT&value){//判断目标位置是否合法boolret=(0<=index)&&(index<=m_length);if(ret){//创建新的结点Node*node=createNode();if(node!=NULL){//当前结点定位到目标位置Node*current=position(index);//修改插入结点的值node->value=value;//将当前位置的下一个结点作为插入结点的下一个结点node->next=current->next;//将要插入结点作为当前结点的下一个结点current->next=node;m_length++;//链表结点长度加1}else{THROW_EXCEPTION(NoEnoughMemoryException,"Noenoughmemmory...");}}else{THROW_EXCEPTION(IndexOutOfBoudsException,"Parameterindexisinvalid...");}returnret;}boolinsert(constT&value){returninsert(m_length,value);}boolremove(intindex){//判断目标位置是否合法boolret=(0<=index)&&(index<m_length);if(ret){//当前结点指向头结点Node*current=position(index);//使用toDel指向要删除的结点Node*toDel=current->next;//将当前结点的下一个结点指向要删除结点的下一个结点current->next=toDel->next;m_length--;//链表结点长度减1destroy(toDel);//释放要删除的结点的堆空间}else{THROW_EXCEPTION(IndexOutOfBoudsException,"Parameterindeisinvalid...");}returnret;}boolset(intindex,constT&value){//判断目标位置是否合法boolret=(0<=index)&&(index<m_length);if(ret){//将当前结点指向头结点Node*current=position(index);//修改目标结点的数据域的值current->next->value=value;}else{THROW_EXCEPTION(IndexOutOfBoudsException,"Parameterindeisinvalid...");}returnret;}boolget(intindex,T&value)const{//判断目标位置是否合法boolret=(0<=index)&&(index<m_length);if(ret){//当前结点指向头结点Node*current=position(index);//遍历到目标位置//获取目标结点的数据域的值value=current->next->value;}else{THROW_EXCEPTION(IndexOutOfBoudsException,"Parameterindeisinvalid...");}returnret;}//重载版本Tget(intindex)const{Tret;if(get(index,ret))returnret;}intlength()const{returnm_length;}intfind(constT&value)const{intret=-1;//指向头结点Node*node=m_header.next;inti=0;while(node){//找到元素，退出循环if(node->value==value){ret=i;break;}else{node=node->next;i++;}}returnret;}voidclear(){//遍历删除结点while(m_header.next){//要删除的结点为头结点的下一个结点Node*toDel=m_header.next;//将头结点的下一个结点指向删除结点的下一个结点m_header.next=toDel->next;m_length--;destroy(toDel);//释放要删除结点}}boolmove(intpos,intstep=1){boolret=(0<=pos)&&(pos<m_length)&&(0<step);if(ret){m_current=position(pos)->next;m_step=step;}returnret;}boolend(){returnm_current==NULL;}Tcurrent(){if(!end()){returnm_current->value;}else{THROW_EXCEPTION(InvalidOperationException,"InvalidOperation...");}}boolnext(){inti=0;while((i<m_step)&&(!end())){m_current=m_current->next;i++;}return(i==m_step);}virtualNode*createNode(){returnnewNode();}virtualvoiddestroy(Node*node){deletenode;}};

五、静态单链表

1、单链表的缺陷

长时间使用单链表频繁增加和删除数据元素时，堆空间会产生大量内存碎片，导致系统运行缓慢。

2、静态单链表的设计

静态单链表的实现要点：
A、通过类模板实现静态单链表
B、在类中定义固定大小的空间
C、重写create、destroy函数，改变内存的分配和释放方式
D、在Node类中重载operator new操作符，用于在指定内存上创建对象。

3、静态单链表的实现

template<typenameT,intN>classStaticLinkedList:publicLinkedList<T>{protected:typedeftypenameLinkedList<T>::NodeNode;structSNode:publicNode{//重载new操作符void*operatornew(unsignedintsize,void*loc){returnloc;}};unsignedcharm_space[N*sizeof(Node)];//顺序存储空间boolm_used[N];//空间可用标识public:StaticLinkedList(){for(inti=0;i<N;i++){m_used[i]=false;}}Node*createNode(){SNode*ret=NULL;for(inti=0;i<N;i++){if(!m_used[i]){ret=reinterpret_cast<SNode*>(m_space)+i;ret=new(ret)SNode();m_used[i]=true;break;}}returnret;}voiddestroy(Node*node){SNode*space=reinterpret_cast<SNode*>(m_space);SNode*pn=dynamic_cast<SNode*>(node);for(inti=0;i<N;i++){if(pn==space+i){m_used[i]=false;pn->~SNode();}}}intcapacty(){returnN;}};

静态单链表拥有单链表的所有操作，在预留的顺序存储空间中创建结点对象，适合于最大数据元素个数固定需要频繁增加和删除数据元素的场合。