图文并茂：彻底清晰带头双向循环链表（C语言版，附完整源码）

博主名称_Doubletful大家好欢迎来到Doubletful的博客博主的GitHub Go to git_hub数据结构专栏路漫漫其修远兮吾将上下而求索文章目录引言主要内容涵盖概念篇1.链表的分类1.1.带头链表1.2.双向链表1.3.循环链表2.超级拼装实现篇1.头文件内容总览2.创建新节点3.初始化链表4.头尾操作4.1.尾插数据4.2.头插数据4.3.尾删数据4.4.头删数据5.指定位置操作5.1.指定位置后插入5.1.1.指定位置后插入实现尾插5.1.2.指定位置后插入实现头插5.2.指定位置删除5.2.1.指定位置删除实现尾删5.2.2.指定位置删除实现头删6.查找6.1.使用值查找数据6.2.使用下标查找数据7.销毁链表8.一份测试代码总结篇1.双向循环链表的应用2.性能分析与对比引言☄️在链表家族中结构最简单的单链表存在着无法从后向前遍历找尾节点需要遍历整个链表找每个节点的前驱节点不方便在代码中每一个插入和删除操作都需判断链表是否为空容易发生空指针越界等问题如果从实际应用角度考虑单链表就像只能完成特定操作的工具想跨界使用它操作少不了代码上的各种弯弯绕绕即增多了码量又不方便。⚙️而我们在这篇博客中将实现链表家族中的“集大成者”带头双向循环链表。反直觉的是结构最复杂的它由于其完美的对称性代码实现反而最简单、最优雅。能向前后遍历找尾节点的时间复杂度为O(1)在指定位置插入无需遍历到指定位置前等等。主要内容涵盖从链表分类循序渐进到各自链表的逻辑结构阐明实现原理与各自操作接口的详解使用头文件声明、源文件定义的形式实现提供完整的测试代码和实际应用场景分析概念篇1.链表的分类在单链表博客中我们简要的提及过链表的种类为了更好的理解和实现带头双向循环链表再回顾一下。根据不同的需求实践应用中衍生出了多种不同的链表结构有单向和双向链表、带头结点和不带头结点的链表、循环和非循环的链表如下图所示将上述几种情况组合起来总共有8种不同链表结构但我们只需重点掌握带头单链表/不带头单链表以及带头双向循环链表即可因为考试和实践中出现的基本也是这三种结构并且这三种掌握以后其他组合结构也都涵盖其中。1.1.带头链表最简结构如下图所示概念“带头”指的是在链表的真正数据节点之前人为加入一个哨兵位节点。这个节点内部不存储任何有效数据它的唯一作用就是“站岗”。不带头痛点每次进行插入或删除操作时都必须小心翼翼地判断链表是否为空。更麻烦的是如果要在第一个位置插入或删除节点头指针 head 的指向必须被修改使你不得不使用二级指针这让代码变得复杂且容易出错。带头优势无论链表是否为空这个哨兵位节点永远存在这意味着头指针永远不会变成 NULL也永远不需要被修改插入和删除操作的逻辑被完全统一了传参时也只需要一级指针即可。1.2.双向链表最简结构如下图所示概念每个节点内部多了一个指针 prevnext 指向后继节点prev 指向前驱节点用空间换时间。单向痛点只能“一条路走到黑”。如果你当前在节点 C突然想操作它前面的节点 B抱歉时不逢机你只能从头指针重新遍历一遍链表来寻找 B。双向优势虽然每个节点多消耗了一个指针的内存但换来的是极大的自由度。无论你身处链表的哪个位置都可以瞬间找到前一个或后一个节点时间复杂度直接到 O(1)。1.3.循环链表最简结构如下图所示概念打破结尾的概念让尾节点的 next 指针不再指向 NULL而是绕回来指向链表的头节点。不循环痛点尾插数据必须从头节点开始顺藤摸瓜遍历整个链表直到找到那个 next 为 NULL 的尾节点才能进行插入每次尾插的时间成本都是 O(N)。循环优势一旦链表循环起来结合前面提到的“双向”属性头节点的 prev 指针直接指向尾节点这意味着获取尾节点不需要任何遍历直接 head-prev 就能拿到找尾节点的时间复杂度变成了 O(1)。2.超级拼装当我们把这三个最优解——带头免去判空与二级指针的烦恼、双向O(1) 寻找前后节点、循环O(1) 锁定尾节点结合在一起时就诞生了链表数据结构中的“究极完全体”概念至此如果还想看看单链表的完整概念和实现请移驾这篇《从线性表到单链表原理、实现与经典应用》实现篇实现部分会用到 malloc(), perror() 和 exit() C语言标准库函数简介如下assert()函数用于在程序运行时检查条件是否成立。若条件为假则输出错误信息并调用 abort() 终止程序若条件为真则无动作。perror()函数用于打印错误信息。调用格式perror(“前缀字符串”)输出格式为“前缀字符串错误原因\n”。exit()函数用于正常终止程序。刷新所有输出缓冲区、关闭已打开的流。将退出状态码返回给操作系统。1.头文件内容总览注代码部分如果直接复制不能成功运行请将所有中文前的#替换为//#pragmaonce#includestdio.h#includestdlib.h#includeassert.htypedefintLNDataType;#定义双向链表的节点结构typedefstructListNode{LNDataType data;/#存储值structListNode*next;#指向下一个节点的指针structListNode*prev;#指向前一个节点的指针}LN;#初始化链表 LN*LNInit();#添加尾插数据voidLNPushBack(LN*phead,LNDataType x);#添加头插数据voidLNPushFront(LN*phead,LNDataType x);#删除尾部数据voidLNPopBack(LN*phead);#删除头部数据voidLNPopFront(LN*phead);#添加指定位置后插入voidLNInsert(LN*pos,LNDataType x);#删除指定位置voidLNErase(LN*pos);#使用值查找数据 LN*LNFindByVal(LN*phead,LNDataType x);#使用下标查找数据 LN*LNFindByIdx(LN*phead,inti);#销毁链表voidLNDestroy(LN*phead);✨头文件是整个实现的核心骨架。这里我们通过 typedef int LNDataType; 将数据类型重命名这样做的好处是一劳永逸——以后如果链表需要存储 char 或 double 类型只需在这里修改一次即可。结构体 ListNode 中包含三个核心成员存储数据的 data、指向下一个节点的 next 指针、指向上一个节点的 prev 指针。有了这两个指针我们就具备了双向游走的能力后续的函数声明则涵盖了链表从生到死初始化到销毁的所有标准操作。2.创建新节点LN*LNBuyNode(LNDataType x){LN*newnode(LN*)malloc(sizeof(LN));if(newnodeNULL){perror(malloc fail);exit(1);}newnode-datax;newnode-nextNULL;newnode-prevNULL;returnnewnode;}✨无论是头插、尾插还是中间插入本质上都需要向内存申请一个新的节点因此将这个过程封装成一个独立的函数以提高代码复用率。注意操作唯一与实现单链表时创建新节点函数不同的是记得将新建节点内的指针 prev 也置空去掉 newnode-prev NULL; 这一行后完全相同。3.初始化链表LN*LNInit(){LN*pheadLNBuyNode(-1);phead-nextphead;phead-prevphead;returnphead;}✨带头链表的精髓就在于这个哨兵位节点——调用 LNBuyNode(-1) 申请一个哨兵位节点内部的值设为-1或其他无意义的值均可因为它不参与实际数据的存取。关键一步因为这是一个“循环”链表且目前链表为空所以我们将它的 next 和 prev 指针都指向自己就完美构建了一个闭环为后续的插入和删除消除了所有空指针的边界烦恼。4.头尾操作4.1.尾插数据voidLNPushBack(LN*phead,LNDataType x){assert(phead);LN*nodeLNBuyNode(x);#尾插 #新建节点的prev指向尾节点next指向头节点 node-prevphead-prev;node-nextphead;#尾节点的next指向新建节点头结点的prev指向新建节点 phead-prev-nextnode;phead-prevnode;}传入链表与要添加的元素断言传入指针不为 NULL创建新节点。✨对于单链表来说尾插需要遍历找尾时间复杂度是 O(N)但对于带头双向循环链表尾节点就是哨兵位的前驱节点 phead-prev。插入时的指针连接顺序非常讲究虽然双向链表通过辅助指针可以无视顺序但建议先连新节点再改老节点1.先让新节点 node 认亲它的 prev 指向原尾节点 phead-prevnext 指向哨兵位。2.再让老节点接纳新节点原尾节点的 next 指向 node哨兵位的 prev 指向 node。四个指针修改完毕形成闭环。4.2.头插数据voidLNPushFront(LN*phead,LNDataType x){assert(phead);LN*nodeLNBuyNode(x);#头插 #新建节点的prev指向头节点next指向首节点 node-prevphead;node-nextphead-next;#首节点的prev指向新建节点头结点的next指向新建节点 phead-next-prevnode;phead-nextnode;}传入链表与要添加的元素断言传入指针不为 NULL创建新节点。✨头插并不是要把数据插在哨兵位前面或者替换哨兵位而是插在哨兵位和第一个有效数据节点之间。新节点 node 的 prev 指向哨兵位next 指向原先的第一个有效节点 phead-next原先第一个有效节点的 prev 指向 node哨兵位的 next 指向 node注意图中的修改顺序该段代码也十分看重执行步骤。4.3.尾删数据voidLNPopBack(LN*phead){assert(pheadphead!phead-next);#尾删 LN*delphead-prev;#头结点的prev指向新尾节点新尾节点的next指向头节点 phead-prevphead-prev-prev;phead-prev-nextphead;free(del);}传入链表断言传入指针不为 NULL 且链表有非头节点。✨定位尾节点 del (phead-prev) 和新的尾节点 (del-prev)跨过要删除的节点让哨兵位的 prev 直接指向新的尾节点让新尾节点的 next 指向哨兵位最后释放节点 del 的内存。4.4.头删数据voidLNPopFront(LN*phead){#传入指针非空且链表有非头节点assert(pheadphead!phead-next);#头删 LN*delphead-next;#头结点的next指向新首节点新首节点的prev指向头节点 phead-nextphead-next-next;phead-next-prevphead;free(del);}传入链表断言传入指针不为 NULL 且链表有非头节点。✨锁定要删除的节点 del (phead-next)重新牵线搭桥将哨兵位的 next 指向 del 的下一个节点将 del 下一个节点的 prev 指向哨兵位最后释放节点 del 的内存。5.指定位置操作5.1.指定位置后插入voidLNInsert(LN*pos,LNDataType x){assert(pos);LN*nodeLNBuyNode(x);#指定位置后插入 #新建节点的prev指向指定节点next指向指定节点后的节点 node-prevpos;node-nextpos-next;#指定节点后的节点的prev指向新建节点指定节点的next指向新建节点 pos-next-prevnode;pos-nextnode;}传入指定位置与要添加的元素断言传入指针不为 NULL创建新节点。✨它的逻辑与头插十分类似让新节点 node 的前后指针分别连接 pos 和 pos-next然后再修改 pos-next 的前驱指针以及 pos 的后继指针指向 node。有了指定位置插入 LNInsert()我们的头尾插入能完全使用函数回调重写5.1.1.指定位置后插入实现尾插voidLNPushBack(LN*phead,LNDataType x){LNInsert(phead-prev,x);}尾插其实就是在尾节点之后插入而尾节点就是 phead-prev所以直接调用 LNInsert(phead-prev, x)。5.1.2.指定位置后插入实现头插voidLNPushFront(LN*phead,LNDataType x){LNInsert(phead,x);}头插其实就是在哨兵位之后插入所以直接调用 LNInsert(phead, x)。5.2.指定位置删除voidLNErase(LN*pos){#传入指针非空且链表有非头节点assert(pospos!pos-next);#指定位置删除 #指定节点前的节点的next指向指定节点后的节点 #指定节点后的节点的prev指向指定节点前的节点 pos-prev-nextpos-next;pos-next-prevpos-prev;free(pos);}传入指定位置断言传入指针不为 NULL 且链表有非头节点。✨将 pos 节点的前驱节点与后继节点直接相连pos-prev-next pos-next; 以及 pos-next-prev pos-prev;最后释放 pos 节点。同样的头尾删除也完全能使用 LNErase() 函数重写5.2.1.指定位置删除实现尾删voidLNPopBack(LN*phead){LNErase(phead-prev);}5.2.2.指定位置删除实现头删voidLNPopFront(LN*phead){LNErase(phead-next);}6.查找6.1.使用值查找数据LN*LNFindByVal(LN*phead,LNDataType x){assert(phead);#查找数据 LN*pcurphead-next;while(pcur!phead){if(pcur-datax){returnpcur;}pcurpcur-next;}returnNULL;}传入链表与要查找的元素断言传入指针不为 NULL。✨由于是循环链表遍历的结束条件不再是传统单链表的 pcur ! NULL真正的结束条件是指针重新转回了哨兵位即 pcur ! phead。在循环体内如果找到匹配的 data则直接返回该节点的指针如果循环结束还没找到则返回 NULL。6.2.使用下标查找数据LN*LNFindByIdx(LN*phead,inti){assert(pheadi0);#查找数据intj0;LN*pcurphead-next;while(pcur!pheadji){pcurpcur-next;j;}#当循环因pcurphead终止时下标i越界assert(ji);returnpcur;}传入链表与要查找的下标断言传入指针不为 NULL 且传入下标合法。✨通过定义一个计数器 j 从第 0 个有效节点开始向后偏移。双重循环条件 pcur ! phead j i 既防止了死循环又满足了计数需求。注意循环结束后通过 assert(j i) 来做越界检查——如果是因为走到了哨兵位导致循环终止说明给定的下标 i 大于了链表的实际长度程序会直接报错拦截这样就完美检查了传入下标的范围既不会是非法值也不会正向越界。7.销毁链表voidLNDestroy(LN*phead){assert(phead);LN*pcurphead-next;while(pcur!phead){LN*delpcur;pcurpcur-next;free(del);}#删除头节点free(pcur);}传入链表断言传入指针不为 NULL。✨pcur 从第一个有效节点开始遍历每次循环中先用 del 记录当前节点然后将 pcur 走向下一个节点最后再释放 del。当所有有效节点都被释放完毕后把最初始的哨兵位节点也释放掉。注意由于函数传的是一级指针调用者需要在函数外部手动将链表指针置空。8.一份测试代码voidTest_ListNode(){#初始化测试 LN*plistLNInit();#尾插测试LNPushBack(plist,1);LNPushBack(plist,2);LNPushBack(plist,3);#头插测试LNPushFront(plist,3);LNPushFront(plist,2);LNPushFront(plist,1);#尾删测试LNPopBack(plist);LNPopBack(plist);#头删测试LNPopFront(plist);LNPopFront(plist);#查找测试 LN*nodeLNFindByVal(plist,1);if(node!NULL){printf(%d\n,node-data);}nodeLNFindByIdx(plist,1);if(node!NULL){printf(%d\n,node-data);}#指定位置后插入测试LNInsert(plist,2);LNInsert(node,2);#指定位置删除测试LNErase(plist-next);LNErase(node);nodeNULL;#销毁测试LNDestroy(plist);plistNULL;}总结篇1.双向循环链表的应用多媒体播放器的“播放列表”我们在使用网易云音乐或 QQ 音乐时播放列表通常有“上一首”、“下一首”和“列表循环”功能。同时我们还可以随时向歌单中添加新歌或者移除不喜欢的歌。操作系统的时间片轮转调度在多任务操作系统如 Linux、Windows中CPU 需要在多个正在运行的进程之间快速切换。系统会给每个进程分配一个短暂的“时间片”时间片用完就切换到下一个进程。图形界面的“AltTab”窗口切换与轮播图在 Windows 系统中按下 AltTab 切换多任务窗口或者在网页端/App端看到的首屏无缝轮播图。2.性能分析与对比操作场景单链表带头双向循环链表性能差异原因分析头插 (PushFront)O(1)O(1)两者都能直接操作头部节点。头删 (PopFront)O(1)O(1)两者都能直接断开头部首节点。尾插 (PushBack)O(N)O(1)单链表需从头遍历找尾节点双向循环可通过 phead-prev 秒锁尾节点。尾删 (PopBack)O(N)O(1)单链表需遍历寻找尾节点的前驱双向循环可通过 phead-prev-prev 直接拿到。在 pos 节点前插入O(N)O(1)单链表需从头遍历寻找 pos 的前驱节点双向链表通过 pos-prev 即可直接获取。在 pos 节点后插入O(1)O(1)两者都能直接通过 pos-next 操作。删除 pos 节点O(N)O(1)单链表必须从头遍历找到 pos 的前驱节点才能缝合双向链表自带 prev直接缝合前后节点。查找数据 (Find)O(N)O(N)链表本质上不支持随机访问无论哪种结构寻找特定值都必须遍历。节点空间开销较小较大普通单链表只需 1 个指针双向链表需 2 个指针多出 prev 消耗内存。“复杂”的底层结构往往是为了支撑“简单”的上层调用。正是因为有了带头双向循环链表这种优雅的数据结构才有了我们今天顺滑的操作系统调度、无缝的音乐播放体验。希望通过这篇文章你能体会到这种“用空间换时间、用结构换逻辑”的编程美学。⚛️EL PSY CONGROO十分感谢你的阅读过往博客《从线性表到单链表原理、实现与经典应用》已优化排版本期不确定如何不冲突的实现OpenCode和CodeX的博客编写