直接进入正题。这是这个系列的第十篇前面几篇我分别讲了链表是什么、为什么需要链表、单链表的创建遍历删除释放今天这篇聚焦双向链表里最常用到的三个操作插入、查询、修改。之所以专门把这三个操作拿出来单讲是因为它们覆盖了双向链表 90% 以上的使用场景。你去看期末卷子、看考研真题、看企业笔试题考来考去基本就是这三种操作再加一个删除。而双向链表和单链表最大的不同就在指针怎么倒腾。很多同学写代码喜欢直接背模板结果一到换结点顺序、加个条件、处理头尾边界的时候就挂说白了就是对指针操作的本质没想透。这篇我会把插入、查询、修改揉碎了讲重点说清楚每一步为什么要这么做以及哪些坑我当年都踩过。1. 先把双向链表的结构吃透后面操作才不会懵1.1 双向链表和单链表到底差在哪儿单链表的结点只有两个部分数据域和指向下一个结点的指针域。所以遍历的时候只能老老实实从头往后走想回头就得重新从头找非常憋屈。双向链表每个结点多了一个指向前一个结点的指针也就是prior 指针和next 指针各管一边。这样带来的直接好处是从任意一个结点出发既可以向前走也可以向后走已知某个结点想找它的前驱结点直接p-prior就行时间复杂度 O(1)。单链表想找前驱必须从头遍历O(n) 起步。代价也很明显每个结点多占用一个指针的内存插入、删除时需要调整的指针数量翻倍。所以双向链表不是更高级的表而是更灵活的表。你要处理多级菜单、需要频繁回退操作、需要维护元素的先后顺序又想快速找到前驱这种场景用双向链表对路如果纯粹是顺序存储、倒序读文件单链表就够用了。1.2 结构定义和头结点的细节直接影响后续所有代码定义双向链表结点的标准写法基本是这样的typedef struct DNode { int data; // 数据域这里用 int 举例 struct DNode *prior; // 指向前驱结点 struct DNode *next; // 指向后继结点 } DNode, *DLinkList;这里面有个关键点prior 指向的是上一个结点不是上一个结点的数据域。新手最常犯的错就是赋值的时候写成p-prior q-data直接把地址给了 int编译就报错或者不报错但运行时崩掉。再一个问题是头结点。我强烈建议带头结点。带头结点的意思是一个真正的数据结点之前先放一个空结点它的 data 不存有效数据prior 和 next 初始为 NULL。带头结点的好处有三个空表的判断统一了。不管表空不空头结点永远存在表空时head-next NULL一目了然。头部插入和中间插入代码逻辑一致不需要为 第一个结点 单独写分支。删除第一个数据结点时不需要额外更新外部头指针。有人习惯不带头结点认为省一个结点内存更高效。理论上没错但代价是代码里到处要处理边界插入删除前都要判断是不是第一个。我个人的经验是刷题和写工程代码时带头结点都能显著降低 bug 率。哪怕面试官说可以用不带头结点的我也会在函数内部临时加一个哑结点再操作最后再移除。2. 插入操作四步指针调整顺序错一步整个链就废了2.1 核心思路就一条先把新结点的左右邻居拴好再拆旧链双向链表插入的核心逻辑是在某个结点p后面插入一个新结点s。无论头插、尾插还是随机位置插本质都是同一套操作区别只在于你先把p定位到哪儿。标准的四步操作是s-next p-next; // 第1步新结点的 next 指向 p 原来的后继 if (p-next ! NULL) // 第2步如果 p 后面原来有结点把它反向指到新结点 p-next-prior s; s-prior p; // 第3步新结点的 prior 指向 p p-next s; // 第4步把 p 的 next 指向新结点为什么必须按这个顺序关键在于第1步到第2步之间你利用的是p-next这个旧值来完成新结点和原后继之间的连接。假如你先把p-next修改成s那么第2步再写p-next-prior s时p-next已经变成了新结点s此时s-prior还没设置好就成了s-prior s自己指向自己链表直接错乱。所以口诀是先处理新结点的 next再处理原后继的 prior然后设置新结点的 prior最后才把前驱的 next 指向新结点。这叫让新结点先鹊巢但先别鸠占把两端的联系都接通了再改对外指针。很多教材会省略第2步的判断直接写p-next-prior s。如果p是表尾结点p-next是 NULL那这一行会访问空指针直接段错误。在实际工程里你无法保证调用者传入的p一定不是尾结点所以建议每次都写判断。虽然多一个 if但换来的是健壮性。2.2 头插、尾插和指定位置后插一套代码给你仨以此为基础头插就是在头结点后面插入。假设头结点指针是L那么DNode *s (DNode *)malloc(sizeof(DNode)); s-data x; s-next L-next; if (L-next ! NULL) L-next-prior s; s-prior L; L-next s;尾插就是先找到尾结点tail再执行和上面一模一样的那四步只是把p换成tail。指定位置后插稍微复杂一点你得先找到第i个位置的结点p然后在它后面插入。查找的逻辑后面章节详聊插入部分不用变DNode *p GetElemByIndex(L, i); // 找到第 i 个结点 if (p NULL) return false; DNode *s (DNode *)malloc(sizeof(DNode)); s-data x; s-next p-next; if (p-next ! NULL) p-next-prior s; s-prior p; p-next s;我当年学这块时最不能理解的就是为什么尾插和头插代码差不多还要分开写两个函数。后来写项目才明白头插和尾插的应用场景完全不同头插构建的链表顺序和输入序列相反常用于栈、撤销列表尾插构建的链表顺序和输入一致常用于队列、日志。两个函数名字清晰调用处看名字就知道链是什么顺序可读性比一个万能函数高得多。2.3 插入操作里的三个坑每一个都是血泪教训坑一malloc 之后没有检查返回值。嵌入式环境、长时间运行的服务端程序内存申请失败是真实存在的。如果s为 NULL下面给s-data赋值直接越界。严谨代码应该写DNode *s (DNode *)malloc(sizeof(DNode)); if (s NULL) return false;刷题时可以不写但面试官问你这段代码有没有问题你答出这一条印象分直接拉满。坑二在一个链上同时用两个指针找位置结果其中一个没更新。我做过一个需求要在一个有序双向链表里插入一个结点找到第一个比它大的结点前插入。当时的代码是先遍历找位置然后用p-prior拿前一个再插入。问题在于遍历过程中用的是临时指针cur插入时又要强调在 p 前插入还是在 p 后插入经常绕晕。后来我总结了一套稳健做法统一只在某个结点的后面插入如果要在它前面插入就先拿到它的前驱prev p-prior再执行在 prev 后面插入这样逻辑永远是同一套代码可复用率高。坑三头结点本身的 prior 和 next 被乱改。头结点的 prior 应该永远保持 NULL头结点的 next 永远指向第一个数据结点。有人图省事让头结点的 next 指向最后一个结点做成循环链表又忘记了在遍历时加循环判断条件跑起来要么死循环要么漏元素。除非你明确要做循环双向链表否则头结点的 prior 必须一直置 NULL。3. 查询操作双向链表的慢慢得有道理3.1 按位置查找和按值查找的标准实现查询说白了就是遍历。按位置查找是给一个 index返回该位置结点的指针DNode *GetElemByIndex(DLinkList L, int i) { if (i 0) return NULL; DNode *p L-next; // 从头结点后的第一个数据结点开始 int j 1; while (p ! NULL j i) { p p-next; j; } return p; }按值查找是给一个值返回第一个匹配的结点DNode *GetElemByValue(DLinkList L, int e) { DNode *p L-next; while (p ! NULL p-data ! e) { p p-next; } return p; }这两个函数我都是把返回值设计成DNode *指针而不是 bool。原因是查询结果往往要被改值、被删除、被当作插入位置去用把指针返回出来调用方可以继续操作只返回 bool 的话调用方还要再遍历一次才能拿指针白白浪费一次 O(n) 的遍历。3.2 为什么说双向链表查找不一定更快市面上很多文章吹双向链表查找效率高这是不严谨的。从渐进复杂度看双向链表按位置、按值查找的时间复杂度都是 O(n)和单链表没有任何区别。那双向的优势在哪在已知结点位置之后的找前驱操作。单链表已知p想知道它的前驱q只能从头遍历因为单链表每个结点只记录后面是谁。双向链表直接p-prior一步到位。所以正确表述是双向链表在由后往前的查询场景中占优。举例我要在一个链表中删除值为 5 的结点。单链表需要维护一个pre指针边移动边记录前驱双向链表则直接找到p然后p-prior-next p-next就行。代码量少一半出错率也低。3.3 双端搜索和倒序查询的实用技巧正因为双向链表可以往前走所以在一些场景中可以写双指针搜索DNode *front L-next; DNode *rear tail; // 需要提前记录尾结点 while (front ! NULL rear ! NULL front ! rear front-prior ! rear) { if (front-data target) return front; if (rear-data target) return rear; front front-next; rear rear-prior; }这个技巧在查找距离某个端点更近的目标时效率不错。假设链表有 1000 个结点目标在第 998 个位置从尾部开始找两步就找到从头部要遍历 998 次。现实中有这种需求的场景挺常见的比如文本编辑器里定位文档末行的某个关键字。不过要提醒一句双端搜索虽然好但前提是你得维护一个尾指针 tail同时要处理链表只有一个结点、两个结点等边界情况代码复杂度比单端遍历略高。实际工程中如果链表规模不大几百个结点内用单端遍历完全够用不要为了炫技把自己的代码写得很难维护。我一直跟学弟学妹说算法优化的前提是先能跑对跑对之后再考虑要不要快。4. 修改操作先定位再改数据但别乱改指针4.1 三步走定位、校验、赋值双链表的修改听起来很复杂其实大部分情况下就是查询 赋值。举个例子把链表中第一个值为 3 的结点的 data 改成 10DNode *p GetElemByValue(L, 3); if (p NULL) { printf(未找到目标结点\n); return false; } p-data 10;就这么简单对就这么简单。因为修改 data 域不涉及结点之间的连接关系不需要倒腾指针。但要加一个校验意识修改前必须确认链表非空、目标结点存在。尤其拿到题目说修改第 i 个结点i可能越界GetElemByIndex会返回 NULL不判断就解引用必然崩。4.2 修改 data 域和修改指针域是两码事很多初学者会把修改结点理解成把结点换掉。这是两类不同的操作修改 data 域值变了但结点在链表中的物理位置不换前后指针关系不变。修改指针域这是重排列链表的操作本质上是先删后插、或先插后删。举个例子链表中有一个结点存了值 5我想把它挪到头结点后面。如果只改 data那只是把另一个结点的值覆盖成数据如果想让这个node跑最前面需要把 node 从原来位置摘下来再用头插法插回去。所以当你听到修改链表这个词一定先分辨对方说的是改数据还是改结构。期末考试和习题集里最爱在这个地方设坑题目写修改结点值考查的是通过查询定位后改 data题目写调整结点顺序考查的是指针操作。4.3 需要保持有序性的修改要额外注意如果你维护的是一个有序双向链表比如按 data 从小到大排那修改 data 就不只是p-data newValue这么简单了。改完以后整个链表的有序性可能被破坏。比如链表是 1, 3, 5, 7你把 5 改成 2那么链表变成 1, 3, 2, 7不再有序。如果后续用它做二分查找或作为优先队列结果就错了。正确处理有两种思路第一种先删除目标结点再以新值重新插入到正确位置复杂度 O(n)。第二种允许结点先无序修改完成后对整条链表做一次排序复杂度 O(n log n)。第一种思路更常用因为只影响到一个结点的位置而且代码逻辑清晰。缺点是如果连续修改大量结点频繁删除插入的开销不小。第二种思路适合批量改值后统一排序的场景。顺便说一个细节修改 data 时如果 data 是结构体比如存了学号和成绩注意别写p-data newStudent就以为万事大吉。结构体里如果带指针比如 char *name那涉及到浅拷贝深拷贝的问题这个很容易让程序出现重复释放或悬空指针。用链表存复杂结构体时建议根据业务写专门的 set 方法别直接给整个结构体赋值。5. 综合示例把一个完整的双向链表跑起来5.1 一套可直接抄走的完整代码我把上面讲的串起来写一个完整可运行的框架覆盖创建、插入、查询、修改、销毁。代码我实测能跑你复制到本地把 main 函数改一改就能用。#include stdio.h #include stdlib.h #include stdbool.h typedef struct DNode { int data; struct DNode *prior; struct DNode *next; } DNode, *DLinkList; // 初始化创建头结点 bool InitList(DLinkList *L) { *L (DNode *)malloc(sizeof(DNode)); if (*L NULL) return false; (*L)-prior NULL; (*L)-next NULL; return true; } // 尾插法在尾部插入新结点 bool InsertAtTail(DLinkList L, int e) { DNode *tail L; while (tail-next ! NULL) tail tail-next; DNode *s (DNode *)malloc(sizeof(DNode)); if (s NULL) return false; s-data e; s-next NULL; s-prior tail; tail-next s; return true; } // 头插法在第一个数据结点之前插入 bool InsertAtHead(DLinkList L, int e) { DNode *s (DNode *)malloc(sizeof(DNode)); if (s NULL) return false; s-data e; s-next L-next; if (L-next ! NULL) L-next-prior s; s-prior L; L-next s; return true; } // 在指定结点 p 后面插入结点 s bool InsertAfterNode(DNode *p, DNode *s) { if (p NULL || s NULL) return false; s-next p-next; if (p-next ! NULL) p-next-prior s; s-prior p; p-next s; return true; } // 按位置查找返回第 i 个数据结点 DNode *GetElemByIndex(DLinkList L, int i) { if (i 1) return NULL; DNode *p L-next; int j 1; while (p ! NULL j i) { p p-next; j; } return p; } // 按值查找返回第一个值为 e 的结点 DNode *GetElemByValue(DLinkList L, int e) { DNode *p L-next; while (p ! NULL p-data ! e) { p p-next; } return p; } // 修改把第 i 个结点的值改为 e bool ModifyByIndex(DLinkList L, int i, int e) { DNode *p GetElemByIndex(L, i); if (p NULL) return false; p-data e; return true; } // 修改把第一个值为 oldVal 的结点改为 newVal bool ModifyByValue(DLinkList L, int oldVal, int newVal) { DNode *p GetElemByValue(L, oldVal); if (p NULL) return false; p-data newVal; return true; } // 正向打印 void PrintList(DLinkList L) { DNode *p L-next; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); } // 反向打印用来验证 prior 指针是否正确 void PrintListReverse(DLinkList L) { DNode *p L; while (p-next ! NULL) p p-next; while (p ! L) { printf(%d , p-data); p p-prior; } printf(\n); } // 销毁链表 void DestroyList(DLinkList *L) { DNode *p *L; while (p ! NULL) { DNode *tmp p; p p-next; free(tmp); } *L NULL; } int main() { DLinkList L; InitList(L); InsertAtTail(L, 1); InsertAtTail(L, 2); InsertAtTail(L, 3); InsertAtTail(L, 5); InsertAtHead(L, 0); printf(正向打印: ); PrintList(L); // 0 1 2 3 5 printf(反向打印: ); PrintListReverse(L); // 5 3 2 1 0 DNode *p GetElemByIndex(L, 3); printf(第3个结点的值: %d\n, p-data); // 2 ModifyByIndex(L, 3, 99); printf(修改后正向打印: ); PrintList(L); // 0 1 99 3 5 ModifyByValue(L, 3, 33); printf(修改后正向打印: ); PrintList(L); // 0 1 99 33 5 // 在值为99的结点后面插入新结点100 DNode *target GetElemByValue(L, 99); DNode *s (DNode *)malloc(sizeof(DNode)); s-data 100; InsertAfterNode(target, s); printf(插入后正向打印: ); PrintList(L); // 0 1 99 100 33 5 DestroyList(L); return 0; }5.2 测试用例设计边界条件是重点考察对象这段代码我特意覆盖了几个典型的测试场景InsertAtHead后检查 0 是否真的排在了最前面。如果头插时忘了处理L-next-prior反向打印就会出问题。PrintListReverse可以交叉验证 prior 指针的完整性。要是插入时 prior 没设对打印结果会对不上。GetElemByIndex(L, 3)验证中间位置查找。ModifyByValue验证第一个匹配值被修改而不是把所有匹配值都改掉。如果你想拿来做实验报告我建议再加这几个边界测试// 空表查询 DNode *p1 GetElemByIndex(L, 0); // 期望 NULL // 越界查询 DNode *p2 GetElemByIndex(L, 999); // 期望 NULL // 修改不存在的值 bool ok ModifyByValue(L, 888, 1); // 期望 false这些边界测试看着简单但能直接暴露一个问题你的 GetElemByIndex 有没有对 i 1 做判断。很多教材代码没写这个判断i 0 时返回值是头结点后续操作就会莫名其妙地动到 head引发难以排查的 bug。5.3 代码中容易被忽略的两个细节第一InitList为什么传的是DLinkList *L而不是DLinkList L因为InitList内部要给头指针分配内存同时要修改调用方手里的头指针变量。C 语言所有参数都是值传递只传DLinkList L的话函数内部修改的只是副本外面依然是指向 NULL 的野指针。所以必须传入指针的指针。这是一个比较隐蔽的坑很多人项目挂了半天查不出来最后发现初始化就没成功。第二DestroyList也要用二级指针。释放完所有结点后如果仅仅把局部指针置 NULL调用方仍然持有已释放的地址之后访问就是野指针。销毁后把*L置成 NULL外界再用这个链表时至少能通过L NULL判断出来。有的代码会犯双重释放的错误第一个地方 free第二个地方又 free 一次。解决办法是每次 free 完顺手置 NULL或者定义一个宏#define SAFE_FREE(ptr) do { free(ptr); (ptr) NULL; } while (0)这个宏在工程上非常实用但刷题时别在代码里写面试官会觉得你太依赖宏操作可读性差。6. 实际应用场景双向链表到底拿来干什么6.1 双向链表多级菜单的实现思路我看到最近网络上双向链表多级菜单这个话题热度不低。其实多级菜单的核心就是树形结构但用双向链表实现时每个菜单结点可以这样设计typedef struct MenuNode { char title[64]; struct MenuNode *parent; // 上级菜单 struct MenuNode *child; // 下级菜单 struct MenuNode *brother; // 同级菜单 } MenuNode;用户在菜单里按返回键就是从当前菜单跳到parent这个操作在双向链表里就是一次cur cur-parent。如果没有parent指针你得从头重新按路径遍历一遍体验非常差。这个场景很适合拿来写数据结构实验报告因为它有真实业务背景不像是为了考试硬编一个链表。可以做成命令行菜单也可以结合 STM32 开发板用 OLED 显示菜单效果直观。这里也给个切入点程序启动时构建菜单树每次按键改变当前索引并重绘屏幕双向链表的parent、child、brother正好对应按键处理的三种分支。6.2 浏览器历史记录、LRU 缓存与文本编辑器的共同点浏览器历史记录的前进后退功能是双向链表的经典教材案例。每次访问新页面往链表尾部插入一个新结点点击后退cur cur-prior点击前进cur cur-next。如果后退以后又访问了新页面需要把当前位置之后的记录全部清掉这就涉及删除尾段的操作。双向链表做这件事比单链表方便得多因为能直接从最后一个结点往前逐个释放。LRU 缓存则是另一个高频考点用哈希表 双向链表。哈希表负责 O(1) 查找双向链表负责 O(1) 删除和移动结点。每次访问一个 key先通过哈希表拿到链表结点再把它移动到链表尾部表示最近使用。淘汰时删除链表头结点。这里的结点移动本质就是我上面讲的先从链上摘下来再尾插回去这对双向链表来说只需要改写几个指针而对单链表你光找要摘结点的前驱就要遍历一次。文本编辑器里的撤销栈、行号缓冲区也会用到双向链表。编辑器要支持光标上移下移、在任意行增删内容天然就是在一个序列中任意位置插入删除的诉求。C 语言实现这个功能时用双向链表存行数据每一行是一个结点行号就是位置。上下移动光标就是cur cur-prior或cur cur-next响应非常快。有人会问这些操作数组也能做为什么用链表答案是数组在中间位置插入删除时需要搬移大量元素而链表只动指针。不过数组在随机访问上碾压链表。所以真正的工程里很少用纯双向链表混合结构更常见。数据结构这门课不是教你把所有东西都换成链表而是教你在适合的场景选对结构。这个是我想反复强调的一点。最后再分享一个小技巧。我运行链表代码时总是习惯写一个反向打印函数。这个函数看似鸡肋但它能非常快地检查 prior 指针是否正确。插入、删除、修改完以后正序打印 逆序打印对照结果一致就说明双向关系没断。很多问题比如插入时忘记设置p-next-prior单看正向打印完全正常一逆序打印就露馅了。在你的实验报告里加上这个验证函数老师看一眼就会觉得你考虑周全。这就是我测试链表类代码的保留节目建议你用起来。