尧图网站建设 
数据结构这关绕不开链表链表这一块双链表又是绕不开的重点。不管你是大一在赶数据结构实验报告还是准备考研408又或者工作中遇到 LRU 缓存这类需要“来回走”的数据结构双链表都是那个躲不过去的基础设施。这篇博文把双链表从设计思路到实操代码、从常见坑位到面试考点一次性讲透适合所有正在学数据结构的同学也适合需要快速捡起来的老手。1. 为什么需要双链表单链表的“单程票”困境1.1 单链表的前驱难题先回顾单链表。每个节点一个 data、一个 next一路朝前。它最大的痛点是想删除中间某个节点 p必须从头遍历找到 p 的前驱。链表规模一大这就是 O(n) 的操作和数组随机访问的 O(1) 一个天上一个地下。更麻烦的是很多实际问题需要“往回倒”——从尾部往头部走单链表连指针都拿不出来。我早先写过一个简易的浏览器历史记录模块用户点“后退”时得从当前页回到上一页。如果用单链表只存 next那你永远知道自己去过哪儿却再也回不去。因为当前节点根本没有 prev 指针。你只能从头重新遍历一遍历史记录找前驱历史一长卡顿就很明显。这个场景直接让我明白单链表的“单程票”设计在回退场景里就是硬伤。1.2 双链表的核心设计思路双链表的改进非常朴素每个节点再加一个 prev 指针指向前一个节点。整条链在逻辑上就是一列双向走廊前进把握 next后退看 prev。代价也很明确每个节点多出一个指针变量的内存典型的空间换时间。内存怎么算以 64 位环境举例一个 int 数据占 4 字节两个指针各占 8 字节光指针就 16 字节。也就是说双链表节点比单链表大概大出一大截。不过现代服务器内存动不动几十 GB这点开销通常可接受换来的是删除、插入在持有目标节点指针时的 O(1) 时间复杂度。到底值不值要看场景需要频繁“往回”操作的场景双链表是首选只做顺序追加、顺序扫描的场景单链表更轻量。这里没有绝对的“谁更好”只有“谁更合适”。2. 双链表的结构定义与基础操作实现2.1 节点结构体怎么定义C语言里的双链表骨架C语言实现双链表核心就是多一个指向前驱的指针。定义一个节点typedef struct DNode { int data; struct DNode *prev; struct DNode *next; } DNode;这里结构体里出现struct DNode是因为 C 语言里结构体不能直接递归使用自己的别名必须用完整的struct DNode来声明指针。如果你开了 typedef也不能在成员声明里直接写DNode *prev编译器在那一刻还不认识 DNode。这是很多初学 C 的同学踩的第一个坑。有了节点还要区分头结点和头指针。头指针是链表的入口变量指向链表的第一个节点头结点是挂在真正数据节点之前的一个哨兵节点data 字段通常存无效值。带头结点的好处是空表判断、插入删除操作统一化不用为“首节点没有前驱”写一坨分支。很多教材会把“头结点”和“首元结点”混着提其实是两个东西必须分清。我的建议是日常练习和考试都带头结点省心。2.2 初始化、遍历与逆序输出先把三个基础动作跑通初始化一个带头结点的空双链表核心是让 head 的 prev 和 next 都指向 NULLDNode *initList() { DNode *head (DNode *)malloc(sizeof(DNode)); if (head NULL) { return NULL; } head-prev NULL; head-next NULL; return head; }malloc 之后一定要判空。这是不少练习代码里没有的步骤但在真实系统中内存申请可能失败不判空后面就是空指针崩溃。顺向遍历很简单从 head-next 开始一路 next 到 NULL 为止void printList(DNode *head) { DNode *cur head-next; while (cur ! NULL) { printf(%d , cur-data); cur cur-next; } printf(\n); }逆序遍历才是双链表的看家本领。先用 cur 走到最后一个节点再一路走 prev 回到 headvoid printReverse(DNode *head) { DNode *cur head; while (cur-next ! NULL) { cur cur-next; } while (cur ! head) { printf(%d , cur-data); cur cur-prev; } printf(\n); }你对比一下单链表单链表逆序输出最笨的办法是每次都从头扫到尾复杂度 O(n²)双链表只需要 O(n)。这个差异在链表长度达到上万的时候就非常明显了。2.3 Python、Java、PHP 怎么写双链表语言差异只是皮很多同学看 C 语言版本觉得指针绕换语言就轻松不少。以 Python 为例class Node: def __init__(self, data): self.data data self.prev None self.next None class DoublyLinkedList: def __init__(self): self.head Node(None) # 哨兵节点Python 的引用本质上就是指针的封装理解逻辑一样只是不用你手动 malloc/free。Java 也类似一个内部类就能表示节点class DNode { int data; DNode prev; DNode next; DNode(int data) { this.data data; } }热词里还看到了 php 双链表。PHP 里写双链表也很直白class DNode { public $data; public $prev; public $next; public function __construct($data) { $this-data $data; $this-prev null; $this-next null; } }语言变了核心就没变每个节点还是 data prev next插入删除还是那把指针操作的逻辑。所以我一直建议双链表的核心不要局限在某一门语言上C 语言把它彻底吃透其他语言就是换皮。3. 插入与删除最考验指针操作的两个环节3.1 在指定节点后插入记住“先绑新链再改旧链”双链表插入的教科书操作是在节点 p 之后插入新节点 s。一共四步s-next p-next; // 第一步新节点的后继指向 p 的旧后继 s-prev p; // 第二步新节点的前驱指向 p if (p-next ! NULL) { // 第三步如果 p 有后继让后继的 prev 指向 s p-next-prev s; } p-next s; // 第四步p 的后继改指向 s为什么这个顺序最关键因为如果先改p-next sp 的原后继就丢了你后面想拿p-next-prev拿到的其实是 s 而不是那个被抛弃的节点链表当场断成两截。所有断链事故根源都是“先动旧链再接新链”。记住八个字先绑新链再改旧链。在 p 之后插入只需要 O(1)不需要遍历这就是双链表的价值。头插法和尾插法都是这个操作的变体。头插法等于在 head 之后插入尾插法则是先遍历到最后一个节点再在它之后插入。尾插因为要走到末尾所以是 O(n)。如果你频繁在尾部追加数据且数据量很大更优做法是维护一个 tail 指针直接指向链表末尾。3.2 删除节点四行核心逻辑与内存释放细节删除 p 的下一节点逻辑同样清晰DNode *del p-next; if (del NULL) { return; // 没有可删的节点 } p-next del-next; if (del-next ! NULL) { del-next-prev p; } free(del);先说为什么删除前要判空如果 p 是最后一个节点它的 next 是 NULL直接给 del 赋 NULL下一步访问 del-next 就直接段错误。这个边界条件在考试写代码时特别容易漏。再说说 double free 的问题。free(del) 之后del 指向的内存已经还给系统如果你后面又写del-next或者再次 free(del)就是非法访问。一个稳妥的习惯是 free 之后立刻把指针置 NULLfree(del); del NULL;很多内存报错看起来莫名其妙最后追查就是 double free 或者 use-after-free。真实的工程环境里这类问题都会被编译器 Sanitizer 或者 Valgrind 抓得明明白白但等你调试到那时候时间已经浪费光了。不如一开始就养成好习惯。3.3 双向循环链表头尾相连后的判空与终止条件双向循环链表是双链表的标准升级版最后一个节点的 next 不再指向 NULL而是指回头结点头结点的 prev 也不再是 NULL而是指向最后一个节点。逻辑上整个链表形成一个环。好处是从任何一个节点出发都能遍历整条链且逆序输出时不需要先从 head 走到 tail。坏处是遍历的终止条件从“遇到 NULL 停”变成“回到 head 停”。这中间最容易出的问题就是死循环如果你遍历前没判断好起点或者循环里指针更新写错程序就在环里转一辈子。判空条件也要跟着改。带头结点的双向循环链表判空是head-next head。考试选择题特别爱考这一点很多人还在用head-next NULL去判断一测一个错。我还记得当年期末上机一个同学写了循环链表遍历打印调试了一节课最后发现是终止条件写成了while (cur ! NULL)cur 永远不可能是 NULL程序当然跑不出去。4. 实操中的高频坑位与排查技巧4.1 断链指针顺序错了节点直接消失断链是双链表实操里最高频的灾难。我见过一个非常典型的反面代码// 错误示范先改了 p-next原后继直接丢了 p-next newNode; newNode-next p-next-next; // p-next 已经是 newNode 了这段代码的意图是在 p 后面插入 newNode但执行第一行后p 的原后继已经被覆盖。第二行里p-next-next取到的是 newNode-next而 newNode-next 此时还是 NULL原后继就再也找不回来了。节点不是被删除而是被“遗忘”了这种 bug 无处安放只能从头重连。排查断链问题时我的做法是把插入过程画成箭头图。先在纸上画出 p、p-next、newNode 三个节点把每一步指针修改后的指向画出来。画完就知道哪一步不能先做。这个习惯帮我省下的排错时间远超当初学画图花的那点时间。所以遇到断链不要急着瞎改代码先停下画图。4.2 空指针与边界条件删除最后一个节点时最容易翻车空指针访问和边界条件几乎是孪生兄弟。最常见的几个翻车点空链表上做删除p-next 为 NULL却直接访问 p-next-prev。删除唯一的数据节点删除后链表为空后续插入时没重新考虑 head 的状态。双向循环链表中删除最后一个非头节点后head 的 prev 应指向 head但很多人忘了更新头结点的 prev。这些问题的共同点就是没在操作前判断“被操作对象是否真的存在”。C 语言不会帮你处理这些访问空指针就直接崩。我调试代码时有个习惯凡是涉及-的操作先问自己一句“这个指针有没有可能为 NULL”。问完这句边界条件基本能避免大半。4.3 内存管理malloc 了不 free实验报告直接判负C 语言写双链表内存泄漏是重灾区。insert 一万次却只在删除时 free 了一部分程序跑完内存没还进程这种问题在集成测试时才会暴露。真正做项目时我会用一个全局计数器记录 malloc 和 free 的次数每次测试结束对比两个计数是否相等。这不是教材内容但非常实用。排查内存问题时用工具比用眼睛快。Linux 下 Valgrind 一条命令就能找出泄漏位置valgrind --leak-checkfull ./your_program跑完它会告诉你哪一行 malloc 的内存没有释放。我再提醒一句释放链表所有节点的时候不能只 free head要把 head 后面的每个节点都遍历出来 free最后再 free head顺序反了会导致访问已释放内存。5. 双链表的应用场景与面试/考研考点5.1 双链表的真实应用从 LRU 缓存到浏览器历史双链表在工程里最常见的应用之一是 LRULeast Recently Used缓存。经典数据结构是“哈希表 双向链表”哈希表负责 O(1) 查找双向链表负责 O(1) 移动节点到头部或删除尾部节点。为什么不能用单链表因为当某个 key 被再次访问时要把对应节点从链表中间移到头部单链表需要先找到前驱这一步是 O(n)双链表直接通过节点的 prev 就能拿到前驱O(1) 完成。这一下优劣势就很明显了。浏览器前进后退是另一个经典场景。当前页面指针往前访问新页面时把后续记录全部丢弃再往后追加后退就是把指针往 prev 方向移动。每一步都符合双链表的天然能力。文本编辑器的撤销重做、操作系统中进程管理使用的某些队列结构也都经常出现双链表的身影。5.2 高频考点双链表反转、排序、删除指定节点双链表反转是面试手写题里的常客。思路和单链表反转不太一样双链表反转的核心是遍历每个节点交换它的 prev 和 next最后再把头结点的指向处理一下。朴素写法是这样void reverseList(DNode *head) { DNode *cur head-next; while (cur ! NULL) { DNode *temp cur-next; cur-next cur-prev; cur-prev temp; cur temp; } // 此时原链表最后一个节点变成了新的第一个数据节点 // 需要把头结点的 next 指向它并更新它的 prev 指向头结点 if (head-next ! NULL) { DNode *newFirst head-next; // 反转后新的第一个节点 head-next newFirst-prev; if (head-next ! NULL) { head-next-prev head; } } }这段代码有个细节反转操作结束后head 还是原来的 head但第一个数据节点变成原来的尾节点。所以最后需要把头结点的指针修正一下。考场上一紧张就容易漏这一步我建议先画三个节点的链把交换过程画完再写代码。删除指定节点 p 也是考研 408 和面试的热点。代码很短p-prev-next p-next; p-next-prev p-prev; free(p);前提是 p 不是头结点且 p 的 prev 和 next 都存在。为什么这个操作在双链表里是 O(1)因为 p 自己带着前驱指针不需要像单链表那样从头找前驱。这个点经常出现在选择题里问“在双链表中删除指针 p 指向的节点时间复杂度是多少”答案就是 O(1)。5.3 复杂度对比与选型什么时候别用双链表把数据结构拉到一张表里对比结论会更直观数据结构按下标/按键查值在已知节点后插入删除已知节点向前遍历额外空间数组O(1)O(n)要搬移O(n)不支持低单链表O(n)O(1)O(n)要找前驱不支持低双链表O(n)O(1)O(1)支持较高双向循环链表O(n)O(1)O(1)支持较高从这张表就能推导出选型原则如果你只需要顺序追加和顺序遍历单链表就够没必要给每个节点多付一个指针的内存如果你需要频繁删除已知节点或者频繁回退双链表是更合适的选择如果数据量本来就不大比如几千个元素以内直接用数组或动态数组就行双链表的指针开销反而显得“重”。最后多聊一句经验学双链表最怕只看代码不动手。当年我准备数据结构实验报告时把插入和删除在纸上画了不下二十遍每画一遍就重新推演一遍指针变化。一开始总在“要不要判空”“p 有没有后继”这些小地方翻车画多了就形成肌肉记忆写代码不再犹豫。你现在遇到的那些一头雾水和 debug 到深夜基本都是因为脑子里没有那张指针变化图。花一个晚上把插入、删除、反转、循环链表判空这几个操作全部画一遍比自己刷十遍博客都管用。 双链表从原理到实战：数据结构核心操作与面试考点详解
数据结构这关绕不开链表链表这一块双链表又是绕不开的重点。不管你是大一在赶数据结构实验报告还是准备考研408又或者工作中遇到 LRU 缓存这类需要“来回走”的数据结构双链表都是那个躲不过去的基础设施。这篇博文把双链表从设计思路到实操代码、从常见坑位到面试考点一次性讲透适合所有正在学数据结构的同学也适合需要快速捡起来的老手。1. 为什么需要双链表单链表的“单程票”困境1.1 单链表的前驱难题先回顾单链表。每个节点一个 data、一个 next一路朝前。它最大的痛点是想删除中间某个节点 p必须从头遍历找到 p 的前驱。链表规模一大这就是 O(n) 的操作和数组随机访问的 O(1) 一个天上一个地下。更麻烦的是很多实际问题需要“往回倒”——从尾部往头部走单链表连指针都拿不出来。我早先写过一个简易的浏览器历史记录模块用户点“后退”时得从当前页回到上一页。如果用单链表只存 next那你永远知道自己去过哪儿却再也回不去。因为当前节点根本没有 prev 指针。你只能从头重新遍历一遍历史记录找前驱历史一长卡顿就很明显。这个场景直接让我明白单链表的“单程票”设计在回退场景里就是硬伤。1.2 双链表的核心设计思路双链表的改进非常朴素每个节点再加一个 prev 指针指向前一个节点。整条链在逻辑上就是一列双向走廊前进把握 next后退看 prev。代价也很明确每个节点多出一个指针变量的内存典型的空间换时间。内存怎么算以 64 位环境举例一个 int 数据占 4 字节两个指针各占 8 字节光指针就 16 字节。也就是说双链表节点比单链表大概大出一大截。不过现代服务器内存动不动几十 GB这点开销通常可接受换来的是删除、插入在持有目标节点指针时的 O(1) 时间复杂度。到底值不值要看场景需要频繁“往回”操作的场景双链表是首选只做顺序追加、顺序扫描的场景单链表更轻量。这里没有绝对的“谁更好”只有“谁更合适”。2. 双链表的结构定义与基础操作实现2.1 节点结构体怎么定义C语言里的双链表骨架C语言实现双链表核心就是多一个指向前驱的指针。定义一个节点typedef struct DNode { int data; struct DNode *prev; struct DNode *next; } DNode;这里结构体里出现struct DNode是因为 C 语言里结构体不能直接递归使用自己的别名必须用完整的struct DNode来声明指针。如果你开了 typedef也不能在成员声明里直接写DNode *prev编译器在那一刻还不认识 DNode。这是很多初学 C 的同学踩的第一个坑。有了节点还要区分头结点和头指针。头指针是链表的入口变量指向链表的第一个节点头结点是挂在真正数据节点之前的一个哨兵节点data 字段通常存无效值。带头结点的好处是空表判断、插入删除操作统一化不用为“首节点没有前驱”写一坨分支。很多教材会把“头结点”和“首元结点”混着提其实是两个东西必须分清。我的建议是日常练习和考试都带头结点省心。2.2 初始化、遍历与逆序输出先把三个基础动作跑通初始化一个带头结点的空双链表核心是让 head 的 prev 和 next 都指向 NULLDNode *initList() { DNode *head (DNode *)malloc(sizeof(DNode)); if (head NULL) { return NULL; } head-prev NULL; head-next NULL; return head; }malloc 之后一定要判空。这是不少练习代码里没有的步骤但在真实系统中内存申请可能失败不判空后面就是空指针崩溃。顺向遍历很简单从 head-next 开始一路 next 到 NULL 为止void printList(DNode *head) { DNode *cur head-next; while (cur ! NULL) { printf(%d , cur-data); cur cur-next; } printf(\n); }逆序遍历才是双链表的看家本领。先用 cur 走到最后一个节点再一路走 prev 回到 headvoid printReverse(DNode *head) { DNode *cur head; while (cur-next ! NULL) { cur cur-next; } while (cur ! head) { printf(%d , cur-data); cur cur-prev; } printf(\n); }你对比一下单链表单链表逆序输出最笨的办法是每次都从头扫到尾复杂度 O(n²)双链表只需要 O(n)。这个差异在链表长度达到上万的时候就非常明显了。2.3 Python、Java、PHP 怎么写双链表语言差异只是皮很多同学看 C 语言版本觉得指针绕换语言就轻松不少。以 Python 为例class Node: def __init__(self, data): self.data data self.prev None self.next None class DoublyLinkedList: def __init__(self): self.head Node(None) # 哨兵节点Python 的引用本质上就是指针的封装理解逻辑一样只是不用你手动 malloc/free。Java 也类似一个内部类就能表示节点class DNode { int data; DNode prev; DNode next; DNode(int data) { this.data data; } }热词里还看到了 php 双链表。PHP 里写双链表也很直白class DNode { public $data; public $prev; public $next; public function __construct($data) { $this-data $data; $this-prev null; $this-next null; } }语言变了核心就没变每个节点还是 data prev next插入删除还是那把指针操作的逻辑。所以我一直建议双链表的核心不要局限在某一门语言上C 语言把它彻底吃透其他语言就是换皮。3. 插入与删除最考验指针操作的两个环节3.1 在指定节点后插入记住“先绑新链再改旧链”双链表插入的教科书操作是在节点 p 之后插入新节点 s。一共四步s-next p-next; // 第一步新节点的后继指向 p 的旧后继 s-prev p; // 第二步新节点的前驱指向 p if (p-next ! NULL) { // 第三步如果 p 有后继让后继的 prev 指向 s p-next-prev s; } p-next s; // 第四步p 的后继改指向 s为什么这个顺序最关键因为如果先改p-next sp 的原后继就丢了你后面想拿p-next-prev拿到的其实是 s 而不是那个被抛弃的节点链表当场断成两截。所有断链事故根源都是“先动旧链再接新链”。记住八个字先绑新链再改旧链。在 p 之后插入只需要 O(1)不需要遍历这就是双链表的价值。头插法和尾插法都是这个操作的变体。头插法等于在 head 之后插入尾插法则是先遍历到最后一个节点再在它之后插入。尾插因为要走到末尾所以是 O(n)。如果你频繁在尾部追加数据且数据量很大更优做法是维护一个 tail 指针直接指向链表末尾。3.2 删除节点四行核心逻辑与内存释放细节删除 p 的下一节点逻辑同样清晰DNode *del p-next; if (del NULL) { return; // 没有可删的节点 } p-next del-next; if (del-next ! NULL) { del-next-prev p; } free(del);先说为什么删除前要判空如果 p 是最后一个节点它的 next 是 NULL直接给 del 赋 NULL下一步访问 del-next 就直接段错误。这个边界条件在考试写代码时特别容易漏。再说说 double free 的问题。free(del) 之后del 指向的内存已经还给系统如果你后面又写del-next或者再次 free(del)就是非法访问。一个稳妥的习惯是 free 之后立刻把指针置 NULLfree(del); del NULL;很多内存报错看起来莫名其妙最后追查就是 double free 或者 use-after-free。真实的工程环境里这类问题都会被编译器 Sanitizer 或者 Valgrind 抓得明明白白但等你调试到那时候时间已经浪费光了。不如一开始就养成好习惯。3.3 双向循环链表头尾相连后的判空与终止条件双向循环链表是双链表的标准升级版最后一个节点的 next 不再指向 NULL而是指回头结点头结点的 prev 也不再是 NULL而是指向最后一个节点。逻辑上整个链表形成一个环。好处是从任何一个节点出发都能遍历整条链且逆序输出时不需要先从 head 走到 tail。坏处是遍历的终止条件从“遇到 NULL 停”变成“回到 head 停”。这中间最容易出的问题就是死循环如果你遍历前没判断好起点或者循环里指针更新写错程序就在环里转一辈子。判空条件也要跟着改。带头结点的双向循环链表判空是head-next head。考试选择题特别爱考这一点很多人还在用head-next NULL去判断一测一个错。我还记得当年期末上机一个同学写了循环链表遍历打印调试了一节课最后发现是终止条件写成了while (cur ! NULL)cur 永远不可能是 NULL程序当然跑不出去。4. 实操中的高频坑位与排查技巧4.1 断链指针顺序错了节点直接消失断链是双链表实操里最高频的灾难。我见过一个非常典型的反面代码// 错误示范先改了 p-next原后继直接丢了 p-next newNode; newNode-next p-next-next; // p-next 已经是 newNode 了这段代码的意图是在 p 后面插入 newNode但执行第一行后p 的原后继已经被覆盖。第二行里p-next-next取到的是 newNode-next而 newNode-next 此时还是 NULL原后继就再也找不回来了。节点不是被删除而是被“遗忘”了这种 bug 无处安放只能从头重连。排查断链问题时我的做法是把插入过程画成箭头图。先在纸上画出 p、p-next、newNode 三个节点把每一步指针修改后的指向画出来。画完就知道哪一步不能先做。这个习惯帮我省下的排错时间远超当初学画图花的那点时间。所以遇到断链不要急着瞎改代码先停下画图。4.2 空指针与边界条件删除最后一个节点时最容易翻车空指针访问和边界条件几乎是孪生兄弟。最常见的几个翻车点空链表上做删除p-next 为 NULL却直接访问 p-next-prev。删除唯一的数据节点删除后链表为空后续插入时没重新考虑 head 的状态。双向循环链表中删除最后一个非头节点后head 的 prev 应指向 head但很多人忘了更新头结点的 prev。这些问题的共同点就是没在操作前判断“被操作对象是否真的存在”。C 语言不会帮你处理这些访问空指针就直接崩。我调试代码时有个习惯凡是涉及-的操作先问自己一句“这个指针有没有可能为 NULL”。问完这句边界条件基本能避免大半。4.3 内存管理malloc 了不 free实验报告直接判负C 语言写双链表内存泄漏是重灾区。insert 一万次却只在删除时 free 了一部分程序跑完内存没还进程这种问题在集成测试时才会暴露。真正做项目时我会用一个全局计数器记录 malloc 和 free 的次数每次测试结束对比两个计数是否相等。这不是教材内容但非常实用。排查内存问题时用工具比用眼睛快。Linux 下 Valgrind 一条命令就能找出泄漏位置valgrind --leak-checkfull ./your_program跑完它会告诉你哪一行 malloc 的内存没有释放。我再提醒一句释放链表所有节点的时候不能只 free head要把 head 后面的每个节点都遍历出来 free最后再 free head顺序反了会导致访问已释放内存。5. 双链表的应用场景与面试/考研考点5.1 双链表的真实应用从 LRU 缓存到浏览器历史双链表在工程里最常见的应用之一是 LRULeast Recently Used缓存。经典数据结构是“哈希表 双向链表”哈希表负责 O(1) 查找双向链表负责 O(1) 移动节点到头部或删除尾部节点。为什么不能用单链表因为当某个 key 被再次访问时要把对应节点从链表中间移到头部单链表需要先找到前驱这一步是 O(n)双链表直接通过节点的 prev 就能拿到前驱O(1) 完成。这一下优劣势就很明显了。浏览器前进后退是另一个经典场景。当前页面指针往前访问新页面时把后续记录全部丢弃再往后追加后退就是把指针往 prev 方向移动。每一步都符合双链表的天然能力。文本编辑器的撤销重做、操作系统中进程管理使用的某些队列结构也都经常出现双链表的身影。5.2 高频考点双链表反转、排序、删除指定节点双链表反转是面试手写题里的常客。思路和单链表反转不太一样双链表反转的核心是遍历每个节点交换它的 prev 和 next最后再把头结点的指向处理一下。朴素写法是这样void reverseList(DNode *head) { DNode *cur head-next; while (cur ! NULL) { DNode *temp cur-next; cur-next cur-prev; cur-prev temp; cur temp; } // 此时原链表最后一个节点变成了新的第一个数据节点 // 需要把头结点的 next 指向它并更新它的 prev 指向头结点 if (head-next ! NULL) { DNode *newFirst head-next; // 反转后新的第一个节点 head-next newFirst-prev; if (head-next ! NULL) { head-next-prev head; } } }这段代码有个细节反转操作结束后head 还是原来的 head但第一个数据节点变成原来的尾节点。所以最后需要把头结点的指针修正一下。考场上一紧张就容易漏这一步我建议先画三个节点的链把交换过程画完再写代码。删除指定节点 p 也是考研 408 和面试的热点。代码很短p-prev-next p-next; p-next-prev p-prev; free(p);前提是 p 不是头结点且 p 的 prev 和 next 都存在。为什么这个操作在双链表里是 O(1)因为 p 自己带着前驱指针不需要像单链表那样从头找前驱。这个点经常出现在选择题里问“在双链表中删除指针 p 指向的节点时间复杂度是多少”答案就是 O(1)。5.3 复杂度对比与选型什么时候别用双链表把数据结构拉到一张表里对比结论会更直观数据结构按下标/按键查值在已知节点后插入删除已知节点向前遍历额外空间数组O(1)O(n)要搬移O(n)不支持低单链表O(n)O(1)O(n)要找前驱不支持低双链表O(n)O(1)O(1)支持较高双向循环链表O(n)O(1)O(1)支持较高从这张表就能推导出选型原则如果你只需要顺序追加和顺序遍历单链表就够没必要给每个节点多付一个指针的内存如果你需要频繁删除已知节点或者频繁回退双链表是更合适的选择如果数据量本来就不大比如几千个元素以内直接用数组或动态数组就行双链表的指针开销反而显得“重”。最后多聊一句经验学双链表最怕只看代码不动手。当年我准备数据结构实验报告时把插入和删除在纸上画了不下二十遍每画一遍就重新推演一遍指针变化。一开始总在“要不要判空”“p 有没有后继”这些小地方翻车画多了就形成肌肉记忆写代码不再犹豫。你现在遇到的那些一头雾水和 debug 到深夜基本都是因为脑子里没有那张指针变化图。花一个晚上把插入、删除、反转、循环链表判空这几个操作全部画一遍比自己刷十遍博客都管用。