数据结构之带头双向循环链表前言一、带头双向循环链表的概念1. 链表前缀的认识2. 带头双向循环链表节点二、带头双向循环链表的功能实现1. 链表节点创建和节点初始化2.链表初始化3. 链表尾插函数4. 链表尾删函数5. 链表定点插入函数6. 链表定点删除函数三、代码汇总1. HDLoopLsit.h 头文件2. HDLoopLsit.c 源文件3. HDLoopLsit_Test.c 源文件四、总结前言上一篇文章我给老铁们介绍了单链表。也介绍了链表可以由带头和不带头单向和双向循环和非循环组成八种链表。上一篇已经给大家介绍了不带头单向非循环链表也就是单链表。这一篇我来介绍链表里叠满buff的带头双向循环链表。一、带头双向循环链表的概念1. 链表前缀的认识与单链表相比带头双向循环链表多了三个前缀概念。分别是带头双向循环。我会分别解释带头指的是比单链表多了一个哨兵位头节点。哨兵位不存储有效数据他起到标识第头节点的意义。双向双向链表是链表节点内部比单向链表的多了一个前驱指针(暂且取名为prev指针)。所以双向链表的节点内有两个指针一个next指针成员指向该节点的下一个节点一个prev指针成员指向该节点的前一个节点。循环单链表的尾节点的next指针被置为空(NULL)。但是循环链表的尾节点内的next指针成员指向头节点形成循环。2. 带头双向循环链表节点无论什么链表都是由一系列节点组成链表的每个节点包含两部分一部分用于存储数据的变量成员另一部分是形成链式链接的指针成员。带头双向循环链表的节点结构体代码如下示例typedefintLTDataType;typedefstructListNode{LTDataType val;structListNode*next;structListNode*prev;//比单链表多了前驱指针}ListNode;二、带头双向循环链表的功能实现前情提要因为链表的实现本质都是大同小异。所以我会着重讲解该链表与单链表的差异部分。详细功能实现我会放在代码汇总里面各位老铁可以直接拿去自己调试。老规矩建议老铁们写一个功能就测试一下。别等到写了一大段代码再去测试调试。到最后爆了一堆错看起来非常头疼。1. 链表节点创建和节点初始化链表是一个个由节点构成的不管要增删查改进行什么操作节点都是基本单位。所以接下来我们要给节点分配空间开辟节点并将它初始化。操作思路依旧三部曲malloc动态分配节点空间。创建完节点后对节点赋值进行初始化。返回节点的地址。代码如下示例structListNode*CreateNode(LTDataType x){ListNode*newnode(structListNode*)malloc(sizeof(ListNode));if(newnodeNULL){perror(malloc fail);exit(-1);}//创建完节点后,对节点进行初始化newnode-valx;newnode-nextNULL;newnode-prevNULL;returnnewnode;}2.链表初始化细心的老铁可能已经发现了上一章单链表只有节点创建和初始化可没有链表的初始化。这是因为单链表创建的时候是链表可以是空的可以一个节点没有。但是带头双向循环链表多了一个哨兵位头节点所以链表永远不为空。也就是说我们对链表的初始化也就是对哨兵位头节点的初始化。可能老铁会问小羊你之前不是说我们最好要用传址调用吗。链表刚创建的时候是为空(NULL)我们初始化之后链表有了哨兵位头节点了地址就不为空了。既然会改变链表的地址我们传参应该传链表地址的地址函数形参应该用二级指针啊没错非常对首先一句话给出我的原因这里用二级指针不划算我们只有在链表初始化的时候会用到二级指针传参。原因解释因为我站在全局代码的宏观角度看只有在链表初始化的时候链表的地址会由空改为哨兵位头节点的地址。哨兵位头节点初始化好了之后链表的头节点将不会改变。换句话说我们用头节点的地址表示链表的地址以后链表头节点的地址不变那么链表的地址也不会发生改变。自然没必要用二级指针了。解决方法那我们不用传址调用那就是用传值调用了。我们要改变链表的地址那我们就穿链表的地址。传值调用形参是实参的拷贝形参的改变不影响实参。没关系我们手动影响直接把链表初始化返回的地址手动赋值给链表地址即可。(可参考第二个代码块)链表初始化代码如下ListNode*LTInit(ListNode*phead){//哨兵位内部不存储有效数据所以初始化的时候给个-1先。pheadCreateNode(-1);//创建哨兵位头节点phead-nextphead;phead-prevphead;returnphead;}链表创建和链表初始话函数调用代码intmain(){//传址调用//ListNode* plist NULL;//LTInit(plist);//传值调用ListNode*plistNULL;//创建链表初始为空plistLTInit(plist);//手动赋值return0;}3. 链表尾插函数带头双向循环链表尾插尾节点的next指针要指向哨兵位头节点哨兵位头节点的prev前驱指针要指向尾节点。一、边界思考因为链表无论什么时候都要有一个哨兵位不能为空所以我们可以断言该链表为不空。这样如果链表为空的话程序就会被强行终止。二、参数设计这里我们传参依旧是传值调用因为我们不需要修改链表的地址。链表的地址就是哨兵位头节点的地址不会发生改变。这个参数的意义就是让我获得头节点的地址。在链表初始化里我们可以判断当链表中只有一个哨兵位头结点的时候他的prev前驱指针和next指针都指向自己构成循环。三、思路设计代码块里我们定义了tail指针指向当前链表的尾节点所以tail phead-prev。找到了当前链表的尾节点之后我们调用函数创建新节点newnode。此时这个newnode就是新的尾节点。再设置好指针之间的对应关系tail-next newnode原尾节点的next指针指向新尾节点。newnode-prev tail新尾节点的前去指针要指向原尾节点。newnode-next phead新尾节点的next指针要指向哨兵位头节点。phead-prev newnode哨兵位头节点的前驱指针要指向新尾节点。代码如下所示voidLTPushBack(structListNode*phead,LTDataType x){assert(phead);//因为链表有哨兵位,所以不可能为空, 要断言ListNode*tailphead-prev;//头结点的前置指针指向尾部节点ListNode*newnodeCreateNode(x);//创建节点tail-nextnewnode;newnode-prevtail;newnode-nextphead;phead-prevnewnode;}4. 链表尾删函数带头双向循环链表尾删思路本质上与尾插没区别。思路三部曲思考边界思考参数找到当前链表的尾节点。在释放掉尾节点前考虑好指针的对应关系。一、边界思考assert(phead) 因为链表无论什么时候都要有一个哨兵位不能为空所以我们可以断言该链表为不空。这样如果链表为空的话程序就会被强行终止。assert(phead-next!phead) 因为我们要尾删且尾删不能删掉哨兵位。 所以我们要防止链表在只有一个哨兵位的时候进行尾删。断言哨兵位头节点的next指针指向的节点不是哨兵位本身。二、边界参数尾删的参数与尾插一样。因为不会修改链表的地址所以依旧传值调用。把头节点的地址传过来即可。三、思路设计代码块里用tail指针表示当前链表的尾节点。tailPrev表示尾节点的前一个节点。如果尾节点被free掉了那么tailPrev就是新的尾节点了。但是在free掉尾节点之前要把指针对应关系处理好。tailPrev-next phead把tailPrev当作新的尾节点他的next指针要指向哨兵位头节点。哨兵位头节点的prev前驱指针要指向新的尾节点tailPrev。此时再去释放掉tail指向的尾节点。再江tail指针置为NULL。代码如下voidLTPopBack(ListNode*phead){assert(phead);//如果链表为空,会删掉哨兵位,我们要防止这种情况,暴力检查//assert(phead-next!phead);//温柔检查if(phead-nextphead){return;}ListNode*tailphead-prev;ListNode*tailPrevtail-prev;tailPrev-nextphead;phead-prevtailPrev;free(tail);tailNULL;LTErase(phead-prev);}5. 链表定点插入函数定点插入是我们想要再pos位置之前插入一个节点并在节点中存放数据x。依旧思路三部曲思考边界思考参数找到当前链表的pos位置的前一个节点。在插入新节点前考虑好指针的对应关系。重复的思考过程大家可以参考尾插和尾删进行思考。值得一说的是如果pos是指向哨兵位头节点那么定点插入就是尾插。原因哨兵位头节点的prev指针指向尾节点。定点插入是再pos位置节点的前面插入一个新节点。其实就是尾插。voidLTInsert(ListNode*pos,LTDataType x){assert(pos);//这里不用断言pos!phead, pos也可以是phead,这样的话就是在phead的前面插入节点,等于尾插ListNode*newnodeCreateNode(x);ListNode*posPrevpos-prev;posPrev-nextnewnode;newnode-prevposPrev;newnode-nextpos;pos-prevnewnode;}6. 链表定点删除函数如果我们想要删除链表中的pos节点我们要利用next指针和prev指针找到pos节点的前一个节点和后一个节点。安排好指针的对应关系后再去释放节点。不然很容易造成野指针问题。分析posNext 代表pos位置节点的后一个节点。posPrev 代表pos位置节点的前一个节点。posPrev的next成员原本是指向pos的但是我们要释放posnext就指向posNext。同样的posNext的prev指针指向pos但是我们要释放posprev指针就只想posPrev。最后再free掉pos位置的节点。总结来看就是当我们要free掉一个结点的时候就是我们要炒掉一个员工。为了不影响后续工作的进行我们要这个员工完成工作交接之后再炒掉他(工作交接就是安排好指针的对应关系)。代码如下voidLTErase(ListNode*pos){assert(pos);ListNode*posNextpos-next;ListNode*posPrevpos-prev;posPrev-nextposNext;posNext-prevposPrev;free(pos);posNULL;//这个pos是形参影响不了外面传的实参pos//所以再外面我们还要手动将pos指针置空}剩下的还由很多功能函数跟单链表雷同。此处我就不再一一列举。大家可以参考下一部分的代码汇总。三、代码汇总1. HDLoopLsit.h 头文件包含各种头文件引用以及函数的声明等等代码如下#pragmaonce#includestdio.h#includestdlib.h#includeassert.h//定义带头双向循环链表结构体typedefintLTDataType;typedefstructListNode{structListNode*next;structListNode*prev;LTDataType val;}ListNode;//链表初始化函数声明.ListNode*LTInit(ListNode*phead);//链表打印函数声明voidLTPrint(ListNode*phead);//尾插函数声明voidLTPushBack(ListNode*phead,LTDataType x);//尾删函数声明voidLTPopBack(ListNode*phead);//头插函数声明voidLTPushFront(ListNode*phead,LTDataType x);//头删函数声明voidLTPopFront(ListNode*phead);//链表查找函数声明ListNode*LTFind(ListNode*phead,LTDataType x);//链表在pos位置之前插入函数声明voidLTInsert(ListNode*pos,LTDataType x);//链表删除pos位置的节点函数声明voidLTErase(ListNode*pos);//链表毁灭函数声明voidLTDestroy(ListNode*phead);2. HDLoopLsit.c 源文件所有带头双向循环链表函数功能的实现#define_CRT_SECURE_NO_WARNINGS1#includeDLoopList.h//节点创建函数封装structListNode*CreateNode(LTDataType x){ListNode*newnode(structListNode*)malloc(sizeof(ListNode));if(newnodeNULL){perror(malloc fail);exit(-1);}//创建完节点后,对节点进行初始化newnode-valx;newnode-nextNULL;newnode-prevNULL;returnnewnode;}//链表初始化函数封装.ListNode*LTInit(ListNode*phead){pheadCreateNode(-1);phead-nextphead;phead-prevphead;returnphead;}//链表打印函数封装voidLTPrint(ListNode*phead){assert(phead);printf(哨兵位);ListNode*curphead-next;while(cur!phead){printf(%d,cur-val);curcur-next;//当时我漏写,怎么都检查不出来}printf(\n);}//尾插函数封装voidLTPushBack(structListNode*phead,LTDataType x){assert(phead);//因为链表有哨兵位,所以不可能为空, 要断言ListNode*tailphead-prev;//头结点的前置指针指向尾部节点ListNode*newnodeCreateNode(x);//创建节点tail-nextnewnode;newnode-prevtail;newnode-nextphead;phead-prevnewnode;//LTInsert(phead, x); //用定点插入函数实现尾插,定点在phead的前面插入.}//尾删函数封装voidLTPopBack(ListNode*phead){assert(phead);////如果链表为空,会删掉哨兵位,我们要防止这种情况,暴力检查//assert(phead-next!phead);//温柔检查//if (phead-next phead)//{// return;//}//ListNode* tail phead-prev;//ListNode* tailPrev tail-prev;////tailPrev-next phead;//phead-prev tailPrev;//free(tail);//tail NULL;//方法二: 头节点前面的节点就是尾节点,用定点删除实现尾删LTErase(phead-prev);}//头插函数封装voidLTPushFront(ListNode*phead,LTDataType x){assert(phead);ListNode*newnodeCreateNode(x);ListNode*curphead-next;phead-nextnewnode;newnode-prevphead;newnode-nextcur;cur-prevnewnode;////方法二: 不创建指针,直接头插,////要注意newnode先与后面节点的链接.//newnode-next phead-next;//phead-next-prev newnode;//phead-next newnode;//newnode-prev phead;}//头删函数封装voidLTPopFront(ListNode*phead){assert(phead);assert(phead-next!phead);//防止链表为空时删除哨兵位//ListNode* cur phead-next;//phead-next cur-next;//cur-next-prev phead;//free(cur);//cur NULL;//方法二: 定点删除头节点,实现头删LTErase(phead-next);}//链表查找函数封装ListNode*LTFind(ListNode*phead,LTDataType x){assert(phead);ListNode*curphead-next;while(cur!phead){if(cur-valx){returncur;}curcur-next;}returnNULL;}//链表在pos位置之前插入函数封装voidLTInsert(ListNode*pos,LTDataType x){assert(pos);//这里不用断言pos!phead, pos也可以是phead,//这样的话就是在phead的前面插入节点,等于尾插ListNode*newnodeCreateNode(x);ListNode*posPrevpos-prev;posPrev-nextnewnode;newnode-prevposPrev;newnode-nextpos;pos-prevnewnode;}//链表删除pos位置的节点函数封装voidLTErase(ListNode*pos){assert(pos);ListNode*posNextpos-next;ListNode*posPrevpos-prev;posPrev-nextposNext;posNext-prevposPrev;free(pos);posNULL;//这个pos影响不了外面传的实参pos}//链表毁灭函数封装ListNode*LTDestroy(ListNode*phead){assert(phead);ListNode*curphead-next;while(cur!phead){ListNode*nextcur-next;free(cur);curnext;}//循环结束后,就只剩下phead节点了free(phead);//phead NULL;//这句没有意义因为phead是plist的形参, 传值调用,//phead的改变不影响plist,//所以我们要在外面调用的时候手动把plist置空}3. HDLoopLsit_Test.c 源文件链表函数功能的测试这个老铁们可以自己随意测试。代码如下voidTest1(){//因为地址plist最后被修改了,所以要么传 plist,初始化函数LTInit用二级指针接受plist,传址调用,这样函数内形参做出的改变也会影响到实参//当然这样很麻烦,我们也可以就传值调用, 直接传plist,形参phead是实参的拷贝,不会影响实参,//但是我们可以让函数返回最终的地址, 由实参接受, 在函数外改变plistListNode*plistNULL;plistLTInit(plist);//尾插LTPushBack(plist,1);LTPushBack(plist,2);LTPushBack(plist,3);LTPrint(plist);//定点插入实现尾插LTInsert(plist,-1);LTPrint(plist);//头插LTPushFront(plist,7);LTPushFront(plist,8);LTPushFront(plist,9);LTPrint(plist);//尾删LTPopBack(plist);LTPopBack(plist);LTPopBack(plist);LTErase(plist-prev);LTPrint(plist);//头删LTPopFront(plist);LTPopFront(plist);LTPrint(plist);//定点删除,实现头删LTErase(plist-next);LTPrint(plist);LTDestroy(plist);plistNULL;}voidTest2(){ListNode*plistNULL;plistLTInit(plist);//尾插LTPushBack(plist,1);LTPushBack(plist,2);LTPushBack(plist,3);LTPrint(plist);//头插LTPushFront(plist,4);LTPushFront(plist,5);LTPushFront(plist,6);LTPrint(plist);//这里查找也意味着可以直接修改ListNode*posLTFind(plist,4);if(pos!NULL){printf(找到了在%p\n,pos);pos-val*10;}//定点插入LTInsert(pos,9);LTPrint(plist);//定点插入实现尾插LTInsert(plist,-1);LTPrint(plist);//查找和定点插入posLTFind(plist,6);LTInsert(pos,7);LTPrint(plist);posLTFind(plist,100);if(pos!NULL)printf(找到了在%p\n,pos);elseprintf(没找到\n);//LTInsert(pos, 100);//LTPrint(plist);}Test3(){ListNode*plistNULL;plistLTInit(plist);//尾插LTPushBack(plist,3);LTPushBack(plist,2);LTPushBack(plist,1);LTPrint(plist);//头插LTPushFront(plist,4);LTPushFront(plist,5);LTPushFront(plist,6);LTPrint(plist);//查找和定点删除ListNode*posLTFind(plist,4);LTErase(pos);LTPrint(plist);}intmain(){Test1();//Test2();//est3();return0;}四、总结我们可以发现就像小羊在单链表中说过的其他种类链表都是单链表的变种。无非就是改变了节点里的指针数量与指针指向。本质的思想还是不变的。只要大家明白了结构体指针函数传参动态内存函数这些基础的语法链表的实现就是他们的总结延伸也很快就会掌握。这个带头双向循环链表尾插尾删比单链表快一些。因为在只知道头节点地址的情况下单链表要遍历整个链表才能找到尾节点。时间复杂度是O(N).带头双向循环链表他的头节点的前一个节点就是尾节点不用遍历链表。时间复杂度是O(1).