双链表

2026 大纲 二（二）线性表的实现 · 2 链式存储 · 本篇只写相对单链表的增量，共性内容（指针修改范式、带头结点、建表、逆置、复杂度来历）见主篇《单链表》。

加一个指针域，解决一个死角

单链表有个绕不过去的毛病：只能往后走。找后继 $O(1)$，找前驱却要从头遍历，$O(n)$。由此派生出的那两个"常数时间技巧"（前插靠交换数据域、删除自身靠搬后继）都是打补丁，而且各带死角——前者会改变结点的相对地址，后者对尾结点无效。

双链表的做法很直接：给每个结点再加一个 prior 指针域，把前驱也显式存下来。逻辑结构一点没变，仍然是线性表，变的只是存储结构。

⚠️ 双向不等于随机存取。 按位查找仍然是 $O(n)$、平均 ${\displaystyle \frac{n+1}{2}}$ 步，按位序插删也仍是 $O(n)$——定位那一步跑不掉。prior 买到的只是"已经拿到某个结点指针之后"的那些操作。

先看一眼

加载可视化中...

插入时数一数箭头改了几根、删除时又是几根，这个"4 与 2"的差别下面会讲清来历。另外留意首尾两端：非循环双链表里头结点的 prior 和尾结点的 next 都是 NULL，代码里那些判空就是在伺候这两端。

增量一：结点结构与结构恒等式

typedef struct DNode {
    ElemType data;
    struct DNode *prior, *next;   // 相对单链表，只多了 prior 这一个域
} DNode, *DLinklist;

┌───────┬──────┬───────┐
│ prior │ data │ next  │
└───────┴──────┴───────┘

双链表的每一处指针操作，都可以用同一个式子验算：

$$\mathtt{\text{d->next->prior}}=\mathtt{\text{d->prior->next}}=\mathtt{\text{d}}$$

意思是：从 d 往后走一步再往回走一步，必须回到 d；反向同理。"改了 next 却忘了改配套的 prior"是双链表唯一的一类新增错误，而它在这个式子里必然暴露——等号会不成立。写完插删代码代进去验一遍，断链错误跑不掉。

⚠️ 这个恒等式有个前提：d 既有前驱又有后继。非循环双链表的首尾两端代进去会解引用 NULL——代码里每一处判空，补的都是这个前提。

增量二：插入的 4 步指针修改

待修改的指针域	应指向	属于哪个结点
① s->next	p 的原后继	新结点
② p->next->prior	s	p 的原后继
③ s->prior	p	新结点
④ p->next	s	p

为什么是 4 个：s 要嵌进 p 和原后继之间，被打断的连接有两处（每处各一个方向），新结点自己还有两个指针域要填。

// 在 p 结点之后插入结点 s（非循环双链表）
bool InsertNextDNode(DNode *p, DNode *s) {
    if (p == NULL || s == NULL) return false;
    s->next = p->next;          // ① 先让 s 接住 p 的原后继
    if (p->next != NULL)        //    p 是尾结点时没有原后继，跳过 ②
        p->next->prior = s;     // ②
    s->prior = p;               // ③
    p->next = s;                // ④ 最后才覆盖 p->next
    return true;
}

🔴 不是"必须严格按 ①②③④"，硬约束只有一条：读"原后继"的语句必须排在覆盖 p->next 的语句之前。 理由和主篇的通用范式完全一致——p->next 里存着原后继的地址、链上只此一处，④ 会把它覆盖掉；而 ③ 读的是 p 本身、写的是 s 的域，放在哪一步都对。

若把 ④ 提到 ① 之前，p->next 已经变成 s，① 执行后 s->next 拿到的是 s 自己的地址——链表就地成环，后半段永久丢失，遍历会死循环。

这条约束还有个直接推论，正是真题反复设的局：一旦 p->next 已经被改成 s，想再取"原后继"就不能写 p->next了，只能顺着 s->next 回溯。也就是说，同样是补全后两句，p->next->prior = s 在这种情形下是错的（p->next 此刻就是 s 自己），得写成 s->next->prior = s。

