双链表这名字，看着比单链表多了一个字，但实际用起来完全是两种体验。在数据结构的教材里，它通常被排在单链表之后的下一节，很多同学翻过去就忘了，真正到刷题或者写项目时，遇到“既要前驱又要后继”的需求，才回头来补这堂课。这篇博客就把我当年踩过的坑和积累的经验写下来，聊聊双链表到底解决了什么问题、怎么写出不丢指针的完整代码，以及它在考研、期末面试里最常被考察的细节，适合正在学数据结构、准备期末或者备考考研的朋友参考。
链表这个东西，本质上就是把“下一个节点在哪”的信息存起来。单链表只存了 next，所以从某个节点出发只能一路向前，想回头看上一个节点就得从头遍历。双链表多存了一个 prior 指针，代价是多占一个指针的空间，换来的是双向遍历和 O(1) 删除指定节点前驱的能力。我为什么说它是“性价比极高”的结构，因为它在真实系统里应用场景非常多，LRU 缓存、双端队列、浏览器历史记录，底层用的都是双链表的设计思路。而且 408 和考研数据结构里，双链表一直是重点考察对象，经常出现在大题里的就是插入、删除、逆序这一类操作。
下面不绕弯子，直接按我的理解把它拆开讲。我会先把“为什么需要双链表”讲透，再给出结构定义、插入删除的指针操作顺序、完整可运行的 C 代码，最后分享调试过程中最容易踩的坑以及双链表在高级数据结构里的延伸。
1. 为什么学了单链表还要折腾双链表
1.1 从生活场景理解双链表的“双向”价值
我第一次学双链表的时候也很困惑：单链表明明能完成基本的数据存取，为什么还要多存一个指针，这不是浪费空间吗？后来我在一个文本编辑器的小项目里被卡住了，编辑器维护一个“当前光标位置”，用户点击“撤销上一步操作”时要回到上一步，点击“重做”时要前进到下一步，每次都要从链头重新遍历，数据量一大就肉眼可见地卡。那时候我才意识到，很多需求天然就是双向的。
你可以这样理解：单链表像一条单行道，你开车进去之后想掉头，就只能一路开到终点再绕回来，代价极高。双链表则相当于给每个节点都修了一个“掉头路口”，在任意一个位置都可以直接朝两个方向走。具体到计算机里，“掉头”就是往前一个节点移动，单链表想做这件事只能回到头节点重新搜索，双链表只需要访问 prior 指针就行。
所以学双链表的时候，不要只盯着“多了一个指针”这个表面差异，要抓住一个核心结论：当你的数据访问模式是“既要看左边又要看右边”的时候，双链表的优势就是结构性的，不是优化手段能弥补的。
1.2 双链表到底改进了什么
要说清改进，直接对比单链表和双链表在几个核心操作上的复杂度最直观。假设链表长度为 n，给定一个已经找到的节点 p：
| 操作 | 单链表 | 双链表 | 改进点 |
|---|---|---|---|
| 查找第 i 个元素 | O(n) | O(n) | 双链表可双向逼近，某些场景常数更小 |
| 删除节点 p（已知 p） | O(n) 需找前驱 | O(1) | 这是双链表最大的优势 |
| 在节点 p 前插入 | O(n) 需找前驱 | O(1) | 单链表做不到 |
| 找直接前驱 | O(n) 从头遍历 | O(1) | 结构天然支持 |
| 逆序遍历 | O(n) 反转或递归 | O(n) 但无需反转 | 代码更简单，不破坏原结构 |
这张表里最关键的一行是“删除节点 p”。单链表删除 p 时必须先知道 p 的前驱是谁，否则无法把前驱的 next 指向 p 的 next。双链表因为 p->prior 指向了前驱，删除就变成了两条赋值加一个 free 的问题。这个 O(n) 到 O(1) 的差距，在链表很长、删除频繁的场景里，直接影响系统能不能扛住压力。
我举个例子：Java 的 LinkedList 底层就是一个带头节点的双向链表，它在中间插入删除的时间复杂度能维持 O(1)，靠的正是双链表的 prior 指针；如果换成单链表，ArrayList 或某些基于数组结构才更适合随机访问。工程选型的底层逻辑，很多时候就是数据结构复杂度分析的直接映射。
1.3 哪些场景必须用双链表
先列举几个经典场景，你会发现双链表不是“锦上添花”，而是“雪中送炭”。
第一类场景是双向遍历。浏览器的前进、后退按钮，音乐播放器的上一首、下一首，文本编辑器里的光标上下移动，这种“以当前节点为基准，向两边移动”的交互模式，双链表是最自然的建模方式。单链表虽然也能实现，但每次回到上一个节点都要从头找，完全是自虐。
第二类场景是频繁删除指定节点。比如操作系统进程列表、网络连接表中需要按某个标识快速摘除一个节点，如果下层是单链表，删除前要先搜索前驱；如果业务里已经通过哈希表或索引拿到了目标节点，那双链表的 O(1) 删除就是唯一合理的选择。这也是经典 LRU 缓存为什么一定要用哈希表加双链表的原因，后面我会专门展开讲。
第三类场景是作为复杂数据结构的骨架。双端队列的底层实现、跳表某些层的节点结构、CDR 环的一部分实现，都可能用双链表组织。它不一定是最终形态，但它是理解这些结构的重要台阶。
对于考研和面试来说，明确一点：考试不会只问你“双链表是什么”，而是会把双链表放进具体的操作题里。408 里常见的一个考点就是给你一段删除或插入的代码，让你判断哪里会断链；或者给你单链表、双链表分别在指定位置插入的元素搬移次数让你分析。所以这个章节的价值，就是让你在一开始就把“为什么需要双链表”想清楚，后续所有代码细节都建立在这个认知之上。
2. 双链表的核心细节与三个关键操作
2.1 结构体怎么定
C 语言的结构体定义是基础，但写法上有几个容易含糊的点。我常用的定义是：
typedef struct DNode { int data; // 数据域，考试和练习里一般用 int struct DNode *prior; // 指向前驱节点 struct DNode *next; // 指向后继节点 } DNode, *DLinkList;这里有两个细节值得说明。第一，为什么在结构体内部声明指针时写struct DNode *prior而不是DNode *prior？因为 typedef 是结构体定义结束后才生效的，在结构体内部它还不认识DNode这个别名。这个问题几乎每个初学者都会问，实际写代码时如果顺序搞错编译器直接报错。
第二，DLinkList这个类型本质上就是DNode *，它的意义在于语义化：当变量声明为DLinkList时，我默认它指向头节点或者链表表头，用来代表整条链表；当变量声明为DNode *时，它代表某个具体节点。虽然在编译器眼里两者是一样的，但在代码可读性上差别很大，团队协作时这个约定能帮你快速看懂接口。
如果你想存字符串、结构体或者其他类型，那就把 int data 改成对应的类型，或者直接改成void *data做泛化设计。不过考试和大部分练习用 int 就足够了，重点考察的是指针逻辑，而不是数据类型本身。
2.2 插入操作：难点在于四个指针的先后顺序
双链表插入节点，比单链表麻烦的地方在于它牵涉到四个指针的修改：新节点的 prior、新节点的 next、前驱节点的 next、后继节点的 prior。核心记忆就四个字：先连后断。
什么意思呢？就是先把新节点和它前后的节点连接好，再去断开原来的指针。这个顺序是必须的，因为如果你先改了p->next指向新节点，那么原来的后继节点就找不到了，新节点的 next 就不知道该指向谁。
假设要在节点 p 之后插入一个值为 value 的新节点 s：
DNode *InsertAfter(DNode *p, int value) { if (p == NULL) { return NULL; } DNode *s = (DNode *)malloc(sizeof(DNode)); if (s == NULL) { exit(1); } s->data = value; // 1. 新节点先搭桥 s->prior = p; s->next = p->next; // 2. 更新后继节点的 prior if (p->next != NULL) { p->next->prior = s; } // 3. 更新前驱节点的 next p->next = s; return s; }这里最难理解的是第 2 步和第 3 步的顺序。如果你先把p->next = s写了，那么p->next->prior = s这行代码的含义就变了，它访问的其实是 s 本身，而不是原后继节点。所以通常建议先处理后继节点的 prior，再修改前驱节点的 next。当然你也可以先用一个临时指针把原后继节点保存下来，再做更新，代码更直观一些。
在 p 之前插入节点InsertBefore的思路完全对称，只是把参考系从“p 的前驱”变成“p 自己”。考试里经常让你对比这两种插入，写出代码后核对一下 4 条语句的先后顺序，基本就能拿分。
2.3 删除操作：记住一句话就够
删除节点 p 的核心逻辑我概括为一句话：让 p 的前驱的后继指向 p 的后继，让 p 的后继的前驱指向 p 的前驱，然后释放 p。
写成代码就是：
int DeleteNode(DNode *p) { if (p == NULL || p->prior == NULL) { return 0; // p 不能是头节点或空节点 } p->prior->next = p->next; if (p->next != NULL) { p->next->prior = p->prior; } free(p); return 1; }这段代码里最容易被忽视的是中间那个 if 判断。因为如果 p 正好是尾节点，那么p->next是 NULL，直接执行p->next->prior就会空指针崩溃。在单链表删除里也有同样的问题，但在双链表里更容易犯，因为双链表的代码看起来太对称了，一不留神就忘了尾节点的特殊性。
删除头节点后面的第一个节点、删除中间节点、删除尾节点，三种情况的代码核心都一样，唯一的区别就是if (p->next != NULL)这个条件是否成立。建议大家动手分别写一遍，加深印象。
2.4 遍历与带头节点问题
双链表遍历和单链表完全一样，从头节点开始，沿着 next 一路走到 NULL 即可：
void PrintList(DLinkList head) { DNode *p = head->next; while (p != NULL) { printf("%d ", p->data); p = p->next; } printf("\n"); }逆序遍历则利用了双链表的优势，先找到最后一个节点，然后沿着 prior 回头走：
void PrintReverse(DLinkList head) { DNode *p = head; while (p->next != NULL) { p = p->next; } while (p != head) { printf("%d ", p->data); p = p->prior; } printf("\n"); }这里的头节点（表头）我统一使用“带头节点”的写法。带头节点和不带头节点的区别，很多同学学的时候不太在意，但实际编码和考试里影响很大。带头节点意味着链表有一个空的头节点，它的 data 不存储有效数据，priority 为 NULL，它的存在让“在第一个位置插入”和“删除第一个节点”这两类操作不需要单独写边界分支，代码更统一。
我强烈建议初学者从一开始就带头节点，理由在后面的“哨兵节点”技巧里会再次印证。考试时如果题目没有明确说明，你也可以在算法描述里自己定义带头节点，只要写清楚就行，很多标准答案甚至默认带头节点，省去大量边界讨论。
3. 用 C 语言完整实现一遍
这一部分给出可直接编译运行的完整代码。我平时调试链表时习惯把所有操作封装成函数，主函数只负责调用和打印，这样每次想验证某个边界情况时，改几行代码就能跑。
3.1 初始化、构建与销毁
初始化带头节点的双链表很简单：
DLinkList InitList() { DLinkList head = (DLinkList)malloc(sizeof(DNode)); if (head == NULL) { exit(1); } head->prior = NULL; head->next = NULL; return head; }这里注意头节点的 prior 和 next 都要制空，尤其是 prior，很多代码只设 next 而忘了 prior，后续反向遍历时就会遍历到随机地址。
构建链表有两种方式：头插法和尾插法。头插法适合需要逆序生成的场景，尾插法适合保持输入顺序的场景。我给出尾插法，因为它的逻辑更贴近“往链表末尾追加”的直觉：
DLinkList CreateByTail(DLinkList head, int arr[], int n) { DNode *tail = head; // tail 始终指向链表最后一个节点 for (int i = 0; i < n; i++) { DNode *s = (DNode *)malloc(sizeof(DNode)); s->data = arr[i]; s->next = NULL; s->prior = tail; // 新节点的前驱是当前的尾节点 tail->next = s; tail = s; // 更新尾节点 } return head; }这段代码的核心就是维护一个 tail 指针。如果不用 tail，每次追加新节点都得从头遍历到尾部，时间复杂度就是 O(n²)，写的人可能感觉不到，数据量一大就原形毕露。这也是一个常见的优化意识：链表操作里，维护尾指针可以大幅降低后续操作的复杂度。
销毁链表要特别注意顺序，因为释放当前节点之后就不能再访问它的 next 了。所以必须先把 next 存到临时变量里：
void DestroyList(DLinkList head) { DNode *p = head->next; while (p != NULL) { DNode *tmp = p; p = p->next; // 先保存下一个节点的位置 free(tmp); // 再释放当前节点 } free(head); }3.2 按位置插入与按值删除
按位置插入其实就是先找到第 i 个节点，再在它后面插入新节点。查找过程是 O(n)，插入本身是 O(1)。这里我封装一个查找函数：
DNode *GetNode(DLinkList head, int i) { DNode *p = head->next; int count = 1; while (p != NULL && count < i) { p = p->next; count++; } return p; // 如果 i 不合法，返回 NULL }然后在第 i 个节点之后插入 value：
int InsertAt(DLinkList head, int i, int value) { DNode *p = GetNode(head, i); if (p == NULL) { return 0; } return InsertAfter(p, value) != NULL; }按值删除的逻辑是先从链表里找到目标节点，然后调用删除函数：
int DeleteByValue(DLinkList head, int value) { DNode *p = head->next; while (p != NULL && p->data != value) { p = p->next; } if (p == NULL) { return 0; } return DeleteNode(p); }这种分离的结构很推荐，因为每个函数只做一件事，测试的时候可以精准定位问题。我早期写链表代码总爱把所有逻辑堆在 main 里，结果一出 bug 就只能对着整个文件发愁，后来改成模块化之后，调试效率高了很多。
3.3 完整示例与运行结果
把上面所有函数组合起来，写一个测试用的 main：
#include <stdio.h> #include <stdlib.h> // 此处放入结构体定义及上述所有函数 int main() { DLinkList head = InitList(); int arr[] = {1, 3, 5, 7, 9}; CreateByTail(head, arr, 5); printf("正向遍历: "); PrintList(head); printf("反向遍历: "); PrintReverse(head); InsertAt(head, 3, 100); printf("在第3个节点后插入100: "); PrintList(head); DeleteByValue(head, 100); printf("删除值为100的节点: "); PrintList(head); DestroyList(head); return 0; }运行结果应该是：
正向遍历: 1 3 5 7 9 反向遍历: 9 7 5 3 1 在第3个节点后插入100: 1 3 5 100 7 9 删除值为100的节点: 1 3 5 7 9我建议大家拿到代码后不要直接抄完就关掉，手动在纸上画一个链表，模拟插入和删除时每个指针的指向变化。画图看起来慢，但特别管用，遇到复杂的边界情况能少走很多弯路。我当时就是把头插、尾插、中间插入、删除头节点、删除尾节点这几种情况全都画了一遍，后面刷题基本没再被指针搞晕过。
4. 调试、排查与面试里最常踩的坑
4.1 指针丢失的经典现场
链表代码里 90% 的 bug 都是指针丢失，双链表因为指针更多，出问题的概率更大。最常见的场景是插入时顺序写错，比如先执行了p->next = s，再想访问原本的p->next就找不到了。这事看起来低级，但在考场上很常见，因为试卷不是 IDE，没有编译器和调试器帮你查错，只能靠对“先连后断”原则的记忆来判断。
第二个经典现场是删除尾节点时没有判空。p->next->prior = p->prior这一句，如果 p 是尾节点，p->next是 NULL，访问NULL->prior直接崩溃。面试官非常喜欢在代码里藏这个陷阱，他会先让你写删除函数，然后追加一句：“如果这个节点是最后一个节点呢？”我见过很多候选人平时写代码很顺，一到这里就卡住。
针对这个问题，我自己的排查习惯是：写完删除函数后，依次在纸上人工执行“删除唯一一个节点”和“删除表头第一个节点”两种用例，只要这两种没问题，大部分边界就算过了。空表情况（只有头节点）也容易忽略，一定要在函数开头加上对 p 是否为 NULL 的判断。
4.2 边界条件遗漏速查表
下面是双链表代码里最容易被遗漏的边界条件，也是我过去面试别人时最常考的几个点，整理成一张检查表：
| 场景 | 需要注意的问题 | 常见错误 |
|---|---|---|
| 空表（只有头节点） | 正向遍历、反向遍历是否正常退出 | 直接解引用 head->next 导致崩溃 |
| 插入到第一个节点前 | 头插法的指针更新顺序 | 忘记更新 head->next 或新节点的 prior |
| 删除第一个有效节点 | 头节点的 next 如何更新 | 忘记赋值 head->next 导致链表失联 |
| 删除尾节点 | p->next 为 NULL，不能访问 p->next->prior | 空指针访问 |
| 只有一个有效节点 | 删除后链表回到空表状态 | 头节点指针没有正确置空 |
| 插入或删除的 p 是头节点 | 头节点不能作为普通节点被删 | 头节点的 prior 是 NULL，逻辑失效 |
这张表我自己在复习考研的时候就会反复默写，因为链表题目只要边界不错，主体逻辑一般就能得大部分分。408 的大题评分里，代码逻辑占大头，边界条件常是扣分点，但也是最好拿回的分。
4.3 写题时的偷懒技巧：哨兵节点
讲一个我在刷题时才真正体会到价值的技巧：带头节点的双链表，天然就是一个带哨兵节点的结构。哨兵节点这个概念听起来高端，其实就是那个不存储有效数据的头节点。它的作用是把空表、表头、表尾这些特殊位置都变成“普通位置”，让边界问题集中到几个统一的判断上。
举个例子，在 p 节点之后插入新节点，如果链表只有一个头节点，那么 p 就是 head，p->next 是 NULL，此时p->next->prior同样面临空指针问题。但你只要在插入函数里写了if (p->next != NULL)，这个用例也自动覆盖了。带头节点把“空链表”和“插入到表尾”统一成同一种情况，代码分支变少，逻辑更清楚。
如果你写的是不带头节点的链表，头插、尾插、删除第一个节点全都要单独写一堆 if 来维护头指针，很容易心情烦躁然后出错。所以我自己刷题时几乎一律默认带头节点，除非题目明确要求不带头节点。面试时也可以先跟面试官确认一下约定，通常对方都会认可。
4.4 听说 408 与考研里怎么考
考研数据结构里，双链表的题目一般集中在三类：一是手写插入删除，二是分析复杂度，三是结合其他结构（栈、队列、散列）设计方案。408 的大题倾向于把链表和算法设计结合，比如要求用双链表作为底层实现一个某种结构；期末和小题则更常考指针的指向判断。
复习时建议把双链表和单链表、循环链表放在一起对比，做一个“链表操作复杂度对照表”，考前翻一遍比临时抱佛脚看代码有用得多。《大话数据结构》里对链表的图示和讲解比较生动，很多人第一遍看不懂课本代码时靠它能理清思路；《数据结构与算法分析：Java 语言描述》则更适合想从面向对象角度理解链表背后道理的读者，语言不同但思想一致。要是备考 408，王道等考研辅导书里的习题至少要过一遍，尤其是算法设计题，练的是手感和边界意识。
5. 从双链表到进阶：双端队列与 LRU 缓存
5.1 双链表是双端队列的底子
双端队列是“两端都能进、两端都能出”的队列。从这个定义你能直接感觉到：它天然需要两端的 O(1) 操作。数组实现双端队列也能做到，但要处理扩容和中间元素平移，而链表实现双端队列则非常自然。队头插入就是头插法，队尾插入就是尾插法，队头弹出就是删除首个有效节点，队尾弹出就是删除尾节点，这四个操作在带头节点的双链表里全部是 O(1)。
Java 的 LinkedList 就是这样一个双链表实现了 List 和 Deque 双重接口。它为什么不用单链表？因为单链表无法实现高效的“弹出队列尾部”操作——你得从头遍历到尾才能找到尾节点的前驱。用双链表，尾节点直接有 prior 指向前一个节点，弹出尾部也就是两条指针调整的事。这种设计选择背后的复杂度考量，就是我们前面反复强调的“删除已知节点的前驱”需求。
学到这里，你会发现一个规律：只要某个操作需要频繁访问“上一个节点”，单链表就会变成性能瓶颈。这个规律放之四海而皆准，理解了这一点，很多系统设计的选型你也能看懂。
5.2 双链表是 LRU 算法的灵魂
LRU（Least Recently Used，最近最少使用）缓存淘汰策略，是面试高频题，也是双链表经典应用。它的核心要求是：当缓存满时，淘汰最久没被访问的数据；每次访问一个数据，就把它标记为“最近使用”。为了满足“最近使用”这个语义，需要一个能快速把节点移动到“最新”位置的结构。
经典解法是哈希表加双链表。哈希表负责在 O(1) 时间内找到某个 key 对应的节点，双链表负责维护访问顺序：队头代表最近使用的，队尾代表最久未使用的。每次访问某个 key，就把对应的节点从链表中间移到队头。这里的“从链表中间移到队头”，拆开来看其实就是两步：先删除该节点（O(1)），再在队头插入该节点（O(1)）。
如果底层是单链表，从链表中间删除一个已知节点需要先找前驱，O(n) 的时间直接把 LRU 的复杂度毁了。所以面试官问你“为什么 LRU 要用双链表”，你只需要回答一句：因为双链表能让“删除中间任意节点”做到 O(1)，配合哈希表就是 O(1) 的 get 和 put。这一个点讲清楚，整道题的核心就答对了一半。
我记得自己第一次手写 LRU 时，在删除节点的逻辑上栽了跟头，把p->prior->next和p->next->prior写反了，当时测试一直报错，怎么调试都看不出问题。后来静下来在纸上画了几条线，一眼就发现顺序反了。这种错误就是“先连后断”原则的另类体现，代码本身没有空指针，但逻辑上已经在不知不觉中改了两个节点的指向。
5.3 如何继续扩展学习
双链表学完之后，建议再往前走三步。
第一步，把双链表改成循环双链表。循环双链表最后一个节点的 next 指向头节点，头节点的 prior 指向最后一个节点，在很多需要“环形”语义的场景——比如操作系统进程调度的时间片轮转、音乐播放器的循环列表——比非循环版本更自然。
第二步，用 Python 再实现一遍双链表。Python 的类定义方式更能帮助你聚焦在“逻辑”而不是“指针语法”上。北大那本《Python 数据结构与算法》里对链表的讲解很细致，如果之前只用 C 写过，换个语言实现一次，你会对“节点是对象、指针是引用”有更抽象的理解。
第三步，去 LeetCode 或王道题库里搜“LRU Cache”和“设计双端队列”这两道题，用你自己实现的链表结构去做一遍。做完之后你会发现，很多看起来复杂的高频题，底层就是咱们今天写的这几个函数。
写在最后的个人经验
双链表写起来不难，难的是每一次指针操作都要心里有数。我个人在实际操作中最深的体会是：永远不要在没画图的情况下写链表的插入删除代码。你可以不画在纸上，但至少在脑子里画清“这时候哪个节点的 next 被改了、哪个节点的 prior 被改了、还有没有别的指针指向被改的节点”。想清楚这三件事再写代码，基本一遍就能跑通。
最后再分享一个小技巧，也是我后来写很多链表题时通用的方法：新节点的内存空间分配后，一定要立刻初始化 prior 和 next 两个指针，哪怕暂时是 NULL。这个习惯能帮你躲掉大量“野指针”和“未初始化内存”带来的诡异 bug。别小看这两行赋值，我见过太多人在复杂链表操作上报错，最后定位到原因就是创建节点时漏了其中一个指针的初始化。
双链表本身不难，但它是一座桥，走过去之后你会对链表这一类结构有完全不同的理解。等我后面有空，再写一篇循环双链表和 LRU 的具体实现，把今天提到的延伸应用串起来。
