双向链表从入门到实战：插入删除、逆置与LRU缓存实现

链表这个基础数据结构很多人的学习路线都是先单链表、再双向链表。我最早在嵌入式菜单项目里用双向链表是因为要在菜单层级中既能“向后翻”又能“向前翻”后来在算法题里实现 LRU 缓存也是靠双向链表才做到 O(1) 的移动和删除。这篇文章把我的双向链表实现经验完整梳理一遍为什么需要双向链表、怎么定义节点、插入删除的指针顺序、C/C/Java/Python/嵌入式常见写法以及真正容易踩的坑。无论你是在准备笔试面试还是要在项目里自己封装链表这里的内容都可以直接拿去做参考。1. 单链表不敢回头看双向链表解决的真实痛点1.1 单链表的“删除尴尬”与逆向访问缺失先回忆一个最基础的操作在单链表里删除一个给定节点。假设你有单链表的头指针head现在想删除某个节点p标准的做法是必须先找到p的前驱节点pre然后把pre-next p-next最后释放p。问题来了如果这个链表是单向的p自己根本不知道前驱在哪里你只能从头遍历才能拿到pre。这意味着一次删除操作的时间复杂度是 O(n)而链表本身的价值在于动态插入和删除配合上 O(n) 的查找前驱整个删除操作的体验会变得很奇怪。更麻烦的是循环单链表。当链表是循环结构时尾节点的next会指向头节点遍历结束条件要从“等于 NULL”变成“等于 head”。这时候如果要找尾节点的前驱依然是绕圈遍历。我见过很多实验报告里写“单链表的基本操作”一到删除节点就会写出二重循环原因就是没有解决“向前看”这个能力。双向链表通过给每个节点增加一个prev指针把单向的链变成双向的链让任意一个节点都能直接找到前驱和后继删除不需要再从头找前驱这也是它最核心的工程价值。1.2 双向链表的节点结构与数据布局双向链表的节点定义非常直观以 C 语言为例typedef struct DNode { int data; struct DNode *prev; struct DNode *next; } DNode;每个节点有两个指针prev指向直接前驱next指向直接后继。如果把链表画出来大概是这样的形状NULL -- head - node1 - node2 - ... - tail -- NULL中间这些双向箭头表示每个节点都有两个方向的链接。这种结构带来的第一个好处是从任意节点出发都能以 O(1) 的时间拿到前驱和后继。第二个好处是如果需要从尾到头遍历直接沿着prev走就行不需要像单链表那样先反转再遍历。内存布局上双向链表比单链表每个节点多一个指针字段。在 64 位系统里一个指针占 8 字节如果一个链表有 100 万个节点相当于多占用 8MB 左右内存。这个开销在服务器或桌面端通常可以接受但在嵌入式设备上需要认真衡量。这也是为什么嵌入式内核里常见的是另一种侵入式链表设计后面第 3 节我会专门说。1.3 带头结点和不带头结点的取舍双向链表和单链表一样有两种常见布局带头结点和不带头结点。带头结点是指链表最前面有一个固定的哑节点dummy node它不存储实际数据主要价值是简化边界处理。用带头结点时空表的判断条件统一写成head-next NULL在表头插入和删除时不用考虑“头指针本身要不要变更”。不带头结点时第一个节点就是实际数据节点空表和空链表的判断要写head NULL并且头插或删除首节点时可能要重新赋值head。我个人的经验是在工程项目和考试里除非题目明确要求“不带头结点”否则优先带头结点。带头结点不是性能优化而是逻辑简化。热词里反复出现“不带头结点的单链表”大多是课程作业里为了考察边界处理能力而设置的条件。真正到了实际项目多数内核和框架里的链表实现都带有哑节点或环形头节点目的就是让代码少一些if (head NULL)之类的分支。双向链表带头结点之后插入删除逻辑几乎可以无差别地处理“第一个位置”和“最后一个位置”这是它带来的最大红利。2. 双向链表的核心操作拆解插入、删除、遍历、逆置2.1 插入操作的“先搭桥再接线最后收尾”在双向链表的任意位置插入一个新节点核心逻辑是四步。假设现在要在节点p的后面插入节点ss-next p-next; s-prev p; if (p-next ! NULL) { p-next-prev s; } p-next s;为什么顺序不能乱如果先执行p-next s那么原本p的后继节点就丢失了后面再想让它指向s就找不到对象。正确的思路是先用s-next把原来的后继“接管”过来再用s-prev锁定前驱p接着让原来后继的prev回指s最后才改p-next。你可以把这两条链接想象成两根电线要先接好新线再拆旧线否则会断电。如果要在p的前面插入逻辑对称s-prev p-prev; s-next p; if (p-prev ! NULL) { p-prev-next s; } p-prev s;这里尤其要注意如果是带头结点的链表p是头结点时p-prev本来就是 NULL不用额外处理。如果是不带头结点p是首节点时p-prev为 NULL条件判断能帮我们跳过回接操作。很多新手容易漏掉这个判断导致NULL-next s直接段错误。2.2 删除操作的双向指针回接删除节点p是双向链表的高光操作因为不需要像单链表那样找出前驱。直接记录它的前驱和后继然后让它们互相连接即可if (p-prev ! NULL) { p-prev-next p-next; } if (p-next ! NULL) { p-next-prev p-prev; } free(p);这段代码有个关键点两个if分别处理p是头节点和p是尾节点的情况。如果p是唯一的实际数据节点那么p-prev和p-next都可能为 NULL这时两个if都不执行链表就变成了空链表。如果带头结点那么第一个if一定会有p-prev指向头结点删除首数据节点时头结点也会自动接上第二个数据节点非常干净。还有一种情况是删除“当前节点后还需要继续遍历”。如果你在循环里删除节点一定要先把next存下来再执行free。否则free之后你再访问p-next就是访问已释放内存。DNode *nextNode p-next; deleteNode(p); p nextNode;2.3 遍历、逆序遍历与逆置遍历双向链表和单链表一样简单正向遍历从head-next开始沿着next一直走for (DNode *cur head-next; cur ! NULL; cur cur-next) { // 处理 cur-data }反向遍历则从tail开始沿着prev走这是单链表做不到的。很多热词里都有“链表遍历”可以说双向链表的遍历是“前前后后自由探索”在需要从后往前找数据时特别占优势。逆置双向链表则比单链表更“对称”。单链表逆序通常用头插法从头到尾依次把节点摘下再插到头部双向链表逆序可以更暴力遍历每个节点交换它的prev和next最后把头指针和尾指针互换。因为每个节点本身就是对称的交换指针等价于把整条链的方向翻转。DNode *right head; while (right ! NULL) { DNode *tmp right-prev; right-prev right-next; right-next tmp; right right-prev; // 这里要继续向左走也就是原来的 next }我见过有人把单链表的头插法硬套到双向链表上结果指针改得一团乱。其实双向链表逆置的核心就是逐节点交换指针然后用一个临时变量记录方向不涉及“重新链接”的复杂操作。Python 写“python单链表逆序”的思路会用到类似的引用交换只不过把指针换成了对象属性。2.4 一个可以直接跑起来的 C 语言综合示例这里给一份带注释的完整实现包含了初始化、头插、尾插、删除、打印、逆置。可以直接复制到本地运行。#include stdio.h #include stdlib.h typedef struct DNode { int data; struct DNode *prev; struct DNode *next; } DNode; // 初始化带头结点的双向链表 DNode *initList(void) { DNode *head (DNode *)malloc(sizeof(DNode)); head-prev NULL; head-next NULL; return head; } // 头插 void insertAtHead(DNode *head, int x) { DNode *s (DNode *)malloc(sizeof(DNode)); s-data x; s-prev head; s-next head-next; if (head-next ! NULL) { head-next-prev s; } head-next s; } // 尾插 void insertAtTail(DNode *head, int x) { DNode *cur head; while (cur-next ! NULL) { cur cur-next; } DNode *s (DNode *)malloc(sizeof(DNode)); s-data x; s-prev cur; s-next NULL; cur-next s; } // 删除第一个值为 x 的节点 void deleteByValue(DNode *head, int x) { for (DNode *cur head-next; cur ! NULL; cur cur-next) { if (cur-data x) { if (cur-prev ! NULL) { cur-prev-next cur-next; } if (cur-next ! NULL) { cur-next-prev cur-prev; } free(cur); return; } } } // 正向打印 void printList(DNode *head) { for (DNode *cur head-next; cur ! NULL; cur cur-next) { printf(%d , cur-data); } printf(\n); } // 逆置交换每个节点的 prev 和 next void reverseList(DNode *head) { DNode *cur head; while (cur ! NULL) { DNode *tmp cur-prev; cur-prev cur-next; cur-next tmp; cur cur-prev; // 原来的 next } // 带头结点时头指针始终不变但 head 的 next 需要指向新的首节点 // 上面的循环已经处理了 head 的 next/prev 交换 } int main(void) { DNode *head initList(); insertAtHead(head, 1); insertAtHead(head, 2); insertAtTail(head, 3); printList(head); // 2 1 3 deleteByValue(head, 1); printList(head); // 2 3 reverseList(head); printList(head); // 3 2 return 0; }注意这里的reverseList是把整个带头结点链表的head也纳入交换范围。由于head的prev原本是 NULL交换后head-next变为 NULLhead-prev指向原来的尾节点打印还是从head-next开始的话会失效。更稳妥的逆置是在带头结点时只交换实际数据节点最后让头结点指向原来的尾节点。这里为了演示“逐节点交换”的思路用了最简写法实际工程里我会写成单独处理头结点的版本避免踩空。这个细节也是我面试时经常问别人的点。3. 多语言落地C/C/Java/Python/嵌入式中的双向链表写法3.1 C 语言结构体与手动内存管理C 语言的双向链表最接近底层也最能暴露问题。节点用struct定义内存用malloc/free管理。写 C 版本时你脑子里要时刻清楚每个节点都是一块堆内存谁负责释放释放完有没有指针还引用它。C 语言里没有引用计数也没有垃圾回收所以删除节点后其他节点中指向它的指针必须立即修正否则就是悬垂指针。C 语言还有一个常见坑结构体链表基本语法不熟的人容易在函数参数上传错。如果要在函数里修改头指针本身必须传二级指针或者用带头结点的方式。这也是面试里“链表插入”题的标准考点。我的习惯是C 语言里一律带头结点这样函数参数只需要一级指针代码维护成本低很多。void insertAtHead(DNode *head, int x) { // head 是带头结点的链表头不需要修改 head 本身 }如果题目要求“不带头结点的单链表”那么头插必须写成void insertAtHead(DNode **headPtr, int x) { DNode *newNode (DNode *)malloc(sizeof(DNode)); newNode-next *headPtr; *headPtr newNode; }这组对比能帮你理解为什么很多工程代码都把头结点抽象出来少一个**少很多心理负担。3.2 C 的 std::list 与手写封装时的浅拷贝问题C 标准库里有一个现成的双向链表容器std::list它的实现就是双向链表。用std::list时你可以直接push_back、pop_front、insert、erase完全不用自己操作指针。但很多人不知道的是std::list的迭代器也支持和--因为它内部就是双向链表结构。如果要在 C 里手写双向链表有两个明显比 C 语言复杂的问题一是构造函数和析构函数要处理好深拷贝二是赋值运算符重载。假设你对一个自定义List对象执行了默认拷贝两个对象会共享同一串节点析构时同一块内存被delete两次这是 C 里非常经典的“浅拷贝双释放”问题。class List { Node *head; public: List(const List other) { // 必须深拷贝整条链表 } ~List() { // 遍历 delete 每个节点 } };如果你只是自己玩建议直接用std::list省心如果你是在做课程设计或面试题一定要手动实现一次深拷贝和析构否则在 LeetCode 风格的环境里跑不出现象在真实工程里就直接崩给你看。3.3 Java LinkedList 的内部节点与双向迭代Java 的java.util.LinkedList底层就是一个双向链表。源码里的节点是一个静态内部类private static class NodeE { E item; NodeE next; NodeE prev; Node(NodeE prev, E element, NodeE next) { this.item element; this.next next; this.prev prev; } }LinkedList有first和last两个节点引用对应头尾。它的listIterator支持hasNext、next和hasPrevious、previous原因就是双向链表天然支持双向遍历。很多人在 Java 里用LinkedList只是当队列用其实它的remove(Object)和set操作都利用了节点前后连接不需要像ArrayList那样移动元素。写 Java 双向链表时内存管理不再需要你手动释放但需要注意“对象引用”形成的强引用链。如果一个节点被删除了要主动把它的prev、next、item置为null否则对象无法被 GC 完整回收。标准库源码里就专门做了这个清理很多人自己实现时反而忽略了。3.4 Python 对象引用式双向链表Python 没有 C 语言意义上的指针但对象引用和指针在链表操作里的逻辑完全一样。你可以这样写class DNode: def __init__(self, data): self.data data self.prev None self.next None def delete_node(p): if p.prev: p.prev.next p.next if p.next: p.next.prev p.prevPython 版本的好处是代码非常短缺点是对象属性访问比 C 的指针操作慢得多所以刷题或生产环境里海量链式节点并不算高效。热词里有“python单链表逆序”很多人用 Python 刷链表时会被None判断绕晕其实只要画图理清“谁是谁的前驱”语言差异就消失了。Python 里还有一个常见坑如果节点是自定义对象两个节点互相引用有可能形成循环引用。虽然现代 CPython 的垃圾回收已经能处理循环引用但在追求实时性的场景里尽量避免构造不必要的互相引用。3.5 嵌入式内核链表的侵入式设计嵌入式场景下内存极其宝贵传统“数据域 指针域”的双向链表每个节点都要单独分配内存且要为每种数据类型重复写一遍链表操作。Linux 内核采用了一种更高级的做法让链表节点内嵌到业务结构体里。struct list_head { struct list_head *next, *prev; }; struct person { char name[32]; int age; struct list_head list; };struct person里包含一个list_head成员链表操作只操作这个嵌入的list_head业务数据通过container_of宏从list_head反推回宿主结构体。这种设计是侵入式的因为业务结构体必须主动“长出”一个链表节点。它的最大好处是一套链表通用代码可以服务任意类型的结构体且节点内存和业务对象内存是同一块不需要二次分配。嵌入式里很多时候用循环双向链表也就是head的prev指向尾节点、尾节点的next指向head遍历一圈回到原点非常适合实现轮询队列。如果你只学过教科书里的纯数据结构式链表第一次看内核链表会觉得别扭。但理解了这种“节点嵌入”的思想后你会明白链表真正的价值是“把任意对象组织起来”而不是绑定在某一种int或字符串数据上。4. 链表操作的常见坑位内存、空指针与复杂删除4.1 谁申请、谁释放所有权边界要划清链表的节点只要是malloc或new出来的就必须有明确的释放责任。最常见的内存泄漏场景是插入了一大串节点退出函数前只free了头结点剩下的节点全部丢了。正确销毁链表需要从头到尾逐个free也就是“边遍历边释放”。void destroyList(DNode *head) { DNode *cur head; while (cur ! NULL) { DNode *next cur-next; free(cur); cur next; } }这里的next必须在free之前保存否则就是一个明显的 use-after-free。我见过很多写了两年 C 的人也偶尔犯这个错解决办法就是把这句先写出来。4.2 空表、单节点与头尾节点的边界矩阵很多 bug 不是主流程写错而是边界条件没考虑到。下面这张表是我整理的双向链表关键边界场景写代码时可以对照着过一遍场景插入操作注意点删除操作注意点空表head-next为 NULL插入后要更新head-next删除时没有节点可删直接返回只有 1 个数据节点在它前后插入都要处理prev和next的 NULL删除后链表变为空表在表头插入带头结点时简单不带头时头指针要更新删除首节点后头指针或头结点要指向第二个节点在表尾插入找到尾节点设置tail-next s删除尾节点时要把前驱的next置 NULL在中间任意位置按“插入四步”无差别处理按“双指针回接”无差别处理我在代码里会专门写一个assert函数在每次插入删除后校验链表的完整性。如果链表是双向的那么对于任意节点cur必须满足cur-next NULL || cur-next-prev cur同时cur-prev NULL || cur-prev-next cur。这个性质可以帮你自动发现一半以上的指针错乱。4.3 删除节点的顺序错误会在什么时候爆雷很多人学双向链表时都知道要先回接前后节点再释放当前节点。但实际写代码时顺序不对的情况经常发生。看看这段错法free(p); if (p-prev ! NULL) { p-prev-next p-next; } if (p-next ! NULL) { p-next-prev p-prev; }先释放p然后马上访问p-prev和p-next。这等于在已经被释放的内存上读数据。在 Debug 模式下可能运气好还能读到旧值在 Release 模式下编译器可能直接优化出未定义行为程序表现为随机崩溃或数据错乱。正确的顺序必须是先改其他节点的指针最后再释放当前节点。这不是风格问题是正确性问题。同理插入时如果先改了p-next导致后续没有记录原来的后继地址同样会丢链。这里最重要的经验就是链表的链接操作本质上是在改图改图之前先保存会受影响的下一个节点地址。4.4 调试链表的工具打印、断言和画图我调试链表有三个习惯。第一个是写一个专门的打印函数不仅打印data还要打印prev和next的地址。这样能直观看到哪个节点指向了错误的位置。void debugPrint(DNode *head) { for (DNode *cur head; cur ! NULL; cur cur-next) { printf(node%p prev%p next%p data%d\n, (void *)cur, (void *)cur-prev, (void *)cur-next, cur-data); } }第二个习惯是在关键操作后调用assert校验双向一致性。第三个习惯是画图不是用工具画多漂亮的图而是拿一张纸把head、n1、n2的格子画出来每一步改动都用橡皮擦掉旧线、画上新线。链表操作的指针改动很少超过 4 条线画图之后顺序错误几乎不可能发生。我面试别人时看到候选人能主动画图就知道他对链表是有真正理解的。5. 双向链表的经典应用从 LRU 缓存到嵌入式内核5.1 LRU 缓存为什么离不开双向链表LRULeast Recently Used缓存是比较热门的数据结构题。它的要求是在 O(1) 时间内根据 key 查 value在 O(1) 时间内淘汰最久未使用的条目。哈希表负责 O(1) 查找双向链表负责维护访问顺序。具体做法是用哈希表存 key 到链表节点的映射链表头部存最近访问过的节点尾部存最久未访问的节点。每次访问一个 key就把对应节点从当前位置摘下来放到链表头部。每次缓存满时删除链表尾部的节点。这个“摘下并放到头部”的操作在单链表里因为要找到该节点的前驱复杂度是 O(n)在双向链表里节点自带prev摘下和插入都是 O(1)。这就是 LRU 选择双向链表的原因。这里还有一个小技巧可以使用 head 和 tail 两个哑节点分别表示链表边界这样插入和删除时就不需要维护头尾指针的空判断。很多工业实现里 LRU 的头尾哑节点都是固定不动的节点在它们之间移动。我第一版写 LRU 时没有用哑节点结果每次删除尾部都要判断“是不是删到了尾节点”代码里全是分支。加了哑节点后主逻辑清爽了一大截。5.2 嵌入式内核的 list_head把链表装进业务结构体嵌入式里最常见的就是循环双向链表 内嵌list_head。前面第 3 节给出了结构定义这里说说它的典型操作。Linux 内核里定义了list_add、list_del、list_for_each_entry等宏它们操作的核心就是struct list_head。一个简单但完整的嵌入式链表示例#include stdio.h #include stdlib.h #include list.h // 假设内有 list_head、list_add、list_del、container_of struct person { char name[32]; int age; struct list_head list; }; void show_person(struct person *p) { printf(name%s age%d\n, p-name, p-age); } int main(void) { struct list_head head; INIT_LIST_HEAD(head); struct person p1 {Alice, 20, {NULL, NULL}}; struct person p2 {Bob, 30, {NULL, NULL}}; list_add_tail(p1.list, head); list_add_tail(p2.list, head); struct list_head *pos; list_for_each(pos, head) { struct person *p container_of(pos, struct person, list); show_person(p); } return 0; }这种写法的精妙之处在于链表操作和业务数据完全解耦。你在person结构体里放多少个list_head就能让同一个对象同时出现在多少条链表里。比如一个设备节点既可以挂进设备链表也可以挂进同类型设备的快查链表不需要复制数据。5.3 撤销/重做、任务队列、日志缓冲常见应用地图除了 LRU双向链表还有很多实际场景文本编辑器的撤销/重做功能。每次操作生成一个状态节点形成一个从“最初状态”到“当前状态”的双向链。撤销就是向prev方向移动游标重做就是向next方向移动游标。如果新增操作就把当前游标后面的所有分支清理掉再追加新节点。嵌入式任务队列。多个任务通过循环双向链表组成就绪队列调度器能从任意位置摘除任务也能在尾部追加任务。日志缓冲或消息队列。当日志需要从尾部快速回读时双向链表的反向遍历能力很省心。浏览器页面前进后退。这是最经典的比喻每一个浏览过的页面是一个节点当前页是游标后退走prev前进走next和撤销/重做本质相同。5.4 什么时候不该用双向链表双向链表并不是万金油。每个节点多一个prev指针意味着更大的内存占用频繁动态分配节点意味着碎片化和分配开销。如果你只需要在尾部插入、头部删除其实用一个数组模拟的队列更合适。如果数据量小且频繁随机访问std::vector或ArrayList的缓存友好型线性存储通常比链表快得多。链表真正的优势场景是插入删除频繁并且插入删除位置常出现在“知道某个节点但不知道它的前驱/后继位置”的时候——这时候双向链表才有不可替代的价值。我在实际项目里会先问自己三个问题数据规模多大是否需要反向遍历是否需要从任意节点摘除如果三个答案里有至少两个是“是”才考虑用双向链表。6. 写在最后我的双向链表学习与面试心得6.1 从单链表迁移到双向链表的核心心法很多人学完单链表再学双向链表觉得难是因为他们还在用单链表的“单向思维”思考双向结构。我的核心心法只有一句话把每个节点看成一份“带撤销功能”的协议prev和next是协议里的两个字段改动时必须按照顺序执行“先保存、再连接、后释放”。单链表插入只需要改两个指针双向链表插入需要改四个指针本质上还是那两个动作只是数量翻倍。迁移时最好自己从零实现一遍初始化、尾部插入、按值删除、按位置插入、逆置、销毁。每一个操作都画一张图然后对照代码检查“图上画的每条线代码里是否都有对应语句”双向链表的指针操作很快就变得和写if一样自然。6.2 值得练的几道双向链表题目如果你正在准备笔试和面试我建议认真练这几道题删除有序双向链表中的重复节点要求空间 O(1)。将双向链表逆置要求不能新开链表。判断一个带头结点的循环双向链表是否对称即从头遍历和从尾遍历结果一致。在双向链表中实现O(1)时间在指定节点前插入。用双向链表设计一个 LRU Cache并实现get和put。这些题都能在 LeetCode 或经典教材里找到影子。做的时候不要只看题解要亲手把节点地址的变化画出来过一周再盲写一遍。链表题是最吃手感的题型没有捷径。6.3 一个让我少写一半 bug 的习惯最后分享一个非常实用的习惯给链表写一个check函数在每次插入和删除之后调用。不要嫌它多写几行它真的能帮你省下大量调试时间。void check(DNode *head) { DNode *cur head; while (cur ! NULL) { if (cur-next ! NULL cur-next-prev ! cur) { fprintf(stderr, link error: cur%p, cur-next%p\n, (void *)cur, (void *)cur-next); abort(); } if (cur-prev ! NULL cur-prev-next ! cur) { fprintf(stderr, back link error: cur%p, cur-prev%p\n, (void *)cur, (void *)cur-prev); abort(); } cur cur-next; } }一旦违反双向链表的一致性程序立刻崩溃并把当前节点地址打印出来配合地址比对基本能一次定位到是哪个操作写错了。我在自己项目里一直保留这个函数甚至会在发布版里也开启。用最笨的校验换最稳的代码这是双向链表给我的最深刻经验。