增量三：删除的 2 步指针修改

// 删除 p 结点的后继结点（非循环双链表）
bool DeleteNextDNode(DNode *p) {
    if (p == NULL || p->next == NULL) return false;   // p 之后无结点可删
    DNode *q = p->next;         // 先记住被删结点，否则无法 free
    p->next = q->next;          // ① p 越过 q
    if (q->next != NULL)        //    q 是尾结点时没有后继，跳过 ②
        q->next->prior = p;     // ②
    free(q);                    // 最后才释放，此前 q->next 还要被读
    return true;
}

图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图 2.19，p73。书上画的是双向循环链表，"改两个指针"的动作与非循环版完全相同，差别只在非循环版要额外判被删结点是不是尾结点。

删除只要 2 个而不是 4 个，原因不在别处：被删结点自己的 prior 和 next 不必维护——它马上就要被 free 掉，谁也不会再读它。

三处次序不能动：q 必须先取（否则地址丢失、free 不掉），free(q) 必须最后（② 还要读 q->next，先释放就是读已释放内存），而 ② 里的 q->next 在 ① 之后读没有问题——① 改的是 p->next，没动 q->next。

按位序插入的代码与删除的边界自查（题目给的是位序、或想逐格验边界时展开）

带头结点时，在第 $i$ 个结点之前插入可以直接用 p->prior，不需要像单链表那样绕道找前驱。

// 在带头结点的双链表 L 中第 i 个位置之前插入元素 e
bool ListInsert_DuL(DLinklist &L, int i, ElemType e) {
    DNode *p = GetElem_DuL(L, i);    // 定位第 i 个结点，O(n)
    if (p == NULL) return false;     // i 不合法
    DNode *s = (DNode *)malloc(sizeof(DNode));
    if (s == NULL) return false;
    s->data = e;
    s->prior = p->prior;             // ① s 接住 p 的前驱
    p->prior->next = s;              // ② 前驱的后继改指向 s（带头结点时 p->prior 必存在）
    s->next = p;                     // ③
    p->prior = s;                    // ④
    return true;
}

这里 p->prior->next = s 不需要判空，因为带头结点保证了任何数据结点都有前驱——即使 $p$ 是首元结点，它的前驱也是头结点。这是头结点在双链表上的又一处收益。总代价 $O(n)$：定位 $O(n)$ + 4 次指针赋值 $O(1)$；只有题面直接给出结点指针时，插入才是 $O(1)$。

删除的边界自查：

• p 是尾结点 → p->next == NULL，返回 false，正确；
• q 是尾结点 → ① 让 p->next 拿到 NULL，p 成为新的尾结点；② 跳过，正确；
• 表中只有一个数据结点、p 是头结点 → q 即该结点，删除后 L->next == NULL，回到空表，正确。

prior 赚了什么、赔了什么

操作（均设已知结点指针 p）	单链表	双链表	差别的来历
访问 p 的后继	$O(1)$	$O(1)$	都有 next
访问 p 的前驱	$O(n)$	$O(1)$	单链表只能从头遍历找
在 p 之后插入	$O(1)$	$O(1)$	都不需要前驱
在 p 之前插入	$O(1)$，但要交换数据域（结点地址会变）	$O(1)$，不必交换，结点地址不变	双链表直接用 p->prior
删除 p 自身（p 非尾结点）	$O(1)$，但要搬后继数据	$O(1)$，直接摘	同上
删除 p 自身（p 是尾结点）	$O(n)$，无后继可搬，只能找前驱	$O(1)$	这一行是双链表最实的收益
反向遍历整表	做不到（除非先逆置）	$O(n)$	prior 链本身就是一条反向链
按位查找 / 按值查找	$O(n)$	$O(n)$	仍是顺序存取，平均 ${\displaystyle \frac{n+1}{2}}$
按位序插入 / 删除	$O(n)$	$O(n)$	定位那一步跑不掉

