Appearance
双链表
为什么需要双链表
单链表中每个结点只有一个指向后继的指针，因此只能从前往后遍历。如果需要查找某个结点的前驱，就必须从头结点重新遍历，时间复杂度为 O(n)。
双链表在单链表的基础上，为每个结点增加了一个指向前驱的指针 prior，使得链表可以双向遍历。这在需要频繁访问前驱结点的场景中（如 LRU 缓存、编辑器撤销操作）非常高效。408 考研中，双链表是链表章节的重要组成部分，插入和删除操作的指针修改顺序是选择题和代码题的高频考点。
核心思想
双链表的核心特点：
- 双向链接：每个结点包含
prior（前驱指针）、data（数据域）、next（后继指针）三个部分 - 双向遍历：既可以从前往后，也可以从后往前遍历
- O(1) 访问前驱：已知某结点时，可以直接通过
prior指针找到其前驱，无需从头遍历
结点结构示意：
┌───────┬──────┬───────┐
│ prior │ data │ next │
└───────┴──────┴───────┘结点定义（C 语言）：
c
typedef struct DNode {
ElemType data;
struct DNode *prior, *next;
} DNode, *DLinklist;与单链表类似，双链表通常也设置头结点，头结点的 prior 为 NULL，尾结点的 next 为 NULL。
双链表插入操作：4 步指针修改
在结点 p 之后插入新结点 s，必须按正确顺序修改 4 个指针，避免断链：
关键：第 1、2 步必须在第 4 步之前执行，否则
p->next被覆盖，原后继结点地址丢失。
交互可视化
通过下方的交互动画，你可以逐步观察双链表的执行过程：
操作详解
插入操作
在结点 p 之后插入新结点 s，需要修改四个指针。注意修改顺序，避免断链。
关键步骤：
s->next = p->next（新结点指向 p 的后继）- 若
p->next != NULL，则p->next->prior = s（原后继的前驱指向新结点） s->prior = p（新结点的前驱指向 p）p->next = s（p 的后继指向新结点）
要点：步骤 1、2 必须在步骤 4 之前完成，否则
p->next会被覆盖，导致原后继结点丢失。
c
// 在 p 结点之后插入结点 s
bool InsertNextDNode(DNode *p, DNode *s) {
if (p == NULL || s == NULL) return false;
s->next = p->next;
if (p->next != NULL)
p->next->prior = s;
s->prior = p;
p->next = s;
return true;
}删除操作
删除结点 p 的后继结点 q，需要修改两个指针，然后释放 q 的空间。
关键步骤：
p->next = q->next（p 的后继跳过 q，指向 q 的后继）- 若
q->next != NULL，则q->next->prior = p（q 的后继的前驱指向 p） free(q)（释放被删除结点的空间）
c
// 删除 p 结点的后继结点
bool DeleteNextDNode(DNode *p) {
if (p == NULL || p->next == NULL) return false;
DNode *q = p->next;
p->next = q->next;
if (q->next != NULL)
q->next->prior = p;
free(q);
return true;
}与单链表对比：单链表删除结点 p 的后继时只需修改一个指针（p->next），而双链表需要额外修改后继结点的 prior 指针。但双链表的优势在于——已知待删除结点本身时，可以 O(1) 完成删除，无需像单链表那样先找前驱。
复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 按位查找 | O(n) | 需从头结点依次遍历 |
| 按值查找 | O(n) | 最坏需遍历整个表 |
| 已知结点后插入 | O(1) | 直接修改前后指针 |
| 已知结点后删除其后继 | O(1) | 直接修改前后指针 |
| 已知结点删除自身 | O(1) | 可直接访问前驱，无需遍历（单链表需 O(n)） |
| 在给定位置插入（按位序） | O(n) | 需先遍历找到目标位置 |
空间复杂度：每个结点比单链表多一个 prior 指针，存储开销更大，属于典型的以空间换时间策略。
考研高频考点
- ⭐ 插入操作的指针修改顺序（选择题/代码题高频，顺序错误会导致断链）
- ⭐ 删除操作中对边界情况的处理（被删除结点是尾结点时
q->next == NULL） - ⭐ 双链表 vs 单链表的优缺点对比（简答题常考）
- 优点：支持双向遍历、已知结点可 O(1) 删除自身、查找前驱 O(1)
- 缺点：每个结点多一个指针域，存储开销更大；插入/删除时需维护更多指针
- ⭐ 已知结点删除自身的时间复杂度：双链表 O(1)，单链表 O(n)
- 双链表结点结构的存储密度（低于单链表，远低于顺序表）