双向链表核心操作详解：结构、插入删除、逆置与C++实现

写数据结构相关的代码这么多年，我有一个很深的体会：单链表用起来确实顺手，但真要往回找前驱节点的时候，只能从头再遍历一遍，总有种“开过头了还要倒车”的别扭感。后来用上双向链表，两个方向都能走，很多场景一下子就顺了。这篇就围绕双向链表展开，带你把结构设计、插入删除的指针操作、带头结点和不带头结点的差异、逆置思路，以及一份能直接跑起来的 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 -> nullptr

A 的 prev 是空，C 的 next 是空，中间节点的指针两两互相指向。这样的好处是，从任意一个节点出发，向前向后都能走通。

1.3 双向链表与单链表、循环链表的使用场景对比

双向链表并不是在所有场合都比单链表好，多一个指针就多一份内存开销和维护复杂度。但如果把它放进真实业务场景里看，几个典型场景很值得对比一下。

我个人的使用经验是：如果业务只需要顺序扫描，单链表完全够；如果涉及频繁的“按照当前位置向前回退”，比如浏览器历史记录、音乐播放器的上一首/下一首、编辑器里的撤销重做，双向链表就特别合适。循环双向链表在需要快速访问“尾节点的下一个就是头节点”这种场景也常见，比如分时操作系统的进程轮转，就可以用这种结构来模拟环形队列。

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; }

但是反向遍历就很舒服了，只需要先走到最后一个节点，然后一路走 prev：

void 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 等于 100，for 循环会一直走到 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 一样的辅助函数，在每次插入删除后打一遍全链表，这样能直观看到结构被改成了什么样。想追踪当前节点，就打印当前节点和前驱后继的地址，比对地址是否和你预想的一致。这个习惯我用了很多年，可以说帮我在各种指针迷宫里少走了一半弯路。