欢迎阅读这篇文章 目录1、链表2、单链表2.1单链表的定义2.2接口函数定义2.3初始化2.4遍历打印和求长度2.5查找2.5.1按值查找2.5.2按下标查找2.6插入2.7删除2.8头尾删除插入2.8.1头插2.8.2尾插2.8.3头删2.8.4尾删2.9销毁3、链表的分类3.1 分类介绍3.2双向链表的结构3.3循环链表的结构3.4单链表和循环单链表的比较3.5双向链表和双向循环链表比较4、带头双向循环链表的实现4.1接口函数定义4.2初始化/销毁/打印/查找4.3插入4.4删除4.5头尾插入删除1、链表我们前面介绍了顺序表是元素存储在物理上连续空间中优势是访问任意位序元素的时间复杂度事O ( 1 ) O(1)O(1)但是要想插入元素需要挪动大量的数据时间复杂度是O ( n ) O(n)O(n)并且空间如果满了就需要扩容。所以发明了链式结构来存储线性表。链式存储把逻辑上相邻的数据元素存储在任意的一组物理存储单元中数据元素之间的逻辑关系用指针来表示。链表的优势在于可以按需申请空间不再需要扩容需要存储一个数据就申请一块空间用指针将空间与空间链接起来存储数据和指针的这一块空间叫做结点节点。还有优势是在某个节点位置插入和删除数据不再需要挪动数据直接更改结点之间的链接关系。链表有很多种结构先看一个单链表2、单链表2.1单链表的定义单链表的结点中既要存储值也要存储后继元素结点的指针。结点的定义//定义结点typedefintLDataType;typedefstructListNode{LDataType data;//存放数据structListNode*next;//存放后继结点的指针}LNode,*LinkList;单链表的特点指向第一个结点的指针叫头指针。尾结点的指针指向空单链表分为带头结点和不带头结点两种结构。头结点也叫哨兵位不存储有效数据。2.2接口函数定义以下定义是针对带头结点的单链表进行研究的。#includestdio.h#includestdlib.h#includeassert.htypedefintLDataType;//定义结点typedefstructListNode{LDataType data;//存放数据structListNode*next;//存放下一个结点的地址}LNode,*LinkList;//创建一个新结点LNode*BuyListNode(intdata);//初始化LNode*ListInit();//打印链表voidListprint(LNode*L);//获取链表中有效元素的个数intListsize(LNode*L);//按值查找LNode*ListLocateElem(LNode*L,LDataType x);//按下标查找LNode*ListGetElem(LNode*L,inti);//在下标为i的位置插入元素xvoidListInsert(LNode*L,inti,LDataType x);//删除下标为i的结点返回删除结点里存放的数据LDataTypeListDelete(LNode*L,inti);//头插voidListPushFront(LNode*L,LDataType x);//尾插voidListPushBack(LNode*L,LDataType x);//头删LDataTypeListPopFront(LNode*L);//尾删LDataTypeListPopBack(LNode*L);//销毁voidListDestroy(LNode*L);2.3初始化LNode* ListInit()初始化函数使⽤了返回哨兵位头结点因为我们函数内部要创建⼀个头结点返回头结点指针。代码演示//新建一个结点LNode*BuyListNode(intdata){//申请空间LNode*newNode(LNode*)malloc(sizeof(LNode));if(newNodeNULL){perror(BuyListNode malloc:);returnNULL;}//开辟成功后对结点中的数据域和指针域进行初始化newNode-datadata;newNode-nextNULL;returnnewNode;}LNode*ListInit(){LNode*nodeBuyListNode(-1);returnnode;}如果使⽤传参⽅式调⽤ListInit以获取指向哨兵位的头指针就必须使⽤⼆级指针LNode**作为形参才能解决问题void ListInit(LNode** pL)。或者使用C引用的方式即void ListInit(LNode pL);2.4遍历打印和求长度打印的核心操作是遍历链表遍历链表的本质在当前结点中的next成员拿到下一个结点的地址进行迭代。代码演示voidListprint(LNode*L){//哨兵位头指针不为空assert(L);//定义一个指针指向每一个结点LNode*curL-next;while(cur!NULL){printf(%d-,cur-data);curcur-next;}printf(NULL\n);}获取链表中有效元素的个数代码演示intListLocateElem(LNode*L){intn0;LNode*curL-next;while(cur!NULL){curcur-next;n;}returnn;}2.5查找链表的查找分为按值查找和按下标查找2.5.1按值查找按值查找是遍历⼀遍链表找到第⼀个值跟x相等的结点即返回没有找到返回NULL。代码演示LNode*ListLocateElem(LNode*L,LDataType x){assert(L);LNode*curL-next;while(cur!NULL){if(cur-datax){returncur;}curcur-next;}returnNULL;}2.5.2按下标查找按下标查找相对更复杂一些需要构造一个计数器j根据j的大小去遍历当ji的时候就到了下标为i的这个结点。需要jiiNode!NULL作为循环条件因为链表的第i个结点不⼀定存在。当i大于目前链表中结点个数的时候就不存在。代码演示LNode*ListGetElem(LNode*L,inti){assert(L);intj0;LNode*iNodeL-next;while(jiiNode!NULL){iNodeiNode-next;j;}returniNode;}2.6插入链表的插入不再需要像顺序表那样挪动数据只需要改动结点间的链接关系但是要在第i个结点之前插入所以就要能够找到第i-1个结点i_1Node。核心操作找到i_1Node方法是利用计数器j和下标i的关系进行控制遍历次数找到i_1Node计数器j应该从-1开始i_1Node最初应该是头指针以保证头插的时候的正确性。找到i_1Node后需要开辟一个新的结点newNode需要让i_1Node-next指向newNode而newNode-next需要指向i_Node-next(就是原iNode)。注意为了保证正确我们需要先操作newNode-nexti_Node-next再操作i_1Node-nextnewNode。因为我们需要i_Node-next来代表第i个结点如果先执行i_1Node-nextnewNode那么这时i_Node-next就是新插入的那个结点无法找到第i个结点。或者创建一个临时指针temp存储i_Node-next后面再newNode-nexttemp即可这样顺序就不影响了。代码演示voidListInsert(LNode*L,inti,LDataType x){assert(L);assert(i0);//寻找i_1Node结点intj-1;LNode*i_1NodeL;while(ji-1i_1Node!NULL){i_1Nodei_1Node-next;j;}//没有第i-1个结点说明i非法assert(i_1Node!NULL);//找到了第i-1个结点LNode*newNodeBuyListNode(x);//创建新结点放入要插入的元素x//改变结点间的链接关系newNode-nexti_1Node-next;//让新插入的结点的next指向原来下标为i的结点i_1Node-nextnewNode;//让原来的下标i-1的位置的结点指向新插入的结点}2.7删除链表的删除不再需要向顺序表那样挪动数据只需要改动结点间的链接关系要删除第i个结点就需要找到第i-1个结点叫i_1Node。核心操作找到i_1Node方法是利用计数器j和下标i的关系进行控制遍历次数找到i_1Node计数器j应该从-1开始i_1Node最初应该是头指针以保证头删的时候的正确性。具体操作的时候可以将删除的那个结点的数据返回要先创建一个临时指针变量存储第i个结点的地址防止后续找不到这个结点的位置。执行完寻找i_1Node的功能后要检查前驱结点后的那个结点是否存在检查要删除的结点是否存在。注意如果没有头结点的链表删除则形参LNode** pL必须⽤⼆级指针因为如果i0头删时需要让实参头指针LT指向第i1个结点(第2个结点)也就是*pL iNode-next;所以不带头结点删除更复杂⼀些因为要对头删单独判断处理且要⽤⼆级指针处理。代码演示//删除下标为i的结点返回删除结点里存放的数据LDataTypeListDelete(LNode*L,inti){assert(L);assert(i0);//查找下标为i-1的元素intj-1;LNode*i_1NodeL;while(ji-1i_1Node!NULL){i_1Nodei_1Node-next;j;}//断言i不合法的情况和检查要删除的结点是否存在assert(i_1Node!NULLi_1Node-next!NULL);LNode*iNodei_1Node-next;//修改结点间链接地址i_1Node-nextiNode-next;LDataType xiNode-data;//释放删除的结点free(iNode);returnx;}2.8头尾删除插入这些接口的实现可以直接复用上方的插入和删除函数2.8.1头插代码演示voidListPushFront(LNode*L,LDataType x){assert(L);LNode*newNodeBuyListNode(x);newNode-nextL-next;L-nextnewNode;}时间复杂度O ( 1 ) O(1)O(1)2.8.2尾插代码演示voidListPushBack(LNode*L,LDataType x){assert(L);LNode*curL;//若链表为空之前的写法则会导致后面空指针访问//找尾结点while(cur-next){curcur-next;}LNode*newNodeBuyListNode(x);newNode-nextcur-next;cur-nextnewNode;}时间复杂度是O ( n ) O(n)O(n)2.8.3头删代码演示LDataTypeListPopFront(LNode*L){assert(L);assert(L-next);//平常练习用实际工程若是release版本assert就失效了就发挥不了作用。LNode*DelNodeL-next;L-nextDelNode-next;LDataType xDelNode-data;free(DelNode);returnx;}时间复杂度是O ( 1 ) O(1)O(1)2.8.4尾删代码演示LDataTypeListPopBack(LNode*L){assert(L);//判空assert(L-next);//找到倒数第二个节点LNode*curL;while(cur-next-next){curcur-next;}LNode*DelNodecur-next;cur-nextDelNode-next;LDataType xDelNode-data;free(DelNode);returnx;}时间复杂度是O ( n ) O(n)O(n)2.9销毁链表的销毁就是不断遍历释放链表结点不过需要先保存下⼀个结点否则free了当前结点就找不到下⼀个结点了。代码演示voidListDestroy(LNode*L){assert(L);//构造遍历指针LNode*curL-next;//遍历释放while(cur!NULL){//保存当前结点的下一个结点的指针LNode*nextcur-next;//释放当前结点free(cur);//把刚刚保存的下一个结点的指针赋给遍历指针curnext;}3、链表的分类3.1 分类介绍根据不同的需要实践应用中出现了多种不同的链表结构分为单向链表和双向链表、带头结点的链表和不带头结点的链表、循环链表和非循环链表。将以上几种链表进行组合可以组合出8种链表结构重点掌握带头结点单链表/不带头结点单链表/双向循环链表即可。3.2双向链表的结构通过前面的了解我们知道单链表中保存了指向后继结点的地址所以在单链表中找当前结点的后继结点很容易但要获取当前结点的前驱结点就很麻烦只能从头开始遍历时间复杂度为O ( n ) O(n)O(n)双向链表相比单链表的最大的一个特征是多了一个前驱指针一些场景需要获取当前结点的前驱结点时就需要用到双向链表。双向链表的⼀些不⾜是找尾结点依旧不是很⽅便另外呢头尾插⼊删除考虑的边界依旧⽐较多。后面的带头双向循环链表就可以很好地解决这些问题。typedefintDLDataType;structDListNode{DLDataType data;//存放数据元素structDListNode*per;//指向前驱元素structDListNode*next;//指向后继元素};3.3循环链表的结构实践应用中最常见的不是在第i个位序处插入删除元素而是在头尾插入删除数据。单链表头插头删效率很高可以做到时间复杂度为O ( 1 ) O(1)O(1)但是对于尾插尾删需要找到尾结点时间复杂度为O ( n ) O(n)O(n)。双向链表头插头删效率⾼确定某个结点位置以后插⼊删除效率也很⾼均可以做到时间复杂度O ( 1 ) O(1)O(1)同样尾插尾删需要增加⼀个尾指针相对⿇烦所以这⾥我们引入循环链表可以解决这⾥的问题。循环链表又可分为单向循环链表和双向循环链表单向循环链表就是让尾结点的next指向头结点双向循环链表就是尾结点的next指向头结点同时头结点的prev指向尾结点。实践中双向循环链表⾮常实⽤C标准库(STL)中list就是使⽤的这个结构实现因为他可以通过头结点的prev指针找到尾结点轻松实现尾插尾删。也就是说这个结构头尾插⼊删除效率都是O ( 1 ) O(1)O(1)确定某个结点位置以后得插⼊删除也是O ( 1 ) O(1)O(1)。3.4单链表和循环单链表的比较循环单链表和单链表在结构体定义和操作中有些不一样的地方初始化不同循环单链表初始化时要让头结点的next指向⾃⼰。//单链表voidListInit(structListNode*L){LBuyListNode(-1);L-nextNULL;}//循环单链表voidListCInit(structCListNode*L){LBuyListNode(-1);assert(L);L-nextL;}遍历时判断结束的逻辑不同循环单链表遍历不能让迭代指针指向空作为结束条件⽽是⾛⼀圈等于头结点时结束。//单链表intListSize(structListNode*L){intsize0;structListNode*curL-next;while(cur!NULL){curcur-next;size;}returnsize;}//循环单链表intCListSize(structCListNode*L){intsize0;structCListNode*curL-next;while(cur!L){curcur-next;size;}returnsize;}3.5双向链表和双向循环链表比较带头双向循环链表相比于双向链表的优势主要体现在两⽅⾯第⼀可以通过头结点的prev快速找到尾结点⾼效实现尾插尾删第⼆pos结点位置插⼊删除时可以更简单因为不需要考虑尾结点的的后继结点为空的情况。4、带头双向循环链表的实现4.1接口函数定义#includestdio.h#includestdlib.h#includeassert.htypedefintDCListDataType;typedefstructDCListNode{DCListDataType data;structDCListNode*prev;structDCListNode*next;}DCListNode;//链表的头结点初始化DCListNode*DCListInit();//销毁链表voidDCListDestroy(DCListNode*L);//打印链表voidDCListPrint(DCListNode*L);//获取链表中下标为i的结点DCListNode*DCListGetElem(DCListNode*L,inti);//在结点pos后插入一个元素为x的结点voidDCListInsert(DCListNode*pos,DCListDataType x);//删除pos结点voidDCListDelete(DCListNode*pos);4.2初始化/销毁/打印/查找#includeDCList.h//创建新结点DCListNode*BuyDCListNode(DCListDataType data){DCListNode*L(DCListNode*)malloc(sizeof(DCListNode));if(LNULL){perror(BuyDCListNode);returnNULL;}// 初始化时要让⾃⼰指向⾃⼰否则就会出问题L-datadata;L-nextL;L-prevL;returnL;}//链表头结点初始化DCListNode*DCListInit(){DCListNode*LBuyDCListNode(-1);assert(L);returnL;}//销毁voidDestoryDCList(DCListNode*L){assert(L);//先销毁有效结点DCListNode*curL-next;while(cur!L){L-nextcur-next;free(cur);curL-next;}//再销毁头结点free(L);}//打印链表voidDCListPrint(DCListNode*L){assert(L);DCListNode*curL-next;while(cur!L){printf(%d-,cur-data);curcur-next;}printf(\n);// //从后往前打印// cur L-prev;// while(cur!L)// {// printf(%d-,cur-data);// cur cur-prev;// }// printf(\n);}//获取链表中下标为i的结点DCListNode*DCListGetElem(DCListNode*L,inti){assert(L);intj0;DCListNode*curL-next;while(cur!Lji){curcur-next;j;}//如果循环结束后j不等于i说明i不合法assert(ji);returncur;}4.3插入在pos结点之后插⼊⼀个新结点newNode。pos可以指向的任意结点(包括头结点)不需要考虑pos前⼀个或者后⼀个为空的情况。如果是双向链表(⾮循环)要注意的是pos为尾结点时需要考虑pos-next为空的情况。注意在修改结点间的链接关系的时候要先修改newNode -next pos和pos-next-prev newNode再修改newNode-prev pos和pos-next newNode。因为需要通过pos-next记录原链表的pos后面的结点。代码演示voidDCListInsert(DCListNode*pos,DCListDataType x){assert(pos);//创建一个新结点DCListNode*newNodeBuyDCListNode(x);//改变链接关系newNode-nextpos-next;pos-next-prevnewNode;pos-nextnewNode;newNode-prevpos;}4.4删除改动两个指针链接关系即可。pos可以指向除了头结点以外的任意结点不需要考虑pos前⼀个或者后⼀个为空的情况。如果是双向链表(⾮循环)要注意的是pos为尾结点时需要考虑pos-next为空的情况。代码演示voidDCListDelete(DCListNode*pos){assert(pos);pos-prev-nextpos-next;pos-next-prevpos-prev;free(pos);}4.5头尾插入删除对于头插尾插和头删尾删可以直接复用上面的插入和删除函数。
欢迎阅读这篇文章 目录1、链表2、单链表2.1单链表的定义2.2接口函数定义2.3初始化2.4遍历打印和求长度2.5查找2.5.1按值查找2.5.2按下标查找2.6插入2.7删除2.8头尾删除插入2.8.1头插2.8.2尾插2.8.3头删2.8.4尾删2.9销毁3、链表的分类3.1 分类介绍3.2双向链表的结构3.3循环链表的结构3.4单链表和循环单链表的比较3.5双向链表和双向循环链表比较4、带头双向循环链表的实现4.1接口函数定义4.2初始化/销毁/打印/查找4.3插入4.4删除4.5头尾插入删除1、链表我们前面介绍了顺序表是元素存储在物理上连续空间中优势是访问任意位序元素的时间复杂度事O ( 1 ) O(1)O(1)但是要想插入元素需要挪动大量的数据时间复杂度是O ( n ) O(n)O(n)并且空间如果满了就需要扩容。所以发明了链式结构来存储线性表。链式存储把逻辑上相邻的数据元素存储在任意的一组物理存储单元中数据元素之间的逻辑关系用指针来表示。链表的优势在于可以按需申请空间不再需要扩容需要存储一个数据就申请一块空间用指针将空间与空间链接起来存储数据和指针的这一块空间叫做结点节点。还有优势是在某个节点位置插入和删除数据不再需要挪动数据直接更改结点之间的链接关系。链表有很多种结构先看一个单链表2、单链表2.1单链表的定义单链表的结点中既要存储值也要存储后继元素结点的指针。结点的定义//定义结点typedefintLDataType;typedefstructListNode{LDataType data;//存放数据structListNode*next;//存放后继结点的指针}LNode,*LinkList;单链表的特点指向第一个结点的指针叫头指针。尾结点的指针指向空单链表分为带头结点和不带头结点两种结构。头结点也叫哨兵位不存储有效数据。2.2接口函数定义以下定义是针对带头结点的单链表进行研究的。#includestdio.h#includestdlib.h#includeassert.htypedefintLDataType;//定义结点typedefstructListNode{LDataType data;//存放数据structListNode*next;//存放下一个结点的地址}LNode,*LinkList;//创建一个新结点LNode*BuyListNode(intdata);//初始化LNode*ListInit();//打印链表voidListprint(LNode*L);//获取链表中有效元素的个数intListsize(LNode*L);//按值查找LNode*ListLocateElem(LNode*L,LDataType x);//按下标查找LNode*ListGetElem(LNode*L,inti);//在下标为i的位置插入元素xvoidListInsert(LNode*L,inti,LDataType x);//删除下标为i的结点返回删除结点里存放的数据LDataTypeListDelete(LNode*L,inti);//头插voidListPushFront(LNode*L,LDataType x);//尾插voidListPushBack(LNode*L,LDataType x);//头删LDataTypeListPopFront(LNode*L);//尾删LDataTypeListPopBack(LNode*L);//销毁voidListDestroy(LNode*L);2.3初始化LNode* ListInit()初始化函数使⽤了返回哨兵位头结点因为我们函数内部要创建⼀个头结点返回头结点指针。代码演示//新建一个结点LNode*BuyListNode(intdata){//申请空间LNode*newNode(LNode*)malloc(sizeof(LNode));if(newNodeNULL){perror(BuyListNode malloc:);returnNULL;}//开辟成功后对结点中的数据域和指针域进行初始化newNode-datadata;newNode-nextNULL;returnnewNode;}LNode*ListInit(){LNode*nodeBuyListNode(-1);returnnode;}如果使⽤传参⽅式调⽤ListInit以获取指向哨兵位的头指针就必须使⽤⼆级指针LNode**作为形参才能解决问题void ListInit(LNode** pL)。或者使用C引用的方式即void ListInit(LNode pL);2.4遍历打印和求长度打印的核心操作是遍历链表遍历链表的本质在当前结点中的next成员拿到下一个结点的地址进行迭代。代码演示voidListprint(LNode*L){//哨兵位头指针不为空assert(L);//定义一个指针指向每一个结点LNode*curL-next;while(cur!NULL){printf(%d-,cur-data);curcur-next;}printf(NULL\n);}获取链表中有效元素的个数代码演示intListLocateElem(LNode*L){intn0;LNode*curL-next;while(cur!NULL){curcur-next;n;}returnn;}2.5查找链表的查找分为按值查找和按下标查找2.5.1按值查找按值查找是遍历⼀遍链表找到第⼀个值跟x相等的结点即返回没有找到返回NULL。代码演示LNode*ListLocateElem(LNode*L,LDataType x){assert(L);LNode*curL-next;while(cur!NULL){if(cur-datax){returncur;}curcur-next;}returnNULL;}2.5.2按下标查找按下标查找相对更复杂一些需要构造一个计数器j根据j的大小去遍历当ji的时候就到了下标为i的这个结点。需要jiiNode!NULL作为循环条件因为链表的第i个结点不⼀定存在。当i大于目前链表中结点个数的时候就不存在。代码演示LNode*ListGetElem(LNode*L,inti){assert(L);intj0;LNode*iNodeL-next;while(jiiNode!NULL){iNodeiNode-next;j;}returniNode;}2.6插入链表的插入不再需要像顺序表那样挪动数据只需要改动结点间的链接关系但是要在第i个结点之前插入所以就要能够找到第i-1个结点i_1Node。核心操作找到i_1Node方法是利用计数器j和下标i的关系进行控制遍历次数找到i_1Node计数器j应该从-1开始i_1Node最初应该是头指针以保证头插的时候的正确性。找到i_1Node后需要开辟一个新的结点newNode需要让i_1Node-next指向newNode而newNode-next需要指向i_Node-next(就是原iNode)。注意为了保证正确我们需要先操作newNode-nexti_Node-next再操作i_1Node-nextnewNode。因为我们需要i_Node-next来代表第i个结点如果先执行i_1Node-nextnewNode那么这时i_Node-next就是新插入的那个结点无法找到第i个结点。或者创建一个临时指针temp存储i_Node-next后面再newNode-nexttemp即可这样顺序就不影响了。代码演示voidListInsert(LNode*L,inti,LDataType x){assert(L);assert(i0);//寻找i_1Node结点intj-1;LNode*i_1NodeL;while(ji-1i_1Node!NULL){i_1Nodei_1Node-next;j;}//没有第i-1个结点说明i非法assert(i_1Node!NULL);//找到了第i-1个结点LNode*newNodeBuyListNode(x);//创建新结点放入要插入的元素x//改变结点间的链接关系newNode-nexti_1Node-next;//让新插入的结点的next指向原来下标为i的结点i_1Node-nextnewNode;//让原来的下标i-1的位置的结点指向新插入的结点}2.7删除链表的删除不再需要向顺序表那样挪动数据只需要改动结点间的链接关系要删除第i个结点就需要找到第i-1个结点叫i_1Node。核心操作找到i_1Node方法是利用计数器j和下标i的关系进行控制遍历次数找到i_1Node计数器j应该从-1开始i_1Node最初应该是头指针以保证头删的时候的正确性。具体操作的时候可以将删除的那个结点的数据返回要先创建一个临时指针变量存储第i个结点的地址防止后续找不到这个结点的位置。执行完寻找i_1Node的功能后要检查前驱结点后的那个结点是否存在检查要删除的结点是否存在。注意如果没有头结点的链表删除则形参LNode** pL必须⽤⼆级指针因为如果i0头删时需要让实参头指针LT指向第i1个结点(第2个结点)也就是*pL iNode-next;所以不带头结点删除更复杂⼀些因为要对头删单独判断处理且要⽤⼆级指针处理。代码演示//删除下标为i的结点返回删除结点里存放的数据LDataTypeListDelete(LNode*L,inti){assert(L);assert(i0);//查找下标为i-1的元素intj-1;LNode*i_1NodeL;while(ji-1i_1Node!NULL){i_1Nodei_1Node-next;j;}//断言i不合法的情况和检查要删除的结点是否存在assert(i_1Node!NULLi_1Node-next!NULL);LNode*iNodei_1Node-next;//修改结点间链接地址i_1Node-nextiNode-next;LDataType xiNode-data;//释放删除的结点free(iNode);returnx;}2.8头尾删除插入这些接口的实现可以直接复用上方的插入和删除函数2.8.1头插代码演示voidListPushFront(LNode*L,LDataType x){assert(L);LNode*newNodeBuyListNode(x);newNode-nextL-next;L-nextnewNode;}时间复杂度O ( 1 ) O(1)O(1)2.8.2尾插代码演示voidListPushBack(LNode*L,LDataType x){assert(L);LNode*curL;//若链表为空之前的写法则会导致后面空指针访问//找尾结点while(cur-next){curcur-next;}LNode*newNodeBuyListNode(x);newNode-nextcur-next;cur-nextnewNode;}时间复杂度是O ( n ) O(n)O(n)2.8.3头删代码演示LDataTypeListPopFront(LNode*L){assert(L);assert(L-next);//平常练习用实际工程若是release版本assert就失效了就发挥不了作用。LNode*DelNodeL-next;L-nextDelNode-next;LDataType xDelNode-data;free(DelNode);returnx;}时间复杂度是O ( 1 ) O(1)O(1)2.8.4尾删代码演示LDataTypeListPopBack(LNode*L){assert(L);//判空assert(L-next);//找到倒数第二个节点LNode*curL;while(cur-next-next){curcur-next;}LNode*DelNodecur-next;cur-nextDelNode-next;LDataType xDelNode-data;free(DelNode);returnx;}时间复杂度是O ( n ) O(n)O(n)2.9销毁链表的销毁就是不断遍历释放链表结点不过需要先保存下⼀个结点否则free了当前结点就找不到下⼀个结点了。代码演示voidListDestroy(LNode*L){assert(L);//构造遍历指针LNode*curL-next;//遍历释放while(cur!NULL){//保存当前结点的下一个结点的指针LNode*nextcur-next;//释放当前结点free(cur);//把刚刚保存的下一个结点的指针赋给遍历指针curnext;}3、链表的分类3.1 分类介绍根据不同的需要实践应用中出现了多种不同的链表结构分为单向链表和双向链表、带头结点的链表和不带头结点的链表、循环链表和非循环链表。将以上几种链表进行组合可以组合出8种链表结构重点掌握带头结点单链表/不带头结点单链表/双向循环链表即可。3.2双向链表的结构通过前面的了解我们知道单链表中保存了指向后继结点的地址所以在单链表中找当前结点的后继结点很容易但要获取当前结点的前驱结点就很麻烦只能从头开始遍历时间复杂度为O ( n ) O(n)O(n)双向链表相比单链表的最大的一个特征是多了一个前驱指针一些场景需要获取当前结点的前驱结点时就需要用到双向链表。双向链表的⼀些不⾜是找尾结点依旧不是很⽅便另外呢头尾插⼊删除考虑的边界依旧⽐较多。后面的带头双向循环链表就可以很好地解决这些问题。typedefintDLDataType;structDListNode{DLDataType data;//存放数据元素structDListNode*per;//指向前驱元素structDListNode*next;//指向后继元素};3.3循环链表的结构实践应用中最常见的不是在第i个位序处插入删除元素而是在头尾插入删除数据。单链表头插头删效率很高可以做到时间复杂度为O ( 1 ) O(1)O(1)但是对于尾插尾删需要找到尾结点时间复杂度为O ( n ) O(n)O(n)。双向链表头插头删效率⾼确定某个结点位置以后插⼊删除效率也很⾼均可以做到时间复杂度O ( 1 ) O(1)O(1)同样尾插尾删需要增加⼀个尾指针相对⿇烦所以这⾥我们引入循环链表可以解决这⾥的问题。循环链表又可分为单向循环链表和双向循环链表单向循环链表就是让尾结点的next指向头结点双向循环链表就是尾结点的next指向头结点同时头结点的prev指向尾结点。实践中双向循环链表⾮常实⽤C标准库(STL)中list就是使⽤的这个结构实现因为他可以通过头结点的prev指针找到尾结点轻松实现尾插尾删。也就是说这个结构头尾插⼊删除效率都是O ( 1 ) O(1)O(1)确定某个结点位置以后得插⼊删除也是O ( 1 ) O(1)O(1)。3.4单链表和循环单链表的比较循环单链表和单链表在结构体定义和操作中有些不一样的地方初始化不同循环单链表初始化时要让头结点的next指向⾃⼰。//单链表voidListInit(structListNode*L){LBuyListNode(-1);L-nextNULL;}//循环单链表voidListCInit(structCListNode*L){LBuyListNode(-1);assert(L);L-nextL;}遍历时判断结束的逻辑不同循环单链表遍历不能让迭代指针指向空作为结束条件⽽是⾛⼀圈等于头结点时结束。//单链表intListSize(structListNode*L){intsize0;structListNode*curL-next;while(cur!NULL){curcur-next;size;}returnsize;}//循环单链表intCListSize(structCListNode*L){intsize0;structCListNode*curL-next;while(cur!L){curcur-next;size;}returnsize;}3.5双向链表和双向循环链表比较带头双向循环链表相比于双向链表的优势主要体现在两⽅⾯第⼀可以通过头结点的prev快速找到尾结点⾼效实现尾插尾删第⼆pos结点位置插⼊删除时可以更简单因为不需要考虑尾结点的的后继结点为空的情况。4、带头双向循环链表的实现4.1接口函数定义#includestdio.h#includestdlib.h#includeassert.htypedefintDCListDataType;typedefstructDCListNode{DCListDataType data;structDCListNode*prev;structDCListNode*next;}DCListNode;//链表的头结点初始化DCListNode*DCListInit();//销毁链表voidDCListDestroy(DCListNode*L);//打印链表voidDCListPrint(DCListNode*L);//获取链表中下标为i的结点DCListNode*DCListGetElem(DCListNode*L,inti);//在结点pos后插入一个元素为x的结点voidDCListInsert(DCListNode*pos,DCListDataType x);//删除pos结点voidDCListDelete(DCListNode*pos);4.2初始化/销毁/打印/查找#includeDCList.h//创建新结点DCListNode*BuyDCListNode(DCListDataType data){DCListNode*L(DCListNode*)malloc(sizeof(DCListNode));if(LNULL){perror(BuyDCListNode);returnNULL;}// 初始化时要让⾃⼰指向⾃⼰否则就会出问题L-datadata;L-nextL;L-prevL;returnL;}//链表头结点初始化DCListNode*DCListInit(){DCListNode*LBuyDCListNode(-1);assert(L);returnL;}//销毁voidDestoryDCList(DCListNode*L){assert(L);//先销毁有效结点DCListNode*curL-next;while(cur!L){L-nextcur-next;free(cur);curL-next;}//再销毁头结点free(L);}//打印链表voidDCListPrint(DCListNode*L){assert(L);DCListNode*curL-next;while(cur!L){printf(%d-,cur-data);curcur-next;}printf(\n);// //从后往前打印// cur L-prev;// while(cur!L)// {// printf(%d-,cur-data);// cur cur-prev;// }// printf(\n);}//获取链表中下标为i的结点DCListNode*DCListGetElem(DCListNode*L,inti){assert(L);intj0;DCListNode*curL-next;while(cur!Lji){curcur-next;j;}//如果循环结束后j不等于i说明i不合法assert(ji);returncur;}4.3插入在pos结点之后插⼊⼀个新结点newNode。pos可以指向的任意结点(包括头结点)不需要考虑pos前⼀个或者后⼀个为空的情况。如果是双向链表(⾮循环)要注意的是pos为尾结点时需要考虑pos-next为空的情况。注意在修改结点间的链接关系的时候要先修改newNode -next pos和pos-next-prev newNode再修改newNode-prev pos和pos-next newNode。因为需要通过pos-next记录原链表的pos后面的结点。代码演示voidDCListInsert(DCListNode*pos,DCListDataType x){assert(pos);//创建一个新结点DCListNode*newNodeBuyDCListNode(x);//改变链接关系newNode-nextpos-next;pos-next-prevnewNode;pos-nextnewNode;newNode-prevpos;}4.4删除改动两个指针链接关系即可。pos可以指向除了头结点以外的任意结点不需要考虑pos前⼀个或者后⼀个为空的情况。如果是双向链表(⾮循环)要注意的是pos为尾结点时需要考虑pos-next为空的情况。代码演示voidDCListDelete(DCListNode*pos){assert(pos);pos-prev-nextpos-next;pos-next-prevpos-prev;free(pos);}4.5头尾插入删除对于头插尾插和头删尾删可以直接复用上面的插入和删除函数。