赔的一面也很明确：每个结点多一个指针域，设 data 与指针同为 4 字节，结点从 8 字节涨到 12 字节，存储密度从 ${\displaystyle \frac{4}{8}}=0.5$ 降到 ${\displaystyle \frac{4}{12}}\approx 0.33$；插入要维护的指针从 2 个涨到 4 个、删除从 1 个涨到 2 个；再加上"改了一个方向忘改另一个方向"这一整类新错误。

这是一次典型的以空间换时间：多付约 50% 的结点空间和一倍的指针维护量，换前驱访问从 $O(n)$ 到 $O(1)$。值不值取决于应用里"需要前驱"的操作占多大比重——只做单向遍历和尾部追加的场景，双链表纯亏。

考点速记

三条会被反复调用的结论：

1. 双链表买到的不是"能往回走"，而是"任意已知结点都能真 $O(1)$ 地删除和前插，且不改其他结点的地址"。 单链表用交换数据域只能做到近似效果，对尾结点无效且结点地址会变。
2. 插入改 4 个指针、删除改 2 个，差别的来历是：被删结点自身的两个域不必维护，它马上要被释放。
3. 验算工具是结构恒等式 d->next->prior = d->prior->next = d，前提是 d 前后都有结点。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：几乎全是给一段指针操作代码，问哪个写法对。两类局面：

• 补全插入的后半截：题面已经先执行了 s->next = p->next; p->next = s;，问还要再执行什么。关键在于 p->next 此刻已经是 s 了，想拿"原后继"只能顺着 s->next 走，所以正确写法是 s->prev = s->next->prev; s->next->prev = s;。凡是仍然用 p->next->prev 的选项都错——它改的是 s 自己的前驱。
• 判断遍历循环写得对不对：让每个结点的某个指针指向"后继的后继"这类题，命门是最后一个结点的边界：它没有后继，得显式置 NULL，而不是跳过；漏了 else 分支还可能让指针不前进、死循环。看到循环体里有 if，先问"不满足条件时指针有没有前进"。

易错：指针被覆盖之后再去读它。 p->next 一旦改指向 s，p->next->prev 就是 s->prev，不再是原后继的前驱。判断这类选项，把每一句执行完的状态在纸上画一遍最稳。

易错：只改了一个方向。 改了 next 忘了改配套的 prior（或反过来），代入结构恒等式立刻暴露。

易错：非循环双链表的两端没判空。 头结点没有 prior、尾结点没有 next，插入时的 ②、删除时的 ② 都要先确认对象存在。改成循环链表后这些判空可以全部省掉。

教材出处

• 双链表的提出动机（"在单链表中，查找直接后继结点的执行时间为 $O(1)$， 而查找直接前驱的执行时间为 $O(n)$"）、结点结构 DuLNode 的 C 语言定义： 严蔚敏《数据结构（C 语言版）》（第 2 版），p39，2.5.4 节。
• 结构恒等式 d->next->prior = d->prior->next = d，以及 "在插入结点时需要修改四个指针，在删除结点时需要修改两个指针"， 连同带头结点双链表的插入算法 2.13 与删除算法 2.14：同书 p40。 该页同时给出：这两个算法的时间复杂度均为 $O(n)$——因为算法中包含了定位第 $i$ 个结点的一步。

相关知识

单链表（主篇，本篇不重复的内容都在那里）｜循环链表（成环后本篇所有 if (p->next != NULL) 都可省）｜线性表的基本概念｜线索二叉树（复用空指针域存前驱 / 后继，同源思路）｜链表的三种通用解法

相关文章

• 线性表基本概念
• 顺序表（数组）
• 单链表
• 循环链表
• 静态链表
• 链表题的三种通用解法

交互体验

前往完整可视化页面 →

真题练习

相关真题（2题）

2026Q22分2023Q22分