从事数据结构教学和底层开发这些年，我越来越发现一个规律：很多初学者能把单链表背得滚瓜烂熟，但一碰到双向链表就发怵。原因也很简单，单链表只需要管好一个next指针，双向链表却要同时维护prev和next两根线，稍不留神就把链给断了。但恰恰是这个看起来更复杂的结构，在实际工程里出场率极高，像浏览器的前进后退、文本编辑器的撤销重做、Redis的列表对象、LRU缓存淘汰，底层全是双向链表的影子。如果你正在准备数据结构期末考试、考研408，或者刚入行想搞懂链表到底怎么玩，这篇文章应该能帮你把双向链表彻底吃透，不光是会背定义，还能真正写出能跑的代码。
我最早在课程设计里维护一个学生成绩表，需求很简单：按学号排序，支持插入、删除、输出。当时用单链表写，删除一个节点得从头遍历找前驱，代码写出来又长又绕，调了几小时bug，最后发现是删除时少记了一个pre指针。后来换成双向链表，一切豁然开朗——删除节点时直接通过prev就能找到前驱，双向遍历也顺手了。今天这篇就把我这些年用双向链表的经验全部摊开来讲，包括设计思路、手写代码、性能分析、面试高频题，以及我自己踩过的一些坑。
1. 为什么会需要双向链表——从单向链表的痛点说起
1.1 单向链表的“回不去”困境
先想一个问题：单链表里，每个节点只存了一个指向后继的指针。这意味着你从表头出发，可以一路顺着next走到结尾，但想回头找上一个节点？对不起，没路。除非你从头再遍历一遍。
这个“回不去”的问题，在某些场景下是致命的。举个最典型的例子：你维护了一个有序链表，现在要删除某个值为x的节点。单链表的做法是：遍历到目标节点的前一个节点，然后修改它的next指针，跳过目标节点。也就是说，你明明要删的是节点p，但真正要操作的是p的前驱。如果链表是单向的，你就得用一个pre指针始终跟着当前节点走，遍历结束后拿到的其实是前驱。代码丑不说，逻辑还容易出错。
好不容易写完了，过几天需求又变了：“我要倒序输出这个链表”。单链表这时候只能先反转，或者递归输出，两种方式都不够优雅。你会发现，单链表一旦涉及到“向前回溯”，就处处受制。
1.2 双向链表怎么解决：每个节点多一根“回头路”
双向链表的改进非常直接：每个节点不再只存一个指针，而是存两个指针。一个叫prev（前驱指针），指向前一个节点；一个叫next（后继指针），指向后一个节点。头节点的prev指向空（或指向尾节点，看是否循环），尾节点的next指向空（或指向头节点）。
用生活的话说，单链表就像一条单行道，你只能顺着一个方向开；双向链表是双向车道，既能往前也能往后。别小看这个改动，它意味着你拿到了任何一个节点，都能以O(1)的时间复杂度访问它的前驱和后继，这在很多算法设计里是质的飞跃。
比如删除操作，双向链表拿到待删除节点p之后，直接p->prev->next = p->next，再p->next->prev = p->prev，两步搞定，根本不需要找前驱。再比如要在某个已知节点p的前面插入一个节点s，双向链表同样可以直接找到p->prev，调整指针完成插入。
1.3 双向链表的适用场景
- 需要频繁在已知节点前后做插入、删除操作的场景，比如LRU缓存淘汰、内存管理中的空闲块回收。
- 需要双向遍历的场景，比如浏览器的前进/后退历史记录、文本编辑器的撤销/重做堆栈。
- 实现某些高级数据结构的基础部件，比如Linux内核的list_head、Redis的quicklist都用到了双向链表的思想。
2. 双向链表的核心结构设计与底层原理
2.1 节点结构：三个字段的职责划分
在C语言里，双向链表的节点定义大概是这样的：
typedef struct DNode { int data; // 数据域，存实际数据 struct DNode *prev; // 前驱指针，指向前一个节点 struct DNode *next; // 后继指针，指向后一个节点 } DNode, *DLinkList;有些教材里你会看到这个结构体里还顺便存了数据长度、或者额外加了mutex锁之类的字段，那是工程化改造，不必纠结。核心就三个字段：data、prev、next。data类型根据实际需求来，可以是int、char，也可以是一个结构体。
2.2 带头结点还是不带头结点
初学链表时候最纠结的一个问题就是：到底要不要头结点？
我的看法很简单：学习阶段和考试答题，带头结点永远是更稳妥的选择。理由有两个：
- 带头结点可以统一空表和非空表的操作逻辑。空表时，头结点的prev和next都指向NULL，插入第一个节点时不需要对头指针做特殊处理；如果不带头结点，空表插入要改头指针本身，很多新手就是在这一步忘了给头指针重新赋值，导致链直接丢了。
- 带头结点时，头指针永远指向头结点，即使链表为空，头指针也不会是NULL，这样遍历、判断空表的代码会简单很多。
当然，不带头结点也能写，但需要处理的操作分支会多一些。实际工程里两者都有，但我强烈建议你先在带头结点的写法上把逻辑练熟，再去理解无头结点的变体。
2.3 循环双向链表：把首尾接成一个环
如果让尾节点的next指向头结点，同时让头结点的prev指向尾节点，双向链表就升级成了循环双向链表。这个结构在实际使用中特别常见，因为它解决了两个问题：
- 从任意节点出发，可以访问到链表中的所有节点，不需要一定从头开始。
- 头结点和尾节点之间形成闭环，正序遍历和逆序遍历都非常方便。
循坏双向链表的判断空表条件也变了：不再是head->next == NULL，而是head->next == head（即尾节点的next又指回头结点，如果整个表只有头结点自己，那next和prev都指向头结点自己）。
3. 双向链表核心操作拆解与C语言实现
3.1 初始化与创建链表：先搞定“地基”
初始化带头结点的空双向链表：
DLinkList initList() { DLinkList head = (DLinkList)malloc(sizeof(DNode)); if (head == NULL) { exit(1); // 内存分配失败，果断退出，别硬撑 } head->prev = NULL; head->next = NULL; return head; }注意这里头结点的prev和next都要置空，否则就是一个野指针，后面遍历或者判断空表的时候会出大问题。面试或者考试时，很多人初始化只给了next=NULL，忘了prev，这是非常典型的低级错误。
接下来创建链表，常用两种方式：头插法和尾插法。头插法建出来的链表和数据输入顺序相反，尾插法则保持一致。写双向链表的插入逻辑之前，我强烈建议你先在纸上画一个三节点的链表图，标清楚指针，再对照着写代码，能少踩一半的坑。
3.2 插入操作：四步指针修改，顺序不能乱
在节点p后面插入新节点s，核心代码是四步：
s->next = p->next; // 1. 新节点先连接后继 s->prev = p; // 2. 新节点连接前驱 if (p->next != NULL) { p->next->prev = s; // 3. 原后继的prev指向新节点（注意判空） } p->next = s; // 4. 前驱的next指向新节点很多人会问：这四步的顺序能不能换？可以换，但有一条铁律：在把p->next指向s之前，必须先保存好原来的p->next，否则原后继就找不到了。上面的四步里，第1步先让s->next指向原后继，就相当于把退路都安排好了，接下来再怎么改p->next都不慌。
这里有个小细节很容易被人忽略：如果p是尾节点，那么p->next本身就是NULL，第3步前要先判断p->next是否为NULL。带头结点的写法里，因为尾节点next为空，直接影响就是p->next->prev = s这行代码会空指针崩溃。所以我在给学员讲的时候，一定强调先画图、再写码。
如果要在p节点之前插入s呢？在不额外遍历的情况下，可以利用p->prev：
s->prev = p->prev; s->next = p; if (p->prev != NULL) { p->prev->next = s; // 同样要判空 } p->prev = s;本质上还是四步，只是把方向反过来。掌握了“后插”，前插就是后插的镜像操作。
3.3 删除操作：两行代码搞定，前提是链要接对
删除节点p的核心逻辑：
if (p->prev != NULL) { p->prev->next = p->next; } if (p->next != NULL) { p->next->prev = p->prev; } free(p);如果p是头结点，千万别删，头结点删了整条链就没了。如果p是尾节点，那么p->next为NULL，第二个if不执行。如果链表只有一个有效节点，两个if同时成立，删除后头结点的next和prev都变为NULL，链表回到空表状态，完全符合预期。
很多资料喜欢把删除写成“p->prev->next = p->next; p->next->prev = p->prev;”两行，但这个写法在p是头结点或尾节点时会出问题。所以实际工程里，我习惯加判空，宁可多写两行也不愿意半夜被线上故障叫醒。
3.4 遍历和查找：正着走、反着走都随意
正向遍历：
void printListForward(DLinkList head) { DNode *cur = head->next; while (cur != NULL) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); }反向遍历：
void printListBackward(DLinkList 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)，这一点不管单双链表都一样。
3.5 完整示例：一个极简的成绩管理
下面给一个完整的、可跑的C语言示例，功能是创建学生成绩链表、按学号顺序插入、按学号删除、输出成绩单。代码我刻意保持简洁，方便你直接拿去跑。
#include <stdio.h> #include <stdlib.h> typedef struct Student { int id; // 学号 int score; // 成绩 struct Student *prev; struct Student *next; } Student, *StuList; StuList initList() { StuList head = (StuList)malloc(sizeof(Student)); if (head == NULL) { exit(1); } head->id = 0; head->score = 0; head->prev = NULL; head->next = NULL; return head; } // 按学号顺序插入（升序） void insertByOrder(StuList head, int id, int score) { Student *s = (Student *)malloc(sizeof(Student)); s->id = id; s->score = score; Student *cur = head->next; // 找到第一个学号大于等于id的节点，插在它前面 while (cur != NULL && cur->id < id) { cur = cur->next; } if (cur == NULL) { // 插到尾部 Student *tail = head; while (tail->next != NULL) { tail = tail->next; } tail->next = s; s->prev = tail; s->next = NULL; } else { // 插到cur前面 s->next = cur; s->prev = cur->prev; if (cur->prev != NULL) { cur->prev->next = s; } cur->prev = s; } } // 按学号删除 int deleteById(StuList head, int id) { Student *cur = head->next; while (cur != NULL && cur->id != id) { cur = cur->next; } if (cur == NULL) { return 0; // 没找到 } if (cur->prev != NULL) { cur->prev->next = cur->next; } if (cur->next != NULL) { cur->next->prev = cur->prev; } free(cur); return 1; } void printForward(StuList head) { Student *cur = head->next; while (cur != NULL) { printf("(id=%d, score=%d) ", cur->id, cur->score); cur = cur->next; } printf("\n"); } int main() { StuList head = initList(); insertByOrder(head, 102, 90); insertByOrder(head, 101, 88); insertByOrder(head, 103, 95); printForward(head); // 输出: (id=101, score=88) (id=102, score=90) (id=103, score=95) deleteById(head, 102); printForward(head); // 输出: (id=101, score=88) (id=103, score=95) return 0; }这段代码我特意把“插到尾部”和“插到中间”分开处理，方便你理解边界情况。运行结果符合预期：插入自动排序，删除后顺序依然保持。
4. 性能分析：双向链表到底快在哪、慢在哪
4.1 时间复杂度对照：不能只看“删除O(1)”
很多帖子张口就是“双向链表删除节点是O(1)”，这个说法其实是有前提的：你得已经拿到了目标节点的指针。如果只知道值要按值删除，那还是得先O(n)遍历找到目标节点，删除本身确实是O(1)，但查找的O(n)省不掉。
| 操作 | 单链表 | 双向链表 |
|---|---|---|
| 头插 | O(1) | O(1) |
| 已知节点后插 | O(1) | O(1) |
| 已知节点前插 | O(n)（需要找前驱） | O(1)（直接用prev） |
| 已知节点删除 | O(n)（需要找前驱） | O(1)（直接用prev） |
| 按值查找 | O(n) | O(n) |
| 获取表长 | O(n) | O(n) |
一目了然，双向链表真正的优势在于“已知节点周围的操作”，这些操作不需要额外遍历，代价就是每个节点多存一个指针字段。
4.2 空间开销：多一个指针带来的真实成本
64位系统里，一个指针占8个字节。假设数据域是4字节的int，单链表有效数据占4字节+8字节指针=12字节；双向链表是4字节+8字节+8字节=20字节。也就是说，双向链表比单链表每个节点多出约67%的指针开销。如果数据量是千万级，这个差距就是实打实的内存成本，嵌入式场景里甚至可能直接导致分配失败。
所以选型的时候要权衡：如果业务里绝大多数操作都是遍历、很少在已知位置插入删除，双向链表并不划算；如果频繁需要在中间插入删除、又需要双向回溯，那么多花的指针空间完全值得。
4.3 缓存友好性：链表的“隐藏短板”
这里补一个很多人忽略的点：链表是节点分散在堆内存里的，遍历时CPU缓存命中率远低于连续内存的数组。在数据量小的时候差别不明显，一旦链表节点过万，频繁的指针跳转会带来显著的访存开销。这也是为什么现代工程里，纯链表的应用场景在减少，很多库都倾向于用“数组+索引”或者“混合结构”。
比如Redis在3.2版本之后，list对象的底层就升级成了quicklist，本质上是用双向链表把多个连续数组串起来，兼顾了链表灵活插入和数组缓存友好的优点。这说明什么？说明理解双向链表的价值，不仅要会手写，还要知道它的短板在哪，才能在真实场景里做出合理选型。
5. 常见错误、面试高频考点与避坑实录
5.1 我自己踩过的坑：五个让人抓狂的bug
第一个坑：插入时只连一半。我早期写双向链表插入，经常写完s->next和s->prev，忘了更新原节点的prev或next，结果链表断成两截。后来我养成了一个习惯：写完插入代码，先完整走一遍逻辑——s的四个指针都指向谁、前后节点的两个指针都指向谁，全部核对一遍再编译。
第二个坑：忘掉头结点的prev初始化。初始化时只写了head->next = NULL，忘了head->prev = NULL。这个问题在插入删除时不一定立刻暴露，但一旦你写“从尾到头遍历”，程序直接就崩了。所以初始化那两行，我用注释标清楚，绝不偷懒。
第三个坑：删除指针后继续使用。free(p)之后，p变成悬空指针，如果后面还试图访问p->data，结果不可预知。这种bug最可恶，因为不一定每次崩溃，有时候数据恰好还能读出来，掩盖了问题，换个数据规模才炸。
第四个坑：边界判断少写一个if。删除尾节点时不判断p->next是否为NULL，直接p->next->prev = p->prev，一执行就是一个空指针异常。这个坑在链表操作里出现频率极高，属于典型的新手失误。
第五个坑：循环链表里死循环。把双向链表改成循环链表后，遍历的终止条件如果你还写cur != NULL，那就永远退不出来。循环列表必须判断cur是否回到头结点或某个标记节点。
5.2 高频面试题：这些题几乎必考
第一题：在不给定头指针的情况下，怎么删除一个已知节点p？
这不是常规的“把前驱的next指向后继”，因为你拿不到前驱指针，正常的双向链表里你是可以拿到prev的，但如果题目限定是单链表呢？经典解法是“值覆盖”：把p->next的数据复制到p，然后删除p->next。注意p是尾节点时需要做特殊处理（因为你没法找p->next），一般会先判断，如果p是尾节点，只能从头遍历找前驱了。这道题考察的就是你对链表的理解深度，而不是死记代码。
第二题：手写LRU缓存淘汰。
LRU（最近最少使用）是面试高频中的高频，经典实现就是“哈希表+双向链表”。哈希表保证O(1)查找，双向链表保证O(1)插入删除。每次访问一个key，如果命中就把它移到链表头部；一旦缓存超过容量，就删除链表尾部的节点。用单链表行不行？理论上能凑合，但删除尾节点需要找前驱，就退化成了O(n)。此刻双向链表的价值体现得淋漓尽致。
第三题：为什么Redis的list不直接用数组？
因为list需要频繁在两端做push/pop操作，数组在头部操作要O(n)搬移数据。而双向链表天然支持头尾O(1)操作。后来Redis改用quicklist，也是吸取了双向链表内存分散、指针开销大的教训，做了工程上的折中。
5.3 学习建议：怎么把双向链表练到肌肉记忆
我一直跟人讲一句话：链表这玩意，光看书等于白看，必须上手写，最好写出bug来，再一个个修。给你一个自检清单：
- 用一张纸画出带头结点双向链表的空表、一个节点、两个节点三种状态，标清楚所有prev和next。
- 手写初始化、尾插、头插、指定位置插入、指定位置删除、正序和逆序打印。
- 把所有边界条件想清楚：空表插入、尾部插入、尾部删除、删除唯一节点。
- 把带头结点改成不带头结点，对比差异在哪。
- 把双向链表改成循环双向链表，再跑一遍之前的测试用例。
如果你能把这五步走完，笔试环节遇到链表题基本就是送分题。
5.4 工程选型心得：什么时候别用双向链表
最后聊点选型的心得。很多人学了双向链表之后，写什么都想用，这其实是个误区。给你几个我的经验：
- 如果主要操作是遍历读取，很少在中间插入删除，优先用数组或ArrayList，内存连续、遍历快。
- 如果主要操作是头尾插入删除，可以用双端队列（deque），底层可能是分块数组，性能更稳。
- 如果确定需要频繁在已知节点前后插入删除，双向链表才是不二选择。
- 如果项目对内存极其敏感，比如单片机开发，多一个指针字段可能都是负担，能用单链表和数组解决的绝不硬上双向链表。
我自己在实际项目里的体会是：双向链表就像一把好用的扳手，但你不能拿扳手去拧螺丝。选型之前先把场景看清楚，再决定用不用它，这才是工程思维。
最后再分享一个小技巧：你可以在带头结点的循环双向链表基础上，用一个“头结点+长度”字段封装一个通用List，这样不管头插、尾插、还是按位置插，全是O(1)级别的操作，代码复用率极高。我在课程设计里就是这么干的，后来做项目也一直沿用这套思路。如果你正在学数据结构，不妨也试试自己封装一个，跑通之后你会发现自己对指针的理解深了一个层次。
