数据结构：双向链表（Doubly Linked List）
目录
引入反向指针：双向链表的核心思想
插入（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 < pos && temp->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 < pos && temp->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 < pos; ++i) {if (current == nullptr) return;current = current->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 < pos && current != nullptr; ++i) {current = current->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 < pos && current != nullptr; ++i) {current = current->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;
}