双链表的基本操作 · 融合风（象牙 + Obsidian 入口）

速查

双链表在单链表基础上增加前驱指针 prior，可双向遍历。已知结点时删除/前插都是 O(1)（单链表需 O(n) 找前驱）；后插四步骤顺序：① $s\text{->next}$ ② $s\text{->prior}$ ③ $p\text{->next\text{->prior}$ ④ $p\text{->next}$。

核心概念 ▾

双链表（Doubly Linked List）在单链表基础上增加了一个前驱指针 prior，使得每个结点可以双向遍历。

特性	单链表	双链表
指针数	1 个（next）	2 个（prior, next）
遍历方向	仅后向	前向 + 后向
删除已知结点	O(n)（需找前驱）	O(1)
空间开销	较小	较大（多一个指针）
插入操作	需要注意顺序	需要注意顺序

typedef struct DNode {
    int data;           // 数据域
    struct DNode *prior; // 前驱指针
    struct DNode *next;  // 后继指针
} DNode, *DLinkList;

NULL ← [A] ⇄ [B] ⇄ [C] ⇄ [D] → NULL
  ↑prior    ↑data  ↑next
  (头结点 prior=NULL，尾结点 next=NULL)

基本操作 ▾

操作	时间复杂度	关键点
按位查找	O(n)	从头遍历
按值查找	O(n)	从头遍历
指定结点后插	O(1)	直接操作
指定结点前插	O(1)	直接操作（vs 单链表 O(n)）
删除指定结点	O(1)	直接操作（vs 单链表 O(n)）

手算示例 ▾

示例 1：后插（在 p 后插入 s）

s->next = p->next;    // ① s 的后继指向 p 的后继
s->prior = p;         // ② s 的前驱指向 p
p->next->prior = s;   // ③ p 的后继的前驱指向 s（需判断 p->next 是否 NULL）
p->next = s;          // ④ p 的后继指向 s

插入前: ... ⇄ [p] ⇄ [q] ⇄ ...
插入后: ... ⇄ [p] ⇄ [s] ⇄ [q] ⇄ ...

注意步骤③④不能交换！若先执行 $p\text{->next} = s$，则 p->next 被覆盖，找不到原后继结点。

示例 2：前插（在 p 前插入 s）

// 方法1：利用 prior 指针
s->prior = p->prior;       // ① s 的前驱指向 p 的前驱
s->next = p;               // ② s 的后继指向 p
p->prior->next = s;        // ③ p 的前驱的后继指向 s
p->prior = s;              // ④ p 的前驱指向 s

// 方法2：转化为后插——在 p->prior 后面插入 s

示例 3：删除结点 p

p->prior->next = p->next;  // ① p 的前驱的后继指向 p 的后继
p->next->prior = p->prior; // ② p 的后继的前驱指向 p 的前驱
free(p);                    // ③ 释放 p

注意若 p 是尾结点，p->next 为 NULL，步骤②需特判。

示例 4：头插法建表（输入 1, 2, 3）

插入1: [HEAD] ⇄ [1] → NULL
插入2: [HEAD] ⇄ [2] ⇄ [1] → NULL
插入3: [HEAD] ⇄ [3] ⇄ [2] ⇄ [1] → NULL
结果: 3 → 2 → 1（逆序）

示例 5：删除所有值为 x 的结点

void DeleteAllX(DLinkList L, int x) {
    DNode *p = L->next;
    while (p != NULL) {
        if (p->data == x) {
            DNode *q = p;
            p->prior->next = p->next;
            if (p->next != NULL)  // 不是尾结点
                p->next->prior = p->prior;
            p = p->next;
            free(q);
        } else {
            p = p->next;
        }
    }
}

常见考法 ▾

操作序列写结果：给定一系列插入删除操作，写出链表最终状态
代码填空：给出插入/删除代码，填写缺失步骤
画图题：画出插入/删除操作后的链表状态
判断代码正确性：指出代码中的错误（如步骤顺序错误）
与单链表对比：双链表删除已知结点为 O(1)，单链表为 O(n)

易错点 ▾

易错清单

后插步骤顺序错误：必须先 $s\text{->next}=p\text{->next}$ 再 $p\text{->next}=s$，否则丢失后继。
忘记判空：操作 p->next->prior 前需判断 p->next 是否为 NULL。
删除时忘记 free：仅改指针不释放内存会导致内存泄漏。
混淆 prior 和 next 方向：prior 指向前驱（左），next 指向后继（右）。
头插法结果逆序。
边界条件：在头结点后或尾结点前操作时的特殊情况。

核心结论 ▾

双链表删除已知结点 O(1)：无需遍历找前驱（单链表需 O(n)）。
双链表已知结点前插 O(1)：利用 prior 直接操作。
后插四步骤顺序关键：① $s\text{->next}$ ② $s\text{->prior}$ ③ $p\text{->next\text{->prior}$ ④ $p\text{->next}$。
删除两步骤：① 前驱的 next 指向后继 ② 后继的 prior 指向前驱。
头插法逆序，尾插法正序（与单链表规律相同）。
空间换时间：多一个指针域，换取操作效率提升。

记忆卡片 ▾

双链表比单链表多什么？优势？

多一个 prior 前驱指针；已知结点的删除和前插都是 O(1)。

后插四步骤？

① $s\text{->next}=p\text{->next}$ ② $s\text{->prior}=p$ ③ $p\text{->next\text{->prior}}=s$ ④ $p\text{->next}=s$。口诀"先链后断，先 s 后 p"。

为何③④不能交换？

先执行 $p\text{->next}=s$ 后，p 的后继变 s，原后继丢失，③的 $p\text{->next\text{->prior}}$ 指向错误。

删除结点 p 的步骤？

① $p\text{->prior\text{->next}}=p\text{->next}$ ② $p\text{->next\text{->prior}}=p\text{->prior}$；尾结点特判。

交互动画 · 后插四步骤与删除 ▾

在 p（A）后插入 s：四步顺序执行

依次点击 ① ② ③ ④ 观察每一步建立的链接

① s 先接后继 B；② s 接前驱 p；③ B 的 prior 指向 s；④ p 的 next 指向 s。步骤③④颠倒会丢失 B。

核心概念 ▾

基本操作 ▾

手算示例 ▾

示例 1：后插（在 p 后插入 s）

示例 2：前插（在 p 前插入 s）

示例 3：删除结点 p

示例 4：头插法建表（输入 1, 2, 3）

示例 5：删除所有值为 x 的结点

常见考法 ▾

易错点 ▾

核心结论 ▾

记忆卡片 ▾

交互动画 · 后插四步骤与删除 ▾

相关知识点