数据结构：双向链表（Doubly Linked List） - 详解
9442
目录
引入反向指针：双向链表的核心思想
插入（Inserting）节点
插入时修改指针的顺序是什么？
删除（Deleting）节点
删除操作是什么顺序？
需不需要修改 curr 的指针？
单向链表的局限：单向链表只能单方向访问 —— 一旦你从 A 走到了 C，你就无法回头，除非你从头开始再走一遍。
这对一些需要双向遍历、删除任意节点、从尾部反向操作的任务来说很低效。比如手机通讯录中，你可以自由的上下滚动，既可以向前也可以向后”遍历“你要寻找的联系人。否则只能浏览到Z后，重新从A开始查找。
引入反向指针：双向链表的核心思想为了解决“不能往回走”的问题，我们在每个节点中增加一个“反向指针”：prev
所以，双向链表（Doubly Linked List） 的每个节点结构如下：
数据（data）
指向下一个节点的指针（next）
指向前一个节点的指针（prev）
结构示意：
NULL ← [A] ⇄ [B] ⇄ [C] → NULL
从第一性看，本质结构是：
typedef struct DNode {
int data;
struct DNode* next;
struct DNode* prev;
} DNode;
双向链表 = 带有前后连接的双向路径图
如果你从图论角度来看：
单向链表是一条有向链路
双向链表是每两个节点之间有两个相反方向的边
它在内存中构成一个可逆的线性结构：
prev ← node → next
这种结构允许我们：
正向遍历：从头到尾走 next
反向遍历：从尾到头走 prev
插入（Inserting）节点我们要做的是：给定一个值 value，把它插入到双向链表中的某个位置 pos，并保持链表结构的正确性。
但在双向链表中，每个节点有两个方向，我们要处理 四个指针连接：
prev newNode next
这就意味着，插入的本质操作就是：
断开原来的链接（或在其间插入），再建立四条新的指针连接。
我们需要针对不同位置分类讨论，每个位置都有不同的结构要求。
插入位置条件举例插入到空链表head == nullptr第一次插入插入到头部pos == 0在原来第一个节点前面插入到中间或尾部pos > 0插入某个节点中间或尾部插入时修改指针的顺序是什么？
prevNode currentNode nextNode
我们假设插入点在某个节点 curr 的前面。
第一步：设置 newNode->prev = prev
告诉 newNode 它“从哪儿来”，即它前面的节点是谁。
此时你还没修改周围节点的任何东西，所以：
prev 和 curr 的结构是稳定的
prev 肯定还指向 curr
所以你可以安全地获取 prev，设置给新节点的 prev
为什么第一步必须是这句？
因为你之后会改掉 prev->next，一旦改了，prev 可能不再指向 curr，你失去了“原位置”的上下文。
所以第一性原则：先让新节点记录旧关系。
第二步：设置 newNode->next = curr
告诉 newNode 它“要去哪儿”，即它后面的节点是谁。
此时链还没断，curr 仍是 prev->next，仍能安全访问。
如果你先断开 prev->next，可能就不再能定位 curr。
所以这一步必须在修改外部节点前完成。
到目前为止：
prevNode newNode nextNode
? ← [data] → ?
第三步：设置 prev->next = newNode
让前一个节点知道“我后面变成谁了”。
这是第一次改变外部结构。
为什么不能提前做这步？
因为一旦做了这步，你就“断开了” prev → curr，如果你还没告诉 newNode 它的后继是谁，就找不到 curr 了。
第四步：设置 curr->prev = newNode
让后一个节点知道“我前面是谁变了”。
到这里，才安全更新 curr->prev。
如果你在更早的时候改掉 curr->prev，而 newNode->next 还没设置好，那 curr 指向的“前一个节点”可能变成一个未初始化的指针（悬空指针）。
步骤原则为什么必须先做newNode->prev = prev先保存旧结构信息一旦链断就找不到原来的节点newNode->next = curr初始化新节点的完整结构保证访问 curr 安全prev->next = newNode开始改变原链结构此时 newNode 已准备好curr->prev = newNode完成双向连接确保 curr 的反向遍历安全插入的顺序必须是：
先设新节点的内部结构，后修改旧节点的连接。
原因是：你只有在结构还完整、未被破坏时，才能安全地访问相关节点，提取它们的指针，设置给新节点。
就像你搬进一间房子：
先摆好自己的家具（内部状态）
再去告诉邻居“我住这里了”（外部链接）
我们回到刚才的内容，讲解插入位置的三种情况：
void insert(Node*& head, int value, int pos);
使用引用 Node*& 是因为插入头部时可能需要修改 head 本身
value 是要插入的值
pos 是目标插入位置（从 0 开始计数）
1. 插入到空链表（head == nullptr）
这时候链表中没有任何节点。我们直接构造一个节点，并把 head 指向它：
if (head == nullptr) {
head = new Node(value);
return;
}
2. 插入到头部（pos == 0）
Node* newNode = new Node(value);
newNode->next = head; // 第一步：新节点向后指
head->prev = newNode; // 第二步：原 head 向前指
head = newNode; // 第三步：更新 head
3. 插入到中间或尾部（pos > 0）
我们要在第 pos 个位置插入，所以需要：
从 head 开始向后走 pos - 1 步
令当前节点为 prevNode
注意：nextNode 有可能是 nullptr（表示在尾部插入）
Node* temp = head;
for (int i = 1; i next != nullptr; ++i) {
temp = temp->next;
}
Node* newNode = new Node(value);
// temp 是前驱，temp->next 是后继
newNode->prev = temp;
newNode->next = temp->next;
if (temp->next != nullptr) {
temp->next->prev = newNode;
}
temp->next = newNode;
完整代码
void insert(Node*& head, int value, int pos) {
// 情况一：空链表
if (head == nullptr) {
head = new Node(value);
return;
}
// 情况二：插入到头部
if (pos == 0) {
Node* newNode = new Node(value);
newNode->next = head;
head->prev = newNode;
head = newNode;
return;
}
// 情况三：插入到中间或尾部
Node* temp = head;
for (int i = 1; i next != nullptr; ++i) {
temp = temp->next;
}
Node* newNode = new Node(value);
newNode->prev = temp;
newNode->next = temp->next;
if (temp->next != nullptr) {
temp->next->prev = newNode;
}
temp->next = newNode;
}
删除（Deleting）节点我们要删除双向链表中的第 pos 个节点（从 0 开始）
删除分三种情况：
删除位置条件删除头部pos == 0删除中间0 < pos < length - 1删除尾部pos >= length - 1（或 next 为 null）删除 = 什么指针需要改？
设目标节点是 current，前驱是 prev，后继是 next。
指针必须这样改：
prev->next = next;
next->prev = prev;
delete current;
删除操作是什么顺序？第一步：定位要删的节点
Node* current = head;
for (int i = 0; i next;
}
因为链表没有索引，想删第 pos 个节点就必须从头走 pos 步。
第二步：绕过当前节点
if (current->prev != nullptr) {
current->prev->next = current->next;
}
if (current->next != nullptr) {
current->next->prev = current->prev;
}
顺序不能反：你得先从 prev 连向 next，再从 next 连回 prev。改完这两条，current 就断开了。
因为如果curr 是尾节点，你写：
curr->next->prev = curr->prev; // 崩溃：访问 nullptr->prev
会导致程序崩溃，段错误。如果你先写 prev->next = curr->next;，它始终是安全的，即使 curr->next == nullptr，你只是赋值 nullptr 给 prev->next。
第三步：释放当前节点
delete current;
必须最后做。否则你前面的指针还没改就删了，后面访问会段错误。
需不需要修改 curr 的指针？你不需要也不应该主动修改 curr->prev 或 curr->next。
本质目的：删除一个节点，就是让它彻底从链表结构中“不可达”。
链表是通过节点之间互相指针连接形成的结构：
如果：
A->next = curr
curr->next = B
你删除 curr 的目标是：让 A 和 B 直接相连，跳过 curr。
如果你修改了 curr->next = nullptr 有什么问题？
它技术上不会出错，但完全是无意义操作，因为：
你马上就 delete curr;，写 curr->next = ... 就像擦桌子前倒杯水。
你不是把 curr 留在链表里，你是把它移除并销毁。
同理，curr->prev = nullptr; 也一样：它的值没用了，不会再访问它。
我们定义函数：
void remove(Node*& head, int pos);
情况 1：删除空链表（head == nullptr）
if (head == nullptr) return;
情况 2：删除头部（pos == 0）
head 本身要被删除，必须先更新 head
新的 head->prev = nullptr，因为它没有前驱
然后释放原来的头
if (pos == 0) {
Node* temp = head;
head = head->next;
if (head != nullptr) {
head->prev = nullptr;
}
delete temp;
return;
}
情况 3：删除中间或尾部节点
Node* current = head;
for (int i = 0; i next;
}
if (current == nullptr) return;
if (current->prev != nullptr) {
current->prev->next = current->next;
}
if (current->next != nullptr) {
current->next->prev = current->prev;
}
delete current;
完整代码
void remove(Node*& head, int pos) {
if (head == nullptr) return;
if (pos == 0) {
Node* temp = head;
head = head->next;
if (head != nullptr) {
head->prev = nullptr;
}
delete temp;
return;
}
Node* current = head;
for (int i = 0; i next;
}
if (current == nullptr) return;
if (current->prev != nullptr) {
current->prev->next = current->next;
}
if (current->next != nullptr) {
current->next->prev = current->prev;
}
delete current;
}