1. 为什么单链表不够用需要双向链表很多同学学到链表这一章第一个接触的往往是单链表一个结点里存一个数据域再加一个 next 指针指到下一个结点。这东西上手确实快但用着用着就会碰到一个让人抓狂的痛点——想找某个结点的前一个结点得从头开始一路遍历过去。比如你在第 100 个结点的位置想知道第 99 个结点是谁不好意思只能从 head 重新走一遍。这在做删除操作、倒序遍历、局部反转这类场景时时间复杂度直接拉到 O(n)一旦链表长了性能很难看。我当年写课设的时候用单链表做一个简单的文本编辑器每一行是一个结点。用户光标在第 50 行想往上移动一行我的实现居然是从头结点重新遍历到第 49 行当时觉得代码能跑就行后来数据量到几千行的时候每按一次方向键都卡顿这才意识到问题出在哪。单链表只有单向的“继承关系”缺少“回溯能力”。而双向链表就是在那条链上多开了一条“回程路”每个结点除了 next 指向后继还多了一个 prev 指向前驱。这样一来往前找、往后找都是 O(1) 的相邻移动很多问题迎刃而解。2. 双向链表长什么样设计思路先想清楚2.1 结点结构多一个指针不是白加的双向链表的结点定义以 C 语言为例通常是这样的typedef int LTDataType; typedef struct ListNode { struct ListNode* prev; // 指向前一个结点 LTDataType data; // 数据域 struct ListNode* next; // 指向后一个结点 } ListNode;多了一个 prev 指针代价是每个结点多占 8 字节64 位系统下一个指针的大小。看起来空间翻了一倍但对现代计算机的内存来说这 8 字节几乎可以忽略。换来的却是遍历、删除、插入操作上的灵活性这就是一个典型的“空间换时间”思路。初学阶段容易纠结“多一个指针是不是浪费”其实在工程里如果这个操作频繁发生那这点空间开销非常划算。2.2 带头结点 vs 不带头结点链表还有一种常见分类带头结点和不带头结点。这里说的“头结点”不是指第一个数据结点而是一个额外的、不存有效数据的哨兵位。很多初学者不理解为什么要平白多一个空结点出来总觉得别扭。但在双向链表的实现里头结点带来的好处非常实在它把“空表”和“非空表”的操作统一了。不带头结点的链表插入到第一个位置和删除第一个结点时需要单独判断“是不是首结点”因为要更新头指针指向。而带头结点的链表头指针永远指向哨兵位数据结点的插入和删除逻辑完全一致不需要特判。考试和面试里写代码少一个 if 分支就少一分出错的可能。所以在后续的代码实现中我会统一使用带头结点的双向循环链表这也是严蔚敏版教材、王道考研系列、Linux 内核链表实现中普遍采用的经典结构。带头双向循环链表也就是最后一个结点的 next 指向哨兵头结点哨兵头结点的 prev 指向最后一个结点。第一次看这个结构的人会觉得绕但你写几行代码就会发现它的妙处找尾结点不需要遍历直接 head-prev 就是尾遍历的结束条件不是 next NULL而是 cur head。整个链表成环任何位置的操作入口都极其对称。3. 核心操作怎么实现直接能抄的代码3.1 初始化先把哨兵结点立起来我们定义一个链表结构体里面只需要存一个头指针typedef struct ListNode* LTNode; // 创建新结点data 为结点数据 LTNode BuyListNode(LTDataType x) { LTNode newNode (LTNode)malloc(sizeof(struct ListNode)); if (newNode NULL) { perror(malloc fail); exit(EXIT_FAILURE); } newNode-data x; newNode-prev NULL; newNode-next NULL; return newNode; } // 初始化带头双向循环链表返回哨兵头结点 LTNode LTInit() { LTNode pHead BuyListNode(-1); // 哨兵位data 不存储有效数据 pHead-next pHead; pHead-prev pHead; return pHead; }这里初始化的时候让头结点的 prev 和 next 都指向自己表示“空表”。很多同学第一次写的时候会写成 next NULL、prev NULL这样后面遍历和插入时都要额外判断空指针平白增加代码复杂度。成环的写法从结构上就把空表的状态也“统一”成了一个合法的链表状态。3.2 打印遍历循环终止条件是回到头结点打印函数是检验链表结构是否正确的第一道关卡void LTPrint(LTNode pHead) { assert(pHead); // 头结点不能为空 printf(guard - ); LTNode cur pHead-next; while (cur ! pHead) { printf(%d - , cur-data); cur cur-next; } printf(guard\n); }循环条件是cur ! pHead也就是遍历完所有数据结点后回到哨兵结点即停止。打印的结果我会习惯性地把哨兵位的 guard 也打出来方便调试时直观看到“环”的状态。这里有一个小细节不要用cur-next ! pHead作为循环条件那会漏掉最后一个结点这是初学最容易犯的边界错误。3.3 尾插找到尾结点三根指针一次接好尾部插入一个结点是双向链表里最有代表性也最简单的插入操作void LTPushBack(LTNode pHead, LTDataType x) { assert(pHead); LTNode newNode BuyListNode(x); LTNode tail pHead-prev; // 带头循环链表头结点的前驱就是尾结点 // 先把 newNode 的 prev 和 next 接好 newNode-prev tail; newNode-next pHead; // 再让原来的尾结点和头结点分别指向 newnode tail-next newNode; pHead-prev newNode; }这里最关键的技巧就是pHead-prev直接拿到尾结点不需要遍历。整个接线过程只有 4 条指针赋值顺序上建议先设置新结点的前后指针再修改原链表中两个结点的指向。如果反过来先把 tail-next 改了万一后面某个结点指针丢失调试起来就麻烦。3.4 头插在哨兵结点之后插入头插和尾插在带头循环链表里几乎对称void LTPushFront(LTNode pHead, LTDataType x) { assert(pHead); LTNode newNode BuyListNode(x); LTNode first pHead-next; // 原来的第一个数据结点 // 新结点插入到 pHead 和 first 之间 newNode-prev pHead; newNode-next first; pHead-next newNode; first-prev newNode; }注意头插的位置是 “哨兵结点的后面”不是 “第一个数据结点的前面”。很多同学分不清头插和尾插的差异其实在带头循环链表里头插的本质是 “在 head 之后插入”尾插的本质是 “在 head 之前插入”。由于链表成环旋转对称这两个操作在实现上几乎一模一样只是选择的参照结点不同。3.5 任意位置插入在 pos 结点之前插入指定位置插入通常是在某个已知结点的前面插入新结点void LTInsert(LTNode pos, LTDataType x) { assert(pos); // pos 不能为 NULL // 不支持在哨兵头结点之前插入也就是不能在“链表开头之前”插入 if (pos NULL) return; LTNode newNode BuyListNode(x); LTNode prev pos-prev; // 接线newNode 夹在 prev 和 pos 之间 newNode-next pos; newNode-prev prev; prev-next newNode; pos-prev newNode; }实现逻辑非常统一只要是“在 pos 之前插入”不管 pos 是普通结点还是尾结点代码都是一样的这也是带头循环链表最优雅的地方。实际应用里如果要在某个位置之后插入可以传pos-next作为参数或者在函数内部再封装一层。3.6 删除操作先记住前驱再跨过目标结点删除 pos 位置结点的核心逻辑void LTErase(LTNode pos) { assert(pos); // 哨兵头结点不能删 if (pos pHead || pos NULL) return; LTNode prev pos-prev; LTNode next pos-next; prev-next next; next-prev prev; free(pos); pos NULL; // 防止野指针 }删除的关键在于先把前后两个结点“跨过”目标结点直接连起来再释放目标结点。操作顺序同样重要先改 prev 的 next再改 next 的 prev最后 free。如果先 free 再去改指针就是典型的悬空指针问题。尾删和头删可以复用这个函数尾删就是LTErase(pHead-prev)头删就是LTErase(pHead-next)。这就是把函数通用化的好处封装一次到处复用。3.7 查找与修改拿到结点地址才能定点操作查找返回的是结点指针而不是下标LTNode LTFind(LTNode pHead, LTDataType x) { assert(pHead); LTNode cur pHead-next; while (cur ! pHead) { if (cur-data x) return cur; // 返回第一个匹配的结点地址 cur cur-next; } return NULL; }拿到结点地址后你就可以配合 LTInsert 和 LTErase 在指定位置做插入、删除操作。比如 “删除所有值为 3 的结点”就可以通过查找删除的组合循环实现。很多练习题看起来难实际就是把基础函数灵活组装。3.8 销毁链表不能只 free 头结点销毁是最容易写出内存泄漏的操作之一。正确的做法是遍历所有数据结点逐个释放最后释放头结点void LTDestroy(LTNode pHead) { assert(pHead); LTNode cur pHead-next; while (cur ! pHead) { LTNode next cur-next; // 先保存下一个结点地址 free(cur); cur next; } free(pHead); pHead NULL; }注意循环里先next cur-next再 free防止 free 之后访问 cur-next 导致非法访问。头结点是最后一个释放的释放完记得把外部的头指针置空否则外面那个指针就成了野指针。这一步很多人会漏导致后续程序崩溃。4. 实操全过程从建表到增删查改的完整示例为了让上面的函数串起来我们用一个完整的小程序跑一遍流程这也是我常推荐给初学者的“测试驱动学习法”——每写一个函数马上用一个场景去调用它立刻看输出。void TestDList() { LTNode plist LTInit(); // 尾插 4 个数据: 1 2 3 4 LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPrint(plist); // 期望: guard - 1 - 2 - 3 - 4 - guard // 头插 2 个数据: 0 -1 LTPushFront(plist, 0); LTPushFront(plist, -1); LTPrint(plist); // 期望: guard - -1 - 0 - 1 - 2 - 3 - 4 - guard // 查找值为 3 的结点在它之前插入 99 LTNode pos LTFind(plist, 3); if (pos ! NULL) { LTInsert(pos, 99); } LTPrint(plist); // 期望: guard - -1 - 0 - 1 - 2 - 99 - 3 - 4 - guard // 删除值为 0 的结点 pos LTFind(plist, 0); if (pos ! NULL) { LTErase(pos); } LTPrint(plist); // 期望: guard - -1 - 1 - 2 - 99 - 3 - 4 - guard // 头删、尾删各一次 LTErase(plist-next); LTErase(plist-prev); LTPrint(plist); // 期望: guard - 1 - 2 - 99 - 3 - guard // 销毁链表 LTDestroy(plist); plist NULL; }我每次调试链表代码都会写这种带打印的测试函数每做一步操作就立刻验证结果。写链表最忌讳的是写完一堆函数直接上线跑出问题根本定位不到是哪一步埋的雷。如果你按照这个步骤操作每一步打印的注释里都有期望值代码输出的结果和期望值一对比立刻就能发现插入逻辑、删除逻辑到底哪里出了问题。5. 我在双向链表踩过的坑整理成速查表双向链表的代码量不大但坑非常密集。我把这些年来的错误经验汇总成一张表每一项都是实际调试过、崩溃过的血泪教训。常见错误现象原因分析正确做法尾插时直接用 pHead-next 找尾数据插到了第二个位置对带头循环链表结构不熟把 head-next 当成尾尾结点用 pHead-prev 获取插入时先改前驱的后继数据错乱或链表断链指针赋值顺序错误导致部分结点“失联”先设置新结点自身指针再改链上结点删除后没有 free内存泄漏程序越跑越慢忘记释放被移除的结点删除操作里必须 free(pos)free 之后还访问 pos-next程序崩溃或随机值野指针继续使用free 后及时置空指针遍历条件写成 cur ! NULL死循环或访问非法内存循环链表里没有 NULL 终点终点是头结点遍历条件改成 cur ! pHead只 free 头结点就结束大量内存泄漏没有释放数据结点完整遍历释放所有数据结点后再释放头结点查找函数返回 NULL 没判断空指针解引用崩溃没找到目标结点直接使用返回值外部必须判断 if(pos ! NULL) 再使用形参指针没有断言传 NULL 时程序异常崩溃没有防御性编程意识函数入口处 assert(pHead)这 8 条里前 4 条是初学者最容易踩的后 4 条是上了项目之后才会暴露的隐患。我建议你把这张表截图保存下来写完代码之后逐一对照检查比自己盲目调试效率高得多。6. 双向链表在真实场景里用在哪学了能做什么6.1 双端队列的底层结构很多语言里都有的双端队列deque允许在头部和尾部都能高效插入删除。用双向链表实现“双端操作”简直是天作之合头插头删是 O(1)尾插尾删也是 O(1)。如果换成单链表头插 O(1)、尾插需要遍历所以是 O(n)完全没法做到两边都高效。数据结构教材里说的“受限的线性表”双向链表就是最常用的底层实现方案之一。6.2 LRU 缓存淘汰算法JDK 里的 LinkedHashMap 实现 LRU最近最少使用缓存时底层维护了一个双向链表按照访问顺序存放元素。被访问过的结点会被移动到链表头部如果缓存满了就把链表尾部的结点淘汰掉。整个过程需要频繁移动结点到链表头部这种“摘下来再插到头”的操作在双向链表里只需要改几个指针效率极高。6.3 操作系统的任务队列进程调度、文件系统缓存页的管理也会用到双向链表。比如 Linux 内核里大量使用的 list_head就是一个不带数据域的双向循环链表通过container_of宏来获取宿主结构体。这种设计的好处是链表操作与具体数据完全解耦任何一个结构体只要嵌入一个 list_head 成员就自动获得了链表的全部能力。初学阶段可能觉得这个有点硬核但如果你以后要读内核源码双向链表的基本功必须打好。6.4 考研和面试的常客408 考研、各大厂笔试面试里双向链表几乎是必考的知识点之一。不过考试里考的往往不是让你从头实现完整链表而是考“链表逆置”、“判断链表是否对称”、“找中间结点”这类综合题。这些题目有一个共同点单链表解法通常需要复杂的三指针维护双向链表解法则天然有 prev 指针帮你省掉一半的思维量。7. 双向链表的逆置、对称判断等经典题拓展7.1 链表逆置双向链表天然好写单链表逆置需要三指针pre、cur、next不断后移双向链表逆置直接交换每个结点的 prev 和 next 就可以了最后再把头结点的指向换一下。void LTReverse(LTNode pHead) { assert(pHead); LTNode cur pHead; do { // 交换 cur 的 prev 和 next LTNode tmp cur-next; cur-next cur-prev; cur-prev tmp; cur cur-prev; // 注意交换之后原来的 prev 变成了 next } while (cur ! pHead); }这里有一个很关键的细节遍历方向的选择。每个结点的 next 和 prev 交换之后原本“下一个结点”的位置变成了cur-prev所以循环推进用的是cur cur-prev。逻辑上有点绕但代码简洁理解之后非常有成就感。7.2 判断链表是否对称带头双向循环链表天然具备“从两边往中间走”的能力判断对称可以用两个指针一个从 head-next 往后走一个从 head-prev 往前走每次比较数据是否相等直到两个指针相遇或者交错。bool LTSymmetric(LTNode pHead) { assert(pHead); LTNode left pHead-next; LTNode right pHead-prev; while (left ! right left-prev ! right) { if (left-data ! right-data) return false; left left-next; right right-prev; } return true; }这里的循环条件left ! right left-prev ! right用来处理奇数个和偶数个两种情况奇数个时左右指针会指向中间同一个结点偶数个时左右指针会相邻并交错。单链表想实现对称判断得先找到中点、再反转后半段麻烦不少。双向链表写起来就是一个双指针向心运动两行循环就搞定。7.3 插入排序和归并排序的自然应用链表不适合快排因为随机访问性能差但插入排序在链表上其实很顺手每次从原链表中取出一个结点在已排序链表中找到合适位置插入。双向链表做这个操作时找位置往前、往后移动都是 O(1) 的相邻移动明显比单链表舒服。归并排序同理找中点用快慢指针合并过程两个链表各自向后移动也都是自然适配。8. 结尾我的一点实战心得双向链表这块内容初学者通常有两种极端反应一种觉得“不就是多了一个指针吗有什么难的”另一种觉得“循环链表绕着绕着就晕了”。我的经验是双向链表真正难的不是代码本身而是指针操作时脑子里要始终保持“前后两根链”同时正确的图景。我练这个模块的时候画图不下几十遍每画一次就对应写一次代码一图一码对照着来比干想代码逻辑高效太多。还有一个很实用的技巧在测试代码里故意写错一个指针赋值然后观察打印结果的表现。比如故意不设置 newNode-prev你看打印结果有时看不出异常但一旦反向遍历或删除时就炸了。这种“逆向测试”能帮你快速理解每个指针到底在支持哪些操作。如果你正在准备数据结构考试或者在刷算法面试题双向链表值得你花一整天时间彻底吃透。把它和单链表放在一起对比着学重点理解“为什么单链表做不到的事双向链表能做到”这个思维转换比背十遍代码都管用。接下来可以继续往 “双向循环链表与内核链表设计” 方向进阶也可以开始刷 LeetCode 上链表的经典题目祝大家写链表不崩、调链表不慌。