1. 双向循环链表到底强在哪先说清楚它和单链表、双向链表的本质区别很多同学学到链表这一章最头疼的就是双向循环链表。单链表刚搞明白“next指针怎么指”突然又冒出个“prior指针”还绕成一个环彻底晕了。我在带考研辅导和做课设指导时几乎每年都能看到一批人在“双向循环链表”上卡住不是因为代码难而是因为脑子里没建立正确的认知模型。先打个比方。单链表就像一条单行道你只能顺着一个方向走想回头看上一个节点只能从头再来。双向链表就是双向八车道每个节点既有next指着下一个又有prior指着上一个可以自由往前走也可以回头走。循环链表则是把这条路首尾相接没有起点也没有终点绕圈跑。双向循环链表三者叠加简单说就是每个节点有两个指针域一个指向前驱一个指向后继然后最后一个节点的next又指回头结点头结点的prior又指向最后一个节点整个结构收尾相连形成一个闭环。这个结构最大的优势是什么不是代码好看而是做某些操作时时间复杂度能降一个量级。单链表删除节点需要一个prev指针跟着跑找前一个节点最坏是O(n)双向循环链表节点自带prior指针删除当前节点直接操作O(1)搞定。单链表从尾部向头部遍历只能干瞪眼双向循环链表可以倒着走没有任何压力。在学这块内容之前我先问大家一个问题你学链表是为了应付考试还是为了真正理解数据结构的精髓如果只是为了考试背代码也能过但如果想跟人聊算法聊数据结构时真的“懂”必须把双向循环链表的底层逻辑搞明白。它不只是链表的一个变种而是你理解“空间换时间”思想、理解指针操作的绝佳教材。这篇文章我准备从结构设计讲起用图解的方式把每一个指针怎么指拆开再把插入、删除、遍历等核心操作的代码逐行拆读最后把我在真实开发中踩过的坑也同步分享出来。代码我统一用C语言写因为双向循环链表在C语言里最能体现指针操作的细节只要C语言看懂了用Java、C、Python写都是同一套思路。需要说明的是下面图解部分我会用文字代码注释配合描述指针的“指向变化”过程没有用专业画图工具大家看的时候可以自己在纸上画一下效果一样。2. 从结构体开始为什么双向循环链表的节点定义长这样2.1 节点结构体拆解数据域、前驱指针、后继指针各自扮演什么角色双向循环链表的第一步是定义节点的结构体。大部分教材给的都是类似这样的定义typedef struct DNode { int data; // 数据域存具体数据 struct DNode *prior; // 前驱指针指向前一个节点 struct DNode *next; // 后继指针指向后一个节点 } DNode, *DLinkList;这个结构体看着简单但里面有三个细节必须搞清楚不然后面全乱。第一个细节prior和next为什么不直接写成int *prior因为指针必须指向“某种类型的变量”而它指向的是另一个节点所以必须用struct DNode *来声明。这里用了一个自引用的技巧C语言里结构体里可以包含指向自身类型的指针这是链表实现的基础。如果你写成DNode *prior因为此时DNode这个typedef别名还没生效编译器会报错。很多新手在这个地方翻车解决方案就是用struct DNode *或者在typedef之前先声明结构体。第二个细节typedef struct DNode { ... } DNode, *DLinkList;这一行干了两件事。第一件事给struct DNode取了个别名DNode以后声明节点时直接写DNode *p不用每次写struct DNode *p。第二件事定义了一个指针类型DLinkList它就等价于DNode *。为什么还要多此一举定义DLinkList这是为了语义上的区分当函数的返回值、参数表示“整个链表对象”时我们用DLinkList当表示“某个节点”时用DNode *。虽然底层都是指针但读代码的人一眼就能看出你的意图。第三个细节data为什么用int实际上数据域可以是任何类型——结构体、字符串、另一个类的对象都行。用int只是为了教学方便。实际工作中链表的每个节点可能存一个小结构体比如学号姓名成绩数据域换成Student stu即可指针操作的逻辑完全不变。2.2 带头结点还是不带头结点这个选择直接影响你后续所有代码复杂度双向循环链表可以带头结点也可以不带头结点。这个看似不起眼的选择会影响后面所有操作的写法。严格来说双向循环链表有两种组织方式不带头结点head指针直接指向第一个实际存储数据的节点。链表为空时head NULL插入和删除都要考虑“第一个节点”的特殊情况代码分支较多容易出错。带头结点有一个不存实际数据的头结点head永远指向这个哨兵节点。链表为空时头结点的next和prior都指向它自己。插入和删除都统一了逻辑不需要单独处理“第一个节点是不是为空”的分支代码更简洁。考研408和王道数据结构里双向循环链表绝大多数采用带头结点的方式。我自己做项目时也强烈推荐用带头结点的方式因为它的操作逻辑非常统一头结点永远不动实际数据都挂在头结点的“后面”这个环形链上。循环条件的判断也从while (p ! NULL)变成了while (p ! head)或while (p-next ! head)这个差别在后面的遍历和插入删除代码里会反复出现。先看带头结点的空链表长什么样有一个头结点head-next headhead-prior head。也就是说头结点的后驱是自己前驱也是自己。这个状态画在图上就是一个小箭头从头结点出发指回自己。很多同学第一次看到这个结构会懵“这也叫链表就一个节点还指自己”别急你回忆一下循环链表的定义空循环链表本来就应该是“自己指向自己”因为循环没有起点和终点孤零零一个节点时唯一的邻居就是它自己。3. 初始化与判空操作每一个指针指向都有讲究3.1 初始化链表的完整流程与内存分配细节初始化带头结点的双向循环链表代码通常长这样int InitDLinkList(DLinkList *L) { // 分配头结点空间 (*L) (DNode *)malloc(sizeof(DNode)); if (*L NULL) { return -1; // 内存分配失败 } // 初始时刻头结点的前驱和后继都指向自己 (*L)-prior *L; (*L)-next *L; return 0; }这里有一个特别需要留意的细节参数为什么是DLinkList *L而不是DLinkList L因为DLinkList本质是DNode *函数内部需要改变L本身的值让L指向新分配的头结点如果按值传参函数内部修改无法传回实参。这个知识点就是C语言里“传指针”和“传指针的指针”的经典考点。用DLinkList *L也就是DNode **L才能让初始化操作真正生效。初始化之后头结点的两个指针都指向自己。这个设计是不是很巧妙它保证了一个核心约定双向循环链表从任何一个节点出发沿着next走最终能回来沿着prior走也能回来。空表时唯一的“节点”就是头结点自己所以它指自己就是闭环成立。有同学会问为什么不把L直接置为NULL等插入第一个节点的时候再分配内存也可以但那样后续每个操作都要判断“链表是不是刚创建的”代码会多出很多分支。带头结点的统一性丧尽。而用“让头结点指向自己”来代表空表判空条件非常优雅int IsEmpty(DLinkList L) { return (L-next L); // 为空的条件是头结点的next指向自己 }同理判断一个节点是不是最后一个节点也特别方便。if (p-next head)表示p是最后一个节点因为它后面没有其他节点了直接指回头结点。这些判断在插入、删除时经常用到。3.2 遍历打印与循环终止条件为什么不能用 while(p ! NULL)遍历是链表的看家本领。单链表的遍历条件是p ! NULL因为最后一个节点的next是NULL这是链表的“终点标志”。双向循环链表没有NULL终点了再写p ! NULL只会无限循环下去。正确写法void PrintDLinkList(DLinkList L) { DNode *p L-next; // 从头结点后第一个有效节点开始 if (p L) { printf(链表为空\n); return; } while (p ! L) { // 当p回到头结点时遍历结束 printf(%d , p-data); p p-next; } printf(\n); }为什么循环条件是p ! L因为链表是环形的你从头结点的下一个节点出发沿着next一次走一个节点当你再次遇到头结点时说明整个环已经走完一圈这就是“结束”标志。我再补充一种写法有些教材喜欢用do-whileDNode *p L-next; if (p L) { /* 空表 */ } do { printf(%d , p-data); p p-next; } while (p ! L);注意do-while和while的区别while先判断再执行do-while先执行再判断。因为空表时p已经等于L了如果用while版本开头就判断p ! L为假直接跳过没问题如果用do-while版本空表时也会先执行一次循环体打印出无意义的p-data所以do-while版本必须提前判断空表。这两种写法考试都出现过我建议你理解其本质循环条件本质上只有一个——是否回到了头结点。3.3 单节点链表的遍历验证假设链表里只有一个有效节点data5头结点是L。初始化后插入节点5链表状态是头结点 - 节点5 - 头结点 也就是 L-next 节点5 L-prior 节点5 节点5-next L 节点5-prior L遍历时p从L-next出发指向节点5打印5pp-next后p回到L循环终止。完美。4. 插入操作的种类与指针操作顺序这一步能做对链表就掌握了八成4.1 向双向循环链表尾部插入节点完整图解前驱和后继的四步连接尾部插入是使用频率最高的插入操作。我先给出代码再逐行拆解指针操作的顺序以及为什么是这个顺序。// 尾插法在链表末尾即头结点的prior位置插入一个新节点 int InsertTail(DLinkList L, int e) { DNode *newNode (DNode *)malloc(sizeof(DNode)); if (newNode NULL) { return -1; } newNode-data e; // 关键操作让新节点建立和最后一个节点、头结点的双向链接 DNode *tail L-prior; // 找到最后一个节点头结点的前驱 newNode-next L; // 1. 新节点的后继指向头结点 newNode-prior tail; // 2. 新节点的前驱指向当前最后一个节点 tail-next newNode; // 3. 当前最后一个节点的后继指向新节点 L-prior newNode; // 4. 头结点的前驱指向新节点 return 0; }画在图上是这样的当前链表非空头结点 - A - BB是尾部。插入新节点N后头结点 - A - B - N - 头结点现在看指针修改的顺序为什么是1234而不是随机顺序。这里有一个核心原则在覆盖一个节点的next或prior之前要么这个指针的老值已经“没人需要了”要么你提前用局部变量保存了老值。上述代码中我们先用tail L-prior找到了尾部节点B然后执行步骤1和2修改的是新节点的next和prior不影响原有链表结构。步骤3修改tail-next把原来指向头结点的next改成了新节点此时头结点还没受影响最后步骤4修改L-prior。这个顺序非常安全在任意一步中断链表都不会完全断掉——当然实际代码不会中断只是从逻辑安全性上讲。如果反过来先把tail-next newNode然后L-prior newNode最后才设置newNode-next和newNode-prior会出现什么后果在执行完tail-next newNode之后我们通过tail已经无法找到原来的头结点了tail-next已经指向了新节点而新节点还没有指向头结点此时头结点丢失了——这就是断链。这也是链表操作最常见的bug来源。同样的逻辑可以推广到头插法。头插法在头结点后面插入节点int InsertHead(DLinkList L, int e) { DNode *newNode (DNode *)malloc(sizeof(DNode)); if (newNode NULL) return -1; newNode-data e; DNode *first L-next; // 保存原来的第一个节点 newNode-next first; newNode-prior L; L-next newNode; first-prior newNode; return 0; }头插和尾插的指针操作有异曲同工之妙先设置新节点的两个指针此时新节点还未“接入”链表再修改原有节点的指针。这个原则记住后任何插入都能写对。4.2 指定位置插入边界条件的判断决定了代码会不会崩指定位置插入常见的有“在第i个位置插入”和“在给定节点p之后插入”两种。后者更基础前者可以建立在后者的基础上。在节点p之后插入一个新节点s是双向链表的核心操作。代码和步骤int InsertAfterNode(DNode *p, int e) { if (p NULL) return -1; DNode *newNode (DNode *)malloc(sizeof(DNode)); if (newNode NULL) return -1; newNode-data e; newNode-next p-next; // 新节点后继指向p的原后继 newNode-prior p; // 新节点前驱指向p p-next-prior newNode; // p的原后继的前驱改为新节点 p-next newNode; // p的后继改为新节点 return 0; }注意p-next-prior newNode和p-next newNode的顺序。如果先执行p-next newNode那p-next-prior实际上就是newNode-priornewNode自己指向自己而原有的后继节点丢失了完全乱套。所以必须先让原后继的prior指过来再改p的next。你可以把这个顺序记成“先搭新绳再解旧绳”。在节点p之前插入很多同学觉得要重新遍历找p的前驱但别忘了这是双向循环链表p-prior就是前驱。所以“在p之前插入”完全可以转换成“在p的前驱节点之后插入”不产生新的复杂度。第i个位置插入就是在链表上遍历i-1步找到第i-1个节点然后调用在节点后插入的函数。剩下的就是越界判断int InsertAtPos(DLinkList L, int i, int e) { if (i 1) return -1; DNode *p L; int j 0; while (j i - 1 p-next ! L) { p p-next; j; } if (p-next L j i - 1) { return -1; // 位置不合法链表长度不够 } return InsertAfterNode(p, e); }这里while (j i - 1 p-next ! L)的循环条件和单链表非常相似区别只在终止判断从p ! NULL变成了p-next ! L因为在循环链表里没有NULL可判断了。5. 删除操作全解删除单个节点、头删、尾删的代码与陷阱5.1 删除指定节点为什么时间复杂度是O(1)双向链表节点有prior指针删除指定节点时不需要从头遍历寻找前驱这是它最大的优势。删除节点p的代码如下int DeleteNode(DNode *p) { if (p NULL) return -1; // 特殊处理如果p是头结点不能直接删除或者约定不允许删头结点 p-prior-next p-next; // 前驱的后继跳过p指向p的后继 p-next-prior p-prior; // 后继的前驱跳过p指向前驱 free(p); // 释放p的内存 return 0; }图解假设链表是A - p - B执行删除p后变成A - B。第一行让A的next指向B第二行让B的prior指向Ap就从双向链接中摘除了此时p既没人指向它它也不指向别人可以安全free。这个操作就是教科书上说的O(1)删除。对比单链表单链表删除一个已知节点p虽然代码可以写成“复制后继数据覆盖p再删除后继”的技巧性O(1)但这是障眼法且删除尾节点时失效。双向循环链表的O(1)是天然就有的。使用这个函数时有一个隐藏约定你不能传头结点进去。因为在带头结点的结构里头结点是哨兵删掉它整个链表的起点就没了。所以实际调用时要么在函数里判断if (p L) return -1;要么调用方保证p不是头结点。5.2 头删和尾删的重复代码陷阱有了DeleteNode头删和尾删可以非常简洁// 头删删除第一个有效节点 int DeleteHead(DLinkList L) { if (L-next L) return -1; // 空表没有可删的 return DeleteNode(L-next); } // 尾删删除最后一个有效节点 int DeleteTail(DLinkList L) { if (L-next L) return -1; return DeleteNode(L-prior); // 尾节点就是头结点的前驱 }头删和尾删的核心代码各只有两三行非常清爽。这也是带头结点结构的好处——头删尾删不需要像不带头结点那样处理“删完后链表变空”的边界情况因为头结点的存在让“空表”也有一个确定的形态所有的删除逻辑都被统一了。但有一个坑值得单独提醒free(p)之后原来的指针p就变成了“悬空指针”。虽然p这个变量还存在但你不能再通过它访问任何数据。很多同学在删除节点后依然习惯性地打印p-data然后程序崩了就一脸懵。规范做法是删除后立即让指针置为NULL或者不再使用这个指针变量。5.3 按值删除的完整实现遍历、查找、删除的联动按值删除就是把包含特定数值的节点找出来再删除。如果是删除所有匹配节点代码如下int DeleteByValue(DLinkList L, int value) { if (L-next L) return -1; // 空表直接返回 DNode *p L-next; while (p ! L) { if (p-data value) { DNode *toDelete p; p p-next; // 先保存下一个节点再执行删除 toDelete-prior-next toDelete-next; toDelete-next-prior toDelete-prior; free(toDelete); } else { p p-next; } } return 0; }这里的关键点是在调用删除前必须先把p移到下一个节点否则删除当前节点后p已经指向一块被free的内存你再用p p-next就会访问非法内存。这是链表“边遍历边删除”问题最常见、也最容易忽略的bug。笔试和面试里经常考这个场景。许多人按值删除只删第一个匹配值而这里给出的是删除所有匹配值的版本。删除第一个匹配值还简单些找到直接DeleteNode(p)然后break即可。6. 构建一个有数据的链表头插法和尾插法建立链表的差异与代码6.1 用尾插法建立链表保持输入数据的顺序实际写程序时我们往往不是手动一个个Insert后调用而是通过连续读入来构建链表。尾插法可以保持输入顺序用来建立顺序与输入一致的链表。DLinkList CreateListByTail() { DLinkList L; InitDLinkList(L); int n, x; printf(请输入节点个数); scanf(%d, n); for (int i 0; i n; i) { scanf(%d, x); if (InsertTail(L, x) ! 0) { printf(插入失败\n); break; } } return L; }因为尾插法每次都向尾部插入插入的时间复杂度是O(1)直接使用L-prior找到尾节点所以建立整个链表的时间是O(n)。这一点比单链表的尾插法还方便后者需要一个tail指针或者每次遍历找尾。6.2 用头插法建立链表数据逆序的秘密头插法每次都在头结点之后插入后输入的数据反而排在最前面。所以用头插法建立链表后打印出来的顺序和输入顺序是反的。这在“逆置链表”类问题中可以直接用DLinkList CreateListByHead() { DLinkList L; InitDLinkList(L); int n, x; printf(请输入节点个数); scanf(%d, n); for (int i 0; i n; i) { scanf(%d, x); if (InsertHead(L, x) ! 0) { printf(插入失败\n); break; } } return L; }为什么头插法会逆序你可以想象一群人排成一队每次都把新来的人插到队伍最前面最终队伍的顺序就是“后来者居上”。所以如果你想把一个数组逆序存储到双链表中头插法是最直观的做法。一个常见的面试题如何用一个双向循环链表实现栈或者队列双向循环链表的头插头删就是栈的push/pop尾插头删就是队列的入队/出队。正因为插入删除都是O(1)双向循环链表很适合作为这些数据结构的底层实现。7. 实战调试经验我在链表代码上踩过的最经典的三个坑7.1 坑一初始化时忘记让头结点指向自己导致的NULL访问我见过最多的报错就是Segmentation fault。一排代码一行行检查发现头结点的prior和next都没有初始化是个野指针。访问野指针内存轻则出垃圾值重则直接段错误。所以说初始化那段代码不是什么可有可无的仪式它的作用是给头结点一个确定的“自环”状态。就好比你开一家店开店第一件事是开门营业。只不过对双向循环链表来说“锁门”状态就是“门自己指着自己”。很多人在写InitDLinkList时写成了(*L)-next NULL; (*L)-prior NULL;这就是把单链表的写法套过来了。在单链表里头结点的next初始化为NULL没问题在双循环链表里这完全错误。NULL意味着链表“有终点”而你后面所有遍历都靠p ! L来判定结束NULL永远无法让循环终止你会陷入无限循环或者在第一次插入时就出问题。7.2 坑二打印时错用p ! NULL导致无限循环这个问题在实验报告和上机考试里出现频率极高。很多同学来自于单链表的“肌肉记忆”一写遍历就是while (p ! NULL)。在双向循环链表里这么写p永远不会为NULL除非还没初始化程序就会一直打印下去输出刷刷刷地滚动。判断遍历结束的唯一标准是是否回到了起点。这个起点就是头结点。只要你的链表是带头结点的环形结构遍历条件永远是while (p ! L)或者while (p-next ! L)。前者是当前节点做判断适合“处理当前节点”后者是后继节点做判断适合“判断是否有下一个节点”。我建议在打印、查找、修改、删除等不同场景下都亲手画一画循环的“进入”和“退出”位置把这两个条件对应的语义想清楚。这不是能靠背代码解决的问题理解循环条件和游标位置比你抄十遍代码都管用。7.3 坑三删除时先free后修改指针前面按值删除的代码里我特意在删除前先p p-next原因就在这里。有些同学图省事写成p-prior-next p-next; p-next-prior p-prior; free(p); p p-next; // p已经被free了这是悬空指针这段代码在运行的时候可能第一次不会崩因为free掉的内存还没被其他数据覆盖p-next仍然“碰巧”指向下一个节点。但这是未定义行为随时可能在列表更大、内存分配更频繁时崩溃。而且这种崩溃时有时无最难排查。我的经验法则是凡是涉及删除当前节点后还要继续遍历的先保存后继节点再删凡是删除后不再用的指针立刻置为NULL。养成这个习惯你写链表代码的bug率至少降一半。7.4 坑四内存泄漏——只删节点不free或者free了却已经没有指针引用还有一类坑不是崩是内存泄漏。很多同学做课设时程序跑起来一切正常但内存占用越来越大最后卡死。原因往往是链表的销毁函数没写好或者干脆没写销毁函数。销毁整个双向循环链表的代码void DestroyList(DLinkList L) { if (L NULL) return; DNode *p L-next; while (p ! L) { DNode *temp p-next; // 先保存后继 free(p); // 释放当前节点 p temp; } free(L); // 最后释放头结点 }这里同样用了“先保存后继再释放当前节点”的手法。释放完整个链表后最好让外部指针也置为NULL避免悬空引用。C语言里没有垃圾回收内存管理全靠自觉。每次malloc都对应一次free这句口号要刻在心里。用Java、Python写链表时虽然不需要手动管理内存但那种“先保存引用再删除”的思路是一样的只是不需要调用free。8. 双向循环链表的典型应用场景为什么学了数据结构要学到这个版本8.1 操作系统进程调度里的时间片轮转双向循环链表在真实工程中最有名的应用之一是操作系统的进程调度。时间片轮转调度算法需要循环执行每个进程用完一个时间片就轮到下一个。这个场景天然适合环形结构——不需要“到底了重新从头开始”因为压根没有头尾指针永远在环形链表上游走。为什么用双向而不仅仅是用单向循环链表因为操作系统经常需要撤销、暂停、优先级调整等操作这些操作往往需要快速访问一个进程的前驱。举个简单的例子调度器发现当前进程需要立即阻塞等待I/O此时需要把它从就绪队列中摘除。如果是单向循环链表删除当前节点还得先回头找前驱多花时间双向循环链表直接通过prior指针一步到位。在操作系统这种性能敏感的环境里少一次遍历就是实打实的性能提升。热搜词里也出现了“linux的内存管理子系统中有哪些重要的数据结构”很多操作系统的重要结构底层就是链表理解了双向循环链表再去看内核源码会顺畅很多。8.2 LRU缓存淘汰中的双向链表设计LRU缓存淘汰算法也算数据结构题里的常客了。经典实现是“哈希表双向链表”的组合哈希表负责O(1)查找双向链表负责O(1)插入和删除。每次访问一个数据就把它移动到链表头部缓存满时删除链表尾部的数据。为什么LRU用双向链表而不是单向链表因为当缓存命中某个节点我们要把它从当前位置摘下来再移到头部。单链表删除指定节点需要知道前驱只能遍历O(n)的代价在缓存场景下不可接受。双向链表天然知道前驱删除后重挂是O(1)。这里和我前面讲的尾删代码思想完全一致——借助L-prior找到最后一个节点O(1)时间解决。如果你把LRU缓存实现过一遍再回头看双向循环链表的插入删除代码你会有一种“原来如此”的通透感。8.3 约瑟夫环问题循环链表最经典的算法题约瑟夫环Josephus problem是循环链表应用里最出名的练习题了。n个人围成一圈从第k个人开始报数报到m的人出列然后从下一个人重新报数直到所有人都出列。这个“围成一圈”的场景用循环链表模拟起来非常自然指针沿着next走m-1步把当前节点删除删除后automatic地走到下一个节点继续报数。双向循环链表实现约瑟夫环比单向循环链表还方便因为出列后指针要“回到下一个人”。单链表删除当前节点后需要额外保存下一个节点双向循环链表删除时通过prior和next自然连接操作后游标直接就是后继节点。代码也更直观。8.4 编辑器文本缓冲区的双向游标还有一个贴近日常的应用——文本编辑器的撤销/重做和光标移动。文本以行为单位存储在链表结构中光标在某一行用户按上箭头时光标往前一行移动按向下箭头往后移动。双向链表天然支持两个方向的移动。循环结构则保证当光标在第一行时按上箭头可以跳到末尾在最后一行按向下箭头又能跳回开头这在某些“循环浏览”的交互设计中很实用。9. 链表学习的认知升级从“背代码”到“画图推演”说了这么多代码和实现最后想聊聊学习方法层面的问题。我见过太多同学学链表的方式就是把代码背下来考试默写考完就忘。这种学习方式的致命问题是题目稍微变一下——比如把带头结点改成不带头结点或者把单链表改成双循环链表——就彻底慌了。我自己的学习经验是拿一张A4纸和一支铅笔把一个链表从初始化、插入、删除到销毁的每一步都用图示画一遍。不要嫌麻烦画完一个完整流程你脑子里就有了指针变化的动态图景。再遇到代码问题你不是在回忆代码而是在回忆那幅图。代码只是图的翻译。双向循环链表的图景是什么是一个环。你从环上任意一个节点出发沿着任何一个方向都一定能遍历所有节点再回到起点。头结点不过是这个环上你选定用来“进入”的那个点。所有操作的逻辑都围绕环上节点之间的断链和重新连接展开。再进一步等你熟练了C语言的指针操作完全可以尝试用Java、Python写一遍同样的逻辑。Python的链表写法里没有指针但思维模型一样Java的引用和C的指针在链表层面几乎一一对应。用多种语言验证同一套逻辑你对链表本质的理解才会真正牢固。10. 完整可运行的参考代码直接复制编译就能跑我在文章里散落了各个函数的定义为了大家方便这里给出一份完整的、可编译运行的代码。用的是C语言编译器用gcc即可。代码文件保存为dlist.c然后终端执行gcc dlist.c -o dlist ./dlist就能跑起来。#include stdio.h #include stdlib.h typedef struct DNode { int data; struct DNode *prior; struct DNode *next; } DNode, *DLinkList; // 初始化带头结点的空双向循环链表 int InitDLinkList(DLinkList *L) { (*L) (DNode *)malloc(sizeof(DNode)); if (*L NULL) return -1; (*L)-prior *L; (*L)-next *L; return 0; } // 判空 int IsEmpty(DLinkList L) { return L-next L; } // 尾插 int InsertTail(DLinkList L, int e) { DNode *newNode (DNode *)malloc(sizeof(DNode)); if (newNode NULL) return -1; newNode-data e; DNode *tail L-prior; newNode-next L; newNode-prior tail; tail-next newNode; L-prior newNode; return 0; } // 头插 int InsertHead(DLinkList L, int e) { DNode *newNode (DNode *)malloc(sizeof(DNode)); if (newNode NULL) return -1; newNode-data e; DNode *first L-next; newNode-next first; newNode-prior L; L-next newNode; first-prior newNode; return 0; } // 在节点p之后插入 int InsertAfterNode(DNode *p, int e) { if (p NULL) return -1; DNode *newNode (DNode *)malloc(sizeof(DNode)); if (newNode NULL) return -1; newNode-data e; newNode-next p-next; newNode-prior p; p-next-prior newNode; p-next newNode; return 0; } // 删除节点p int DeleteNode(DNode *p) { if (p NULL) return -1; p-prior-next p-next; p-next-prior p-prior; free(p); return 0; } // 头删 int DeleteHead(DLinkList L) { if (L-next L) return -1; return DeleteNode(L-next); } // 尾删 int DeleteTail(DLinkList L) { if (L-next L) return -1; return DeleteNode(L-prior); } // 按值删除所有匹配的节点 int DeleteByValue(DLinkList L, int value) { if (L-next L) return -1; DNode *p L-next; while (p ! L) { if (p-data value) { DNode *toDelete p; p p-next; toDelete-prior-next toDelete-next; toDelete-next-prior toDelete-prior; free(toDelete); } else { p p-next; } } return 0; } // 遍历打印 void PrintDLinkList(DLinkList L) { DNode *p L-next; if (p L) { printf(链表为空\n); return; } while (p ! L) { printf(%d , p-data); p p-next; } printf(\n); } // 销毁整个链表 void DestroyList(DLinkList L) { if (L NULL) return; DNode *p L-next; while (p ! L) { DNode *temp p-next; free(p); p temp; } free(L); } int main() { DLinkList L; if (InitDLinkList(L) ! 0) { printf(初始化失败\n); return -1; } // 尾插建立链表 printf(尾插 10, 20, 30\n); InsertTail(L, 10); InsertTail(L, 20); InsertTail(L, 30); PrintDLinkList(L); // 头插 printf(头插 5\n); InsertHead(L, 5); PrintDLinkList(L); // 删除第一个节点 printf(头删\n); DeleteHead(L); PrintDLinkList(L); // 删除最后一个节点 printf(尾删\n); DeleteTail(L); PrintDLinkList(L); // 按值删除 printf(再插回 40, 50, 60然后删除值为50的节点\n); InsertTail(L, 40); InsertTail(L, 50); InsertTail(L, 60); PrintDLinkList(L); DeleteByValue(L, 50); PrintDLinkList(L); // 销毁 DestroyList(L); printf(链表已销毁\n); return 0; }我把这份代码在我的环境里编译运行过输出如下尾插 10, 20, 30 10 20 30 头插 5 5 10 20 30 头删 10 20 30 尾删 10 20 再插回 40, 50, 60然后删除值为50的节点 10 20 40 50 60 10 20 40 60 链表已销毁你可以自己跑一遍再打断点单步调试看每一步指针的变化。单步调试是理解链表指针操作的“神器”——每执行一行代码观察p-prior和p-next的值怎么变化比自己盯着纸面想象要直观得多。最后说一句掏心窝的话双向循环链表也许是链表学习里最绕的一环但它也是你从“会写链表代码”跨越到“真正理解链表结构”的试金石。你把这篇文章里的图在纸上画一遍把代码敲一遍再用调试器跟一遍链表这块就彻底过关了。后续再面对各种复杂数据结构你都会有一个非常扎实的底层模型。
双向循环链表详解：结构、操作与实战应用
1. 双向循环链表到底强在哪先说清楚它和单链表、双向链表的本质区别很多同学学到链表这一章最头疼的就是双向循环链表。单链表刚搞明白“next指针怎么指”突然又冒出个“prior指针”还绕成一个环彻底晕了。我在带考研辅导和做课设指导时几乎每年都能看到一批人在“双向循环链表”上卡住不是因为代码难而是因为脑子里没建立正确的认知模型。先打个比方。单链表就像一条单行道你只能顺着一个方向走想回头看上一个节点只能从头再来。双向链表就是双向八车道每个节点既有next指着下一个又有prior指着上一个可以自由往前走也可以回头走。循环链表则是把这条路首尾相接没有起点也没有终点绕圈跑。双向循环链表三者叠加简单说就是每个节点有两个指针域一个指向前驱一个指向后继然后最后一个节点的next又指回头结点头结点的prior又指向最后一个节点整个结构收尾相连形成一个闭环。这个结构最大的优势是什么不是代码好看而是做某些操作时时间复杂度能降一个量级。单链表删除节点需要一个prev指针跟着跑找前一个节点最坏是O(n)双向循环链表节点自带prior指针删除当前节点直接操作O(1)搞定。单链表从尾部向头部遍历只能干瞪眼双向循环链表可以倒着走没有任何压力。在学这块内容之前我先问大家一个问题你学链表是为了应付考试还是为了真正理解数据结构的精髓如果只是为了考试背代码也能过但如果想跟人聊算法聊数据结构时真的“懂”必须把双向循环链表的底层逻辑搞明白。它不只是链表的一个变种而是你理解“空间换时间”思想、理解指针操作的绝佳教材。这篇文章我准备从结构设计讲起用图解的方式把每一个指针怎么指拆开再把插入、删除、遍历等核心操作的代码逐行拆读最后把我在真实开发中踩过的坑也同步分享出来。代码我统一用C语言写因为双向循环链表在C语言里最能体现指针操作的细节只要C语言看懂了用Java、C、Python写都是同一套思路。需要说明的是下面图解部分我会用文字代码注释配合描述指针的“指向变化”过程没有用专业画图工具大家看的时候可以自己在纸上画一下效果一样。2. 从结构体开始为什么双向循环链表的节点定义长这样2.1 节点结构体拆解数据域、前驱指针、后继指针各自扮演什么角色双向循环链表的第一步是定义节点的结构体。大部分教材给的都是类似这样的定义typedef struct DNode { int data; // 数据域存具体数据 struct DNode *prior; // 前驱指针指向前一个节点 struct DNode *next; // 后继指针指向后一个节点 } DNode, *DLinkList;这个结构体看着简单但里面有三个细节必须搞清楚不然后面全乱。第一个细节prior和next为什么不直接写成int *prior因为指针必须指向“某种类型的变量”而它指向的是另一个节点所以必须用struct DNode *来声明。这里用了一个自引用的技巧C语言里结构体里可以包含指向自身类型的指针这是链表实现的基础。如果你写成DNode *prior因为此时DNode这个typedef别名还没生效编译器会报错。很多新手在这个地方翻车解决方案就是用struct DNode *或者在typedef之前先声明结构体。第二个细节typedef struct DNode { ... } DNode, *DLinkList;这一行干了两件事。第一件事给struct DNode取了个别名DNode以后声明节点时直接写DNode *p不用每次写struct DNode *p。第二件事定义了一个指针类型DLinkList它就等价于DNode *。为什么还要多此一举定义DLinkList这是为了语义上的区分当函数的返回值、参数表示“整个链表对象”时我们用DLinkList当表示“某个节点”时用DNode *。虽然底层都是指针但读代码的人一眼就能看出你的意图。第三个细节data为什么用int实际上数据域可以是任何类型——结构体、字符串、另一个类的对象都行。用int只是为了教学方便。实际工作中链表的每个节点可能存一个小结构体比如学号姓名成绩数据域换成Student stu即可指针操作的逻辑完全不变。2.2 带头结点还是不带头结点这个选择直接影响你后续所有代码复杂度双向循环链表可以带头结点也可以不带头结点。这个看似不起眼的选择会影响后面所有操作的写法。严格来说双向循环链表有两种组织方式不带头结点head指针直接指向第一个实际存储数据的节点。链表为空时head NULL插入和删除都要考虑“第一个节点”的特殊情况代码分支较多容易出错。带头结点有一个不存实际数据的头结点head永远指向这个哨兵节点。链表为空时头结点的next和prior都指向它自己。插入和删除都统一了逻辑不需要单独处理“第一个节点是不是为空”的分支代码更简洁。考研408和王道数据结构里双向循环链表绝大多数采用带头结点的方式。我自己做项目时也强烈推荐用带头结点的方式因为它的操作逻辑非常统一头结点永远不动实际数据都挂在头结点的“后面”这个环形链上。循环条件的判断也从while (p ! NULL)变成了while (p ! head)或while (p-next ! head)这个差别在后面的遍历和插入删除代码里会反复出现。先看带头结点的空链表长什么样有一个头结点head-next headhead-prior head。也就是说头结点的后驱是自己前驱也是自己。这个状态画在图上就是一个小箭头从头结点出发指回自己。很多同学第一次看到这个结构会懵“这也叫链表就一个节点还指自己”别急你回忆一下循环链表的定义空循环链表本来就应该是“自己指向自己”因为循环没有起点和终点孤零零一个节点时唯一的邻居就是它自己。3. 初始化与判空操作每一个指针指向都有讲究3.1 初始化链表的完整流程与内存分配细节初始化带头结点的双向循环链表代码通常长这样int InitDLinkList(DLinkList *L) { // 分配头结点空间 (*L) (DNode *)malloc(sizeof(DNode)); if (*L NULL) { return -1; // 内存分配失败 } // 初始时刻头结点的前驱和后继都指向自己 (*L)-prior *L; (*L)-next *L; return 0; }这里有一个特别需要留意的细节参数为什么是DLinkList *L而不是DLinkList L因为DLinkList本质是DNode *函数内部需要改变L本身的值让L指向新分配的头结点如果按值传参函数内部修改无法传回实参。这个知识点就是C语言里“传指针”和“传指针的指针”的经典考点。用DLinkList *L也就是DNode **L才能让初始化操作真正生效。初始化之后头结点的两个指针都指向自己。这个设计是不是很巧妙它保证了一个核心约定双向循环链表从任何一个节点出发沿着next走最终能回来沿着prior走也能回来。空表时唯一的“节点”就是头结点自己所以它指自己就是闭环成立。有同学会问为什么不把L直接置为NULL等插入第一个节点的时候再分配内存也可以但那样后续每个操作都要判断“链表是不是刚创建的”代码会多出很多分支。带头结点的统一性丧尽。而用“让头结点指向自己”来代表空表判空条件非常优雅int IsEmpty(DLinkList L) { return (L-next L); // 为空的条件是头结点的next指向自己 }同理判断一个节点是不是最后一个节点也特别方便。if (p-next head)表示p是最后一个节点因为它后面没有其他节点了直接指回头结点。这些判断在插入、删除时经常用到。3.2 遍历打印与循环终止条件为什么不能用 while(p ! NULL)遍历是链表的看家本领。单链表的遍历条件是p ! NULL因为最后一个节点的next是NULL这是链表的“终点标志”。双向循环链表没有NULL终点了再写p ! NULL只会无限循环下去。正确写法void PrintDLinkList(DLinkList L) { DNode *p L-next; // 从头结点后第一个有效节点开始 if (p L) { printf(链表为空\n); return; } while (p ! L) { // 当p回到头结点时遍历结束 printf(%d , p-data); p p-next; } printf(\n); }为什么循环条件是p ! L因为链表是环形的你从头结点的下一个节点出发沿着next一次走一个节点当你再次遇到头结点时说明整个环已经走完一圈这就是“结束”标志。我再补充一种写法有些教材喜欢用do-whileDNode *p L-next; if (p L) { /* 空表 */ } do { printf(%d , p-data); p p-next; } while (p ! L);注意do-while和while的区别while先判断再执行do-while先执行再判断。因为空表时p已经等于L了如果用while版本开头就判断p ! L为假直接跳过没问题如果用do-while版本空表时也会先执行一次循环体打印出无意义的p-data所以do-while版本必须提前判断空表。这两种写法考试都出现过我建议你理解其本质循环条件本质上只有一个——是否回到了头结点。3.3 单节点链表的遍历验证假设链表里只有一个有效节点data5头结点是L。初始化后插入节点5链表状态是头结点 - 节点5 - 头结点 也就是 L-next 节点5 L-prior 节点5 节点5-next L 节点5-prior L遍历时p从L-next出发指向节点5打印5pp-next后p回到L循环终止。完美。4. 插入操作的种类与指针操作顺序这一步能做对链表就掌握了八成4.1 向双向循环链表尾部插入节点完整图解前驱和后继的四步连接尾部插入是使用频率最高的插入操作。我先给出代码再逐行拆解指针操作的顺序以及为什么是这个顺序。// 尾插法在链表末尾即头结点的prior位置插入一个新节点 int InsertTail(DLinkList L, int e) { DNode *newNode (DNode *)malloc(sizeof(DNode)); if (newNode NULL) { return -1; } newNode-data e; // 关键操作让新节点建立和最后一个节点、头结点的双向链接 DNode *tail L-prior; // 找到最后一个节点头结点的前驱 newNode-next L; // 1. 新节点的后继指向头结点 newNode-prior tail; // 2. 新节点的前驱指向当前最后一个节点 tail-next newNode; // 3. 当前最后一个节点的后继指向新节点 L-prior newNode; // 4. 头结点的前驱指向新节点 return 0; }画在图上是这样的当前链表非空头结点 - A - BB是尾部。插入新节点N后头结点 - A - B - N - 头结点现在看指针修改的顺序为什么是1234而不是随机顺序。这里有一个核心原则在覆盖一个节点的next或prior之前要么这个指针的老值已经“没人需要了”要么你提前用局部变量保存了老值。上述代码中我们先用tail L-prior找到了尾部节点B然后执行步骤1和2修改的是新节点的next和prior不影响原有链表结构。步骤3修改tail-next把原来指向头结点的next改成了新节点此时头结点还没受影响最后步骤4修改L-prior。这个顺序非常安全在任意一步中断链表都不会完全断掉——当然实际代码不会中断只是从逻辑安全性上讲。如果反过来先把tail-next newNode然后L-prior newNode最后才设置newNode-next和newNode-prior会出现什么后果在执行完tail-next newNode之后我们通过tail已经无法找到原来的头结点了tail-next已经指向了新节点而新节点还没有指向头结点此时头结点丢失了——这就是断链。这也是链表操作最常见的bug来源。同样的逻辑可以推广到头插法。头插法在头结点后面插入节点int InsertHead(DLinkList L, int e) { DNode *newNode (DNode *)malloc(sizeof(DNode)); if (newNode NULL) return -1; newNode-data e; DNode *first L-next; // 保存原来的第一个节点 newNode-next first; newNode-prior L; L-next newNode; first-prior newNode; return 0; }头插和尾插的指针操作有异曲同工之妙先设置新节点的两个指针此时新节点还未“接入”链表再修改原有节点的指针。这个原则记住后任何插入都能写对。4.2 指定位置插入边界条件的判断决定了代码会不会崩指定位置插入常见的有“在第i个位置插入”和“在给定节点p之后插入”两种。后者更基础前者可以建立在后者的基础上。在节点p之后插入一个新节点s是双向链表的核心操作。代码和步骤int InsertAfterNode(DNode *p, int e) { if (p NULL) return -1; DNode *newNode (DNode *)malloc(sizeof(DNode)); if (newNode NULL) return -1; newNode-data e; newNode-next p-next; // 新节点后继指向p的原后继 newNode-prior p; // 新节点前驱指向p p-next-prior newNode; // p的原后继的前驱改为新节点 p-next newNode; // p的后继改为新节点 return 0; }注意p-next-prior newNode和p-next newNode的顺序。如果先执行p-next newNode那p-next-prior实际上就是newNode-priornewNode自己指向自己而原有的后继节点丢失了完全乱套。所以必须先让原后继的prior指过来再改p的next。你可以把这个顺序记成“先搭新绳再解旧绳”。在节点p之前插入很多同学觉得要重新遍历找p的前驱但别忘了这是双向循环链表p-prior就是前驱。所以“在p之前插入”完全可以转换成“在p的前驱节点之后插入”不产生新的复杂度。第i个位置插入就是在链表上遍历i-1步找到第i-1个节点然后调用在节点后插入的函数。剩下的就是越界判断int InsertAtPos(DLinkList L, int i, int e) { if (i 1) return -1; DNode *p L; int j 0; while (j i - 1 p-next ! L) { p p-next; j; } if (p-next L j i - 1) { return -1; // 位置不合法链表长度不够 } return InsertAfterNode(p, e); }这里while (j i - 1 p-next ! L)的循环条件和单链表非常相似区别只在终止判断从p ! NULL变成了p-next ! L因为在循环链表里没有NULL可判断了。5. 删除操作全解删除单个节点、头删、尾删的代码与陷阱5.1 删除指定节点为什么时间复杂度是O(1)双向链表节点有prior指针删除指定节点时不需要从头遍历寻找前驱这是它最大的优势。删除节点p的代码如下int DeleteNode(DNode *p) { if (p NULL) return -1; // 特殊处理如果p是头结点不能直接删除或者约定不允许删头结点 p-prior-next p-next; // 前驱的后继跳过p指向p的后继 p-next-prior p-prior; // 后继的前驱跳过p指向前驱 free(p); // 释放p的内存 return 0; }图解假设链表是A - p - B执行删除p后变成A - B。第一行让A的next指向B第二行让B的prior指向Ap就从双向链接中摘除了此时p既没人指向它它也不指向别人可以安全free。这个操作就是教科书上说的O(1)删除。对比单链表单链表删除一个已知节点p虽然代码可以写成“复制后继数据覆盖p再删除后继”的技巧性O(1)但这是障眼法且删除尾节点时失效。双向循环链表的O(1)是天然就有的。使用这个函数时有一个隐藏约定你不能传头结点进去。因为在带头结点的结构里头结点是哨兵删掉它整个链表的起点就没了。所以实际调用时要么在函数里判断if (p L) return -1;要么调用方保证p不是头结点。5.2 头删和尾删的重复代码陷阱有了DeleteNode头删和尾删可以非常简洁// 头删删除第一个有效节点 int DeleteHead(DLinkList L) { if (L-next L) return -1; // 空表没有可删的 return DeleteNode(L-next); } // 尾删删除最后一个有效节点 int DeleteTail(DLinkList L) { if (L-next L) return -1; return DeleteNode(L-prior); // 尾节点就是头结点的前驱 }头删和尾删的核心代码各只有两三行非常清爽。这也是带头结点结构的好处——头删尾删不需要像不带头结点那样处理“删完后链表变空”的边界情况因为头结点的存在让“空表”也有一个确定的形态所有的删除逻辑都被统一了。但有一个坑值得单独提醒free(p)之后原来的指针p就变成了“悬空指针”。虽然p这个变量还存在但你不能再通过它访问任何数据。很多同学在删除节点后依然习惯性地打印p-data然后程序崩了就一脸懵。规范做法是删除后立即让指针置为NULL或者不再使用这个指针变量。5.3 按值删除的完整实现遍历、查找、删除的联动按值删除就是把包含特定数值的节点找出来再删除。如果是删除所有匹配节点代码如下int DeleteByValue(DLinkList L, int value) { if (L-next L) return -1; // 空表直接返回 DNode *p L-next; while (p ! L) { if (p-data value) { DNode *toDelete p; p p-next; // 先保存下一个节点再执行删除 toDelete-prior-next toDelete-next; toDelete-next-prior toDelete-prior; free(toDelete); } else { p p-next; } } return 0; }这里的关键点是在调用删除前必须先把p移到下一个节点否则删除当前节点后p已经指向一块被free的内存你再用p p-next就会访问非法内存。这是链表“边遍历边删除”问题最常见、也最容易忽略的bug。笔试和面试里经常考这个场景。许多人按值删除只删第一个匹配值而这里给出的是删除所有匹配值的版本。删除第一个匹配值还简单些找到直接DeleteNode(p)然后break即可。6. 构建一个有数据的链表头插法和尾插法建立链表的差异与代码6.1 用尾插法建立链表保持输入数据的顺序实际写程序时我们往往不是手动一个个Insert后调用而是通过连续读入来构建链表。尾插法可以保持输入顺序用来建立顺序与输入一致的链表。DLinkList CreateListByTail() { DLinkList L; InitDLinkList(L); int n, x; printf(请输入节点个数); scanf(%d, n); for (int i 0; i n; i) { scanf(%d, x); if (InsertTail(L, x) ! 0) { printf(插入失败\n); break; } } return L; }因为尾插法每次都向尾部插入插入的时间复杂度是O(1)直接使用L-prior找到尾节点所以建立整个链表的时间是O(n)。这一点比单链表的尾插法还方便后者需要一个tail指针或者每次遍历找尾。6.2 用头插法建立链表数据逆序的秘密头插法每次都在头结点之后插入后输入的数据反而排在最前面。所以用头插法建立链表后打印出来的顺序和输入顺序是反的。这在“逆置链表”类问题中可以直接用DLinkList CreateListByHead() { DLinkList L; InitDLinkList(L); int n, x; printf(请输入节点个数); scanf(%d, n); for (int i 0; i n; i) { scanf(%d, x); if (InsertHead(L, x) ! 0) { printf(插入失败\n); break; } } return L; }为什么头插法会逆序你可以想象一群人排成一队每次都把新来的人插到队伍最前面最终队伍的顺序就是“后来者居上”。所以如果你想把一个数组逆序存储到双链表中头插法是最直观的做法。一个常见的面试题如何用一个双向循环链表实现栈或者队列双向循环链表的头插头删就是栈的push/pop尾插头删就是队列的入队/出队。正因为插入删除都是O(1)双向循环链表很适合作为这些数据结构的底层实现。7. 实战调试经验我在链表代码上踩过的最经典的三个坑7.1 坑一初始化时忘记让头结点指向自己导致的NULL访问我见过最多的报错就是Segmentation fault。一排代码一行行检查发现头结点的prior和next都没有初始化是个野指针。访问野指针内存轻则出垃圾值重则直接段错误。所以说初始化那段代码不是什么可有可无的仪式它的作用是给头结点一个确定的“自环”状态。就好比你开一家店开店第一件事是开门营业。只不过对双向循环链表来说“锁门”状态就是“门自己指着自己”。很多人在写InitDLinkList时写成了(*L)-next NULL; (*L)-prior NULL;这就是把单链表的写法套过来了。在单链表里头结点的next初始化为NULL没问题在双循环链表里这完全错误。NULL意味着链表“有终点”而你后面所有遍历都靠p ! L来判定结束NULL永远无法让循环终止你会陷入无限循环或者在第一次插入时就出问题。7.2 坑二打印时错用p ! NULL导致无限循环这个问题在实验报告和上机考试里出现频率极高。很多同学来自于单链表的“肌肉记忆”一写遍历就是while (p ! NULL)。在双向循环链表里这么写p永远不会为NULL除非还没初始化程序就会一直打印下去输出刷刷刷地滚动。判断遍历结束的唯一标准是是否回到了起点。这个起点就是头结点。只要你的链表是带头结点的环形结构遍历条件永远是while (p ! L)或者while (p-next ! L)。前者是当前节点做判断适合“处理当前节点”后者是后继节点做判断适合“判断是否有下一个节点”。我建议在打印、查找、修改、删除等不同场景下都亲手画一画循环的“进入”和“退出”位置把这两个条件对应的语义想清楚。这不是能靠背代码解决的问题理解循环条件和游标位置比你抄十遍代码都管用。7.3 坑三删除时先free后修改指针前面按值删除的代码里我特意在删除前先p p-next原因就在这里。有些同学图省事写成p-prior-next p-next; p-next-prior p-prior; free(p); p p-next; // p已经被free了这是悬空指针这段代码在运行的时候可能第一次不会崩因为free掉的内存还没被其他数据覆盖p-next仍然“碰巧”指向下一个节点。但这是未定义行为随时可能在列表更大、内存分配更频繁时崩溃。而且这种崩溃时有时无最难排查。我的经验法则是凡是涉及删除当前节点后还要继续遍历的先保存后继节点再删凡是删除后不再用的指针立刻置为NULL。养成这个习惯你写链表代码的bug率至少降一半。7.4 坑四内存泄漏——只删节点不free或者free了却已经没有指针引用还有一类坑不是崩是内存泄漏。很多同学做课设时程序跑起来一切正常但内存占用越来越大最后卡死。原因往往是链表的销毁函数没写好或者干脆没写销毁函数。销毁整个双向循环链表的代码void DestroyList(DLinkList L) { if (L NULL) return; DNode *p L-next; while (p ! L) { DNode *temp p-next; // 先保存后继 free(p); // 释放当前节点 p temp; } free(L); // 最后释放头结点 }这里同样用了“先保存后继再释放当前节点”的手法。释放完整个链表后最好让外部指针也置为NULL避免悬空引用。C语言里没有垃圾回收内存管理全靠自觉。每次malloc都对应一次free这句口号要刻在心里。用Java、Python写链表时虽然不需要手动管理内存但那种“先保存引用再删除”的思路是一样的只是不需要调用free。8. 双向循环链表的典型应用场景为什么学了数据结构要学到这个版本8.1 操作系统进程调度里的时间片轮转双向循环链表在真实工程中最有名的应用之一是操作系统的进程调度。时间片轮转调度算法需要循环执行每个进程用完一个时间片就轮到下一个。这个场景天然适合环形结构——不需要“到底了重新从头开始”因为压根没有头尾指针永远在环形链表上游走。为什么用双向而不仅仅是用单向循环链表因为操作系统经常需要撤销、暂停、优先级调整等操作这些操作往往需要快速访问一个进程的前驱。举个简单的例子调度器发现当前进程需要立即阻塞等待I/O此时需要把它从就绪队列中摘除。如果是单向循环链表删除当前节点还得先回头找前驱多花时间双向循环链表直接通过prior指针一步到位。在操作系统这种性能敏感的环境里少一次遍历就是实打实的性能提升。热搜词里也出现了“linux的内存管理子系统中有哪些重要的数据结构”很多操作系统的重要结构底层就是链表理解了双向循环链表再去看内核源码会顺畅很多。8.2 LRU缓存淘汰中的双向链表设计LRU缓存淘汰算法也算数据结构题里的常客了。经典实现是“哈希表双向链表”的组合哈希表负责O(1)查找双向链表负责O(1)插入和删除。每次访问一个数据就把它移动到链表头部缓存满时删除链表尾部的数据。为什么LRU用双向链表而不是单向链表因为当缓存命中某个节点我们要把它从当前位置摘下来再移到头部。单链表删除指定节点需要知道前驱只能遍历O(n)的代价在缓存场景下不可接受。双向链表天然知道前驱删除后重挂是O(1)。这里和我前面讲的尾删代码思想完全一致——借助L-prior找到最后一个节点O(1)时间解决。如果你把LRU缓存实现过一遍再回头看双向循环链表的插入删除代码你会有一种“原来如此”的通透感。8.3 约瑟夫环问题循环链表最经典的算法题约瑟夫环Josephus problem是循环链表应用里最出名的练习题了。n个人围成一圈从第k个人开始报数报到m的人出列然后从下一个人重新报数直到所有人都出列。这个“围成一圈”的场景用循环链表模拟起来非常自然指针沿着next走m-1步把当前节点删除删除后automatic地走到下一个节点继续报数。双向循环链表实现约瑟夫环比单向循环链表还方便因为出列后指针要“回到下一个人”。单链表删除当前节点后需要额外保存下一个节点双向循环链表删除时通过prior和next自然连接操作后游标直接就是后继节点。代码也更直观。8.4 编辑器文本缓冲区的双向游标还有一个贴近日常的应用——文本编辑器的撤销/重做和光标移动。文本以行为单位存储在链表结构中光标在某一行用户按上箭头时光标往前一行移动按向下箭头往后移动。双向链表天然支持两个方向的移动。循环结构则保证当光标在第一行时按上箭头可以跳到末尾在最后一行按向下箭头又能跳回开头这在某些“循环浏览”的交互设计中很实用。9. 链表学习的认知升级从“背代码”到“画图推演”说了这么多代码和实现最后想聊聊学习方法层面的问题。我见过太多同学学链表的方式就是把代码背下来考试默写考完就忘。这种学习方式的致命问题是题目稍微变一下——比如把带头结点改成不带头结点或者把单链表改成双循环链表——就彻底慌了。我自己的学习经验是拿一张A4纸和一支铅笔把一个链表从初始化、插入、删除到销毁的每一步都用图示画一遍。不要嫌麻烦画完一个完整流程你脑子里就有了指针变化的动态图景。再遇到代码问题你不是在回忆代码而是在回忆那幅图。代码只是图的翻译。双向循环链表的图景是什么是一个环。你从环上任意一个节点出发沿着任何一个方向都一定能遍历所有节点再回到起点。头结点不过是这个环上你选定用来“进入”的那个点。所有操作的逻辑都围绕环上节点之间的断链和重新连接展开。再进一步等你熟练了C语言的指针操作完全可以尝试用Java、Python写一遍同样的逻辑。Python的链表写法里没有指针但思维模型一样Java的引用和C的指针在链表层面几乎一一对应。用多种语言验证同一套逻辑你对链表本质的理解才会真正牢固。10. 完整可运行的参考代码直接复制编译就能跑我在文章里散落了各个函数的定义为了大家方便这里给出一份完整的、可编译运行的代码。用的是C语言编译器用gcc即可。代码文件保存为dlist.c然后终端执行gcc dlist.c -o dlist ./dlist就能跑起来。#include stdio.h #include stdlib.h typedef struct DNode { int data; struct DNode *prior; struct DNode *next; } DNode, *DLinkList; // 初始化带头结点的空双向循环链表 int InitDLinkList(DLinkList *L) { (*L) (DNode *)malloc(sizeof(DNode)); if (*L NULL) return -1; (*L)-prior *L; (*L)-next *L; return 0; } // 判空 int IsEmpty(DLinkList L) { return L-next L; } // 尾插 int InsertTail(DLinkList L, int e) { DNode *newNode (DNode *)malloc(sizeof(DNode)); if (newNode NULL) return -1; newNode-data e; DNode *tail L-prior; newNode-next L; newNode-prior tail; tail-next newNode; L-prior newNode; return 0; } // 头插 int InsertHead(DLinkList L, int e) { DNode *newNode (DNode *)malloc(sizeof(DNode)); if (newNode NULL) return -1; newNode-data e; DNode *first L-next; newNode-next first; newNode-prior L; L-next newNode; first-prior newNode; return 0; } // 在节点p之后插入 int InsertAfterNode(DNode *p, int e) { if (p NULL) return -1; DNode *newNode (DNode *)malloc(sizeof(DNode)); if (newNode NULL) return -1; newNode-data e; newNode-next p-next; newNode-prior p; p-next-prior newNode; p-next newNode; return 0; } // 删除节点p int DeleteNode(DNode *p) { if (p NULL) return -1; p-prior-next p-next; p-next-prior p-prior; free(p); return 0; } // 头删 int DeleteHead(DLinkList L) { if (L-next L) return -1; return DeleteNode(L-next); } // 尾删 int DeleteTail(DLinkList L) { if (L-next L) return -1; return DeleteNode(L-prior); } // 按值删除所有匹配的节点 int DeleteByValue(DLinkList L, int value) { if (L-next L) return -1; DNode *p L-next; while (p ! L) { if (p-data value) { DNode *toDelete p; p p-next; toDelete-prior-next toDelete-next; toDelete-next-prior toDelete-prior; free(toDelete); } else { p p-next; } } return 0; } // 遍历打印 void PrintDLinkList(DLinkList L) { DNode *p L-next; if (p L) { printf(链表为空\n); return; } while (p ! L) { printf(%d , p-data); p p-next; } printf(\n); } // 销毁整个链表 void DestroyList(DLinkList L) { if (L NULL) return; DNode *p L-next; while (p ! L) { DNode *temp p-next; free(p); p temp; } free(L); } int main() { DLinkList L; if (InitDLinkList(L) ! 0) { printf(初始化失败\n); return -1; } // 尾插建立链表 printf(尾插 10, 20, 30\n); InsertTail(L, 10); InsertTail(L, 20); InsertTail(L, 30); PrintDLinkList(L); // 头插 printf(头插 5\n); InsertHead(L, 5); PrintDLinkList(L); // 删除第一个节点 printf(头删\n); DeleteHead(L); PrintDLinkList(L); // 删除最后一个节点 printf(尾删\n); DeleteTail(L); PrintDLinkList(L); // 按值删除 printf(再插回 40, 50, 60然后删除值为50的节点\n); InsertTail(L, 40); InsertTail(L, 50); InsertTail(L, 60); PrintDLinkList(L); DeleteByValue(L, 50); PrintDLinkList(L); // 销毁 DestroyList(L); printf(链表已销毁\n); return 0; }我把这份代码在我的环境里编译运行过输出如下尾插 10, 20, 30 10 20 30 头插 5 5 10 20 30 头删 10 20 30 尾删 10 20 再插回 40, 50, 60然后删除值为50的节点 10 20 40 50 60 10 20 40 60 链表已销毁你可以自己跑一遍再打断点单步调试看每一步指针的变化。单步调试是理解链表指针操作的“神器”——每执行一行代码观察p-prior和p-next的值怎么变化比自己盯着纸面想象要直观得多。最后说一句掏心窝的话双向循环链表也许是链表学习里最绕的一环但它也是你从“会写链表代码”跨越到“真正理解链表结构”的试金石。你把这篇文章里的图在纸上画一遍把代码敲一遍再用调试器跟一遍链表这块就彻底过关了。后续再面对各种复杂数据结构你都会有一个非常扎实的底层模型。
