写数据结构相关的代码这么多年我有一个很深的体会单链表用起来确实顺手但真要往回找前驱节点的时候只能从头再遍历一遍总有种“开过头了还要倒车”的别扭感。后来用上双向链表两个方向都能走很多场景一下子就顺了。这篇就围绕双向链表展开带你把结构设计、插入删除的指针操作、带头结点和不带头结点的差异、逆置思路以及一份能直接跑起来的 C 实现完整过一遍。不管你是刚学数据结构的学生还是工作中需要手写链表的工程开发者这篇文章应该都能给你一些参考。1. 双向链表到底解决了什么问题1.1 从单链表的痛点说起链表的核心价值说白了就是“用不连续的内存通过指针把节点串起来”。单链表里每个节点只存了一个 next 指针指向下一个节点你只能从一个方向往前推进。这种结构有个很尴尬的缺点当你想删除某个节点或者想知道某个节点的前驱是谁就必须从头开始找复杂度是 O(n)。我当时做学生管理系统的时候就吃过这个亏。用户要删除某个学号对应的记录我的链表只存 next删除操作必须用一个 cur 和一个 prev 同步往前走。稍微走神或者边界条件没判断好指针就乱了。更难受的是如果业务上需要“从后往前处理数据”单链表几乎没法做只能先反转整个链表或者用栈来辅助。这些操作不是不行而是每次都要绕路代码里全是应对“只能前进”这种限制而写的补丁。双向链表的出现等于给每个节点补了一个 prev 指针让每个节点都知道“我前面是谁我后面是谁”。删除时不用再从头找前驱插入时也能直接拿到前后节点很多程序能写得非常自然。1.2 双向链表的结构定义一个节点多出的那一根指针双向链表节点比单链表节点只多了一个成员指向前驱节点的指针。C 语言的结构体写法大概是这样的typedef struct DNode { int data; // 数据域 struct DNode *prev; // 指向前驱节点 struct DNode *next; // 指向后继节点 } DNode;C 里如果你习惯用 struct 搭配构造函数可以写成这样struct Node { int data; Node* prev; Node* next; Node(int val) : data(val), prev(nullptr), next(nullptr) {} };你也可以用生活里的情景来理解这个结构一场演唱会入场观众排成一列每个观众手里拿着两个对讲机一个能联系到前面的人一个能联系到后面的人。这时候不管你是要通知前排的第一个人还是要通知后排的最后一个人都能直接对上话。这个“知道前面是谁”的能力就是 prev 指针带来的。如果用文字串一个三节点链表的话它的形态是nullptr - A - B - C - nullptrA 的 prev 是空C 的 next 是空中间节点的指针两两互相指向。这样的好处是从任意一个节点出发向前向后都能走通。1.3 双向链表与单链表、循环链表的使用场景对比双向链表并不是在所有场合都比单链表好多一个指针就多一份内存开销和维护复杂度。但如果把它放进真实业务场景里看几个典型场景很值得对比一下。对比维度单链表双向链表循环链表内存开销每节点 1 个指针每节点 2 个指针取决于单/双向找后继O(1)O(1)O(1)找前驱O(n)O(1)尾部找头 O(1)其他 O(n) 或 O(1) 取决于循环方向删除给定节点通常 O(n)O(1)双向循环 O(1)实现复杂度低中中偏高我个人的使用经验是如果业务只需要顺序扫描单链表完全够如果涉及频繁的“按照当前位置向前回退”比如浏览器历史记录、音乐播放器的上一首/下一首、编辑器里的撤销重做双向链表就特别合适。循环双向链表在需要快速访问“尾节点的下一个就是头节点”这种场景也常见比如分时操作系统的进程轮转就可以用这种结构来模拟环形队列。2. 核心操作拆解从初始化到遍历2.1 带头结点还是不带头结点我的选择很多教材里喜欢用带哨兵头结点的链表也就是说链表的最前面人为放一个不存储有效数据的节点它的 next 指向真正的第一个数据节点。还有一种方式是不带头结点head 指针直接指向第一个数据节点空链表时 head 为 nullptr。这两种方式没有绝对的好坏但我这里要给你一个明确的建议学习阶段先把“不带头结点”吃透写工程代码时再看项目风格决定。不带头结点更接近底层的真实状态空表就是 nullptr插入删除时的分支判断都要自己处理。刚开始会觉得麻烦但你把边界条件想清楚之后对指针理解会深很多。带头结点相当于给链表加了一个“缓冲区”头插和空表删除都不需要单独处理 head代码分支会少一些但要始终记得 head-next 才是真正的数据节点。用不带头结点初始化也就是一行代码Node* head nullptr;用带头结点初始化则是先 new 一个哨兵Node* dummy new Node(-1); dummy-next nullptr; dummy-prev nullptr;我觉得初学者可以先从不带头结点入手把所有边界问题亲手试一遍后续再切换到带哨兵的写法会非常轻松。2.2 插入操作先连新节点再断旧链接双向链表的插入最重要的口诀只有一句话先把新节点的两个指针都接好再修改旧节点的指针。这句话听起来简单但很多人第一次写的时候会翻车。我见过不少同学在头插时先把 head 的 prev 改了然后 new 节点的 next 还没指过去链表直接断成两截。我们分几种情况来看。头插在链表最前面插入bool pushFront(Node* head, int val) { Node* newNode new Node(val); if (head nullptr) { head newNode; return true; } newNode-next head; newNode-prev nullptr; head-prev newNode; head newNode; return true; }尾插在链表最后面插入bool pushBack(Node* head, int val) { Node* newNode new Node(val); if (head nullptr) { head newNode; return true; } Node* cur head; while (cur-next ! nullptr) { cur cur-next; } cur-next newNode; newNode-prev cur; return true; }指定位置插入就稍微复杂一点比如在第 index 个位置插入。核心是先通过循环把指针移动到目标位置的前一个节点 cur然后按照固定顺序接入bool insertAtIndex(Node* head, int index, int val) { if (index 0) return false; Node* newNode new Node(val); if (index 0) { newNode-next head; newNode-prev nullptr; if (head ! nullptr) head-prev newNode; head newNode; return true; } Node* cur head; for (int i 0; i index - 1 cur ! nullptr; i) { cur cur-next; } if (cur nullptr) return false; newNode-next cur-next; newNode-prev cur; if (cur-next ! nullptr) { cur-next-prev newNode; } cur-next newNode; return true; }为什么一定要先处理 newNode 的 next 和 prev因为这个时候 newNode 还独立在外面它怎么指都不会影响原链表。一旦你先把 cur-next 改了原链表右半段就找不到了你要想再把 newNode 串进去就需要额外用一个临时指针保存代码会麻烦得多。凡是涉及“插入”的操作先孤立新节点再拆旧链接这是个通用定律。2.3 删除操作两个方向的指针都要处理删除比插入更容易踩坑因为要释放内存指针一旦处理错要么崩溃要么泄漏。删除的关键在于先把节点从链中“摘下来”再 delete。分情况来看删头节点bool deleteFront(Node* head) { if (head nullptr) return false; Node* tmp head; head head-next; if (head ! nullptr) head-prev nullptr; delete tmp; return true; }删任意节点比如按值删除第一个匹配的节点bool deleteByValue(Node* head, int val) { if (head nullptr) return false; Node* cur head; while (cur ! nullptr cur-data ! val) { cur cur-next; } if (cur nullptr) return false; if (cur head) { head cur-next; if (head ! nullptr) head-prev nullptr; delete cur; return true; } if (cur-prev ! nullptr) cur-prev-next cur-next; if (cur-next ! nullptr) cur-next-prev cur-prev; delete cur; return true; }这里有个容易忽略的细节如果链表只有一个节点删除前 head 是 cur删除后 head 应该变成 nullptr。上面代码处理了 head 的情况所以这个边界自然覆盖到了。另外一个细节是删除完成后要把 cur 的指针成员也清理一下虽然 delete 之后不一定出问题但习惯上让 cur-prev cur-next nullptr 之后再 delete调试时可读性更好。面试时如果考“给定一个节点指针怎么在 O(1) 时间内删除它”双向链表就非常容易回答直接拿到 node-prev 和 node-next互相接起来再 delete node 就行完全不用从头遍历。2.4 遍历与前驱访问遍历双向链表和单链表没太大区别正着走一路 next 就行void printList(Node* head) { Node* cur head; while (cur ! nullptr) { std::cout cur-data - ; cur cur-next; } std::cout nullptr std::endl; }但是反向遍历就很舒服了只需要先走到最后一个节点然后一路走 prevvoid printReverse(Node* head) { if (head nullptr) return; Node* cur head; while (cur-next ! nullptr) cur cur-next; while (cur ! nullptr) { std::cout cur-data - ; cur cur-prev; } std::cout nullptr std::endl; }这个能力在需要“从后往前汇总”的业务里特别有用。比如你在做文件版本记录最新版本在尾部需要从最新往旧版本回溯用双向链表就能直接从尾巴往回遍历不需要反转链表。3. 可运行的C实现手把手写一份完整代码3.1 结构体定义与基本工具函数下面我给出一个相对完整的不带头结点双向链表实现。先建立一个头文件风格的完整主体方便你直接复制运行#include iostream struct Node { int data; Node* prev; Node* next; Node(int val) : data(val), prev(nullptr), next(nullptr) {} }; class DoublyLinkedList { private: Node* head; void destroy() { Node* cur head; while (cur ! nullptr) { Node* nextNode cur-next; cur-prev nullptr; cur-next nullptr; delete cur; cur nextNode; } head nullptr; } public: DoublyLinkedList() : head(nullptr) {} ~DoublyLinkedList() { destroy(); } bool empty() const { return head nullptr; } void pushFront(int val) { Node* newNode new Node(val); if (head nullptr) { head newNode; return; } newNode-next head; newNode-prev nullptr; head-prev newNode; head newNode; } void pushBack(int val) { Node* newNode new Node(val); if (head nullptr) { head newNode; return; } Node* cur head; while (cur-next ! nullptr) cur cur-next; cur-next newNode; newNode-prev cur; } bool insertAtIndex(int index, int val) { if (index 0) return false; Node* newNode new Node(val); if (index 0) { pushFront(val); return true; } Node* cur head; int i 0; while (cur ! nullptr i index - 1) { cur cur-next; i; } if (cur nullptr) return false; newNode-next cur-next; newNode-prev cur; if (cur-next ! nullptr) { cur-next-prev newNode; } cur-next newNode; return true; } bool deleteByValue(int val) { if (head nullptr) return false; Node* cur head; while (cur ! nullptr cur-data ! val) cur cur-next; if (cur nullptr) return false; if (cur head) { head cur-next; if (head ! nullptr) head-prev nullptr; } else { if (cur-prev ! nullptr) cur-prev-next cur-next; if (cur-next ! nullptr) cur-next-prev cur-prev; } cur-prev nullptr; cur-next nullptr; delete cur; return true; } void print() const { Node* cur head; while (cur ! nullptr) { std::cout cur-data - ; cur cur-next; } std::cout nullptr std::endl; } void printReverse() const { if (head nullptr) return; Node* cur head; while (cur-next ! nullptr) cur cur-next; while (cur ! nullptr) { std::cout cur-data - ; cur cur-prev; } std::cout nullptr std::endl; } }; int main() { DoublyLinkedList list; list.pushBack(1); list.pushBack(2); list.pushBack(3); list.pushFront(0); list.print(); // 0 - 1 - 2 - 3 - nullptr list.insertAtIndex(2, 99); list.print(); // 0 - 1 - 99 - 2 - 3 - nullptr list.deleteByValue(1); list.print(); // 0 - 99 - 2 - 3 - nullptr list.printReverse(); // 3 - 2 - 99 - 0 - nullptr return 0; }这份代码里有几个细节我觉得值得单独拿出来说一说。一个是 destroy 函数。我看到很多教材在析构里直接 while 循环 delete cur然后 cur cur-next。这样写顺序上其实是危险的因为 delete cur 之后cur-next 已经属于已释放内存再去访问它是未定义行为。正确做法是先把下一个节点指针存下来再释放当前节点。我在 destroy 里用 nextNode 暂存的办法就是为了避免悬垂指针。另一个细节是 insertAtIndex 的第 0 位置我直接复用了 pushFront避免逻辑重复。很多初学者会写两套非常相似的头插逻辑后续维护时容易改了这个忘了那个。3.2 指定位置插入的完整实现与运行示例指定位置插入是最能体现“双指针聪明之处”的一个操作。前面代码里给了实现这里我用一个具体例子帮你逐步拆解。假设当前链表是nullptr - 0 - 1 - 2 - 3 - nullptr我想在 index 等于 2 的位置插入 99也就是期望结果nullptr - 0 - 1 - 99 - 2 - 3 - nullptr代码里 cur 要移动到 index - 1也就是下标为 1 的节点值为 1。这时候newNode-next cur-next于是 99 的 next 指向了 2。newNode-prev cur于是 99 的 prev 指向了 1。cur-next-prev newNode于是 2 的 prev 指向了 99。cur-next newNode于是 1 的 next 指向了 99。新节点进来后原来的 1 - 2 链接变成了 1 - 99 - 2完美插入。这个过程中最关键的是第二步和第三步的顺序必须保证 99 已经“握住了”2再让 2 回头指向 99。如果你先把 1-next 改成 99那么 2 就随着断开的链接一起丢失了后面的步骤就会出错。index 越界时比如 index 等于 100for 循环会一直走到 cur 为 nullptr这时候直接返回 false 即可。这个越界判断是很多刚写链表的人容易漏掉的漏掉的后果就是空指针访问程序直接崩。3.3 双向链表的逆置技巧逆置链表是热搜词里的高频内容双向链表逆置其实比单链表更直观因为每个节点都有两个方向的指针逆置的本质就是“把每个节点的两个指针交换方向”然后把头指针指向原来的尾巴。思路是这样的从 head 开始遍历每个节点把 node-next 和 node-prev 交换。遍历结束后原来链表的最后一个节点变成新的 head。用代码实现void reverse() { if (head nullptr) return; Node* cur head; Node* newHead head; while (cur ! nullptr) { std::swap(cur-next, cur-prev); newHead cur; cur cur-prev; // 交换后原 next 变成了 prev } head newHead; }这里最容易踩的坑在遍历移动那一步。交换 next 和 prev 之后原来 cur 的后继节点变成了 cur-prev所以你必须用 cur cur-prev 而不是 cur cur-next。我第一次写这个函数时交换之后下意识继续走 cur cur-next结果死循环后来画了一下图才反应过来。这就是那种“代码只有一行逻辑却要思考五分钟”的典型例子。如果你想保持泛化性也可以用递归逆置但链表一长就容易爆栈实际工程中我更推荐这个原地 O(1) 空间的迭代版。3.4 内存释放写链表最容易忽略的环节很多教材写链表只讲插入删除不讲析构导致很多同学学完整章后对“链表到底要不要释放内存”完全没有概念。实际上链表节点全是 new 出来的不释放就是内存泄漏程序跑久了内存会越来越大。双向链表释放时要注意如果节点里还有指向其他动态分配资源的指针需要先释放那些资源再释放节点本身。节点本身的内存释放顺序建议先断开 prev 和 next 指针再用 delete 删除节点最后再把 cur 指向暂存的下一个节点。代码已经在 3.1 节的 destroy 里体现。我还见过一种非常隐蔽的泄漏删除节点时没有把 cur-prev 和 cur-next 置空就 delete。表面上看内存是释放了但如果这个 cur 还被其他地方引用而引用它的代码又在做梦那么访问 cur-next 就是一个悬垂指针轻则读到垃圾值重则直接段错误。所以我个人习惯在 delete 之前把节点的 prev 和 next 都置为 nullptr。这不是 C 规范要求的但能减少调试时的迷惑。4. 常见问题与排查实录4.1 经典翻车现象一插入后链表断成两截这是双向链表初学者最容易遇到的问题。现象是插入了新节点但打印链表时发现只能打到某个位置后面全部丢失。比如原链表 1-2-3在中间插入 4 后输出变成 1-4后面 2、3 都不见了。原因几乎总是出在插入顺序上。比如你先执行了 cur-next newNode那么原链表中 cur 的后半段就通过原来的 cur-next 断开了。此时如果 newNode 的 next 还没有指到原来的后半段这部分链表就成了孤儿区。解决办法就是我在 2.2 节强调的先让 newNode-next 指向 cur-next再改 cur-next。也就是说新节点必须先“握住旧链接的右边”旧节点才能“松开手”。排查思路也很简单不要盯代码硬看画箭头图最有效。把 cur、newNode、cur-next 三个节点画出来给每个指针画一条线按代码执行顺序一步步连线断点一眼就能看出来。4.2 经典翻车现象二空指针访问导致崩溃空指针崩溃一般出现在三种情况链表为空时执行插入或删除尾插时 cur 跑到 nullptr 却没发现删除时没有判断 cur-next 是否为空就直接访问 cur-next-prev。典型代码长这样// 错误示范 cur-next-prev newNode;如果 cur-next 是 nullptr这行代码直接崩。正确写法是先判断再操作if (cur-next ! nullptr) { cur-next-prev newNode; }还有一种情况是“删除尾巴节点”。当 cur-next 为 nullptr你执行 cur-prev-next cur-next也就是把前驱的 next 设为 nullptr这没问题。但如果你不判断 cur-prev 是否存在删除头节点时就会出问题。好在删除头节点我们已经有单独分支处理这也是为什么我建议删除操作先判断 cur head。排查空指针崩溃最好的工具其实就是调试器。在崩溃那一行看调用栈找到是哪个指针是 nullptr然后往前梳理它的值是什么时候变成 nullptr 的。链表调试十次有九次都是这么查出来的。4.3 经典翻车现象三删除节点后链表全乱删除节点的典型错误有两个方向一是“忘接”删完一个节点后前驱的 next 和后继的 prev 没有正确对接链表断成两段二是“接错”比如写了 cur-prev-next cur-prev把前驱的 next 指向了自己形成环。第二个问题特别危险因为它不会立刻崩溃而是会让遍历陷入死循环程序看起来“卡住”。比如打印链表时输出一直在重复同一个节点那八成就是指针形成了环。我的排查建议是在 delete 节点之前先用临时节点把需要保留的信息保存好。删之前问自己三句话前驱的 next 应该指向哪里后继的 prev 应该指向哪里如果要释放当前节点我是不是已经保存了下一步需要访问的位置这三句话都想清楚删除节点基本不会出错。另一点删除节点和释放内存是两件事摘链和 delete 最好分开写别在一行里玩花活否则出了问题不容易定位。4.4 面试与考试中的双向链表高频考点这些年看过的链表题和面试题双向链表相关的考点其实很集中。最常考的是给定一个节点指针O(1) 时间内删除该节点。你只需要访问它的 prev 和 next把两者串起来再删除当前节点。这就是双向链表比单链表“值钱”的核心点。第二个高频考点是“双向链表的逆置”。考题经常会在末尾加一句“要求原地实现空间复杂度 O(1)”那就是要求你用 swap next/prev 的迭代法而不是新建一个链表。平时在一张纸上手写几遍这个代码面试时就能写得又快又稳。第三个高频考点是“带头结点的双向循环链表”。这种结构在 Linux 内核链表里非常常见它的特点是 head 的 prev 指向尾节点尾节点的 next 指向 head遍历时既可以正向走一圈回到头也可以反向走一圈。写这种链表时最关键的是在插入和删除时保持循环性质的完整性也就是所有涉及边界节点的地方都要考虑“最后一个节点的 next 其实是 head”而不是 nullptr。我个人的学习建议是把 3.1 节那份代码自己默写一遍然后试着改成带头结点的版本再改成循环版本。三种形态都写一遍你对链表结构的理解就算真正过关了。最后说一个很实在的调试经验链表这类指针操作的问题绝大多数都能靠“在纸上画方框和箭头”解决别急着在 IDE 里不停加打印。调试打印输出很重要尤其可以写一个像 printList 一样的辅助函数在每次插入删除后打一遍全链表这样能直观看到结构被改成了什么样。想追踪当前节点就打印当前节点和前驱后继的地址比对地址是否和你预想的一致。这个习惯我用了很多年可以说帮我在各种指针迷宫里少走了一半弯路。