03. 链表

0. 本章先解决什么问题

数组要求连续存储,插入删除中间元素要移动大量数据。链表提供另一种思路:

元素可以分散存放
每个节点保存到下一个节点的指针

本章要解决:

• 链表如何用指针把节点串起来?
• 单链表、双链表、循环链表有什么区别?
• 链表插入删除为什么“改指针”即可,但查找仍然慢?
• 链表为什么 cache 不友好?
• 链表适合什么问题,不适合什么问题?
• 链表常见 bug 如何分析?

链表的核心特征是:

离散节点 + 指针连接 + 顺序访问

这张图怎么读

这张图强调链表最容易出错的地方:插入删除不是“写两行指针”这么简单,而是要按正确顺序维护结构不变量。顺序错了会断链,边界漏了会丢头尾,循环链表还可能遍历不停止。

1. 单链表的结构

单链表节点通常包含:

value
next

示意:

每个节点不要求连续存放。next 保存下一个节点的位置。

遍历链表:

current = head
while current != null:
visit current.value
current = current.next

链表不能像数组一样直接算出第 i 个节点地址。要从头沿着指针走。

2. 链表操作成本

关键句:

链表插入删除 O(1) 的前提是你已经拿到了正确位置或前驱节点。

如果还要先查找位置,整体仍可能 O(n)。

3. 插入节点

在 prev 后插入 x:

prev -> next

变成:

prev -> x -> next

步骤:

x.next = prev.next
prev.next = x

顺序不能反:

如果先写:

prev.next = x

就可能丢掉原来的 prev.next,导致后半段断链。

链表操作很考验指针更新顺序。

4. 删除节点

删除 prev 后面的节点:

prev -> target -> next

变成:

prev -> next

步骤:

target = prev.next
prev.next = target.next

如果需要释放节点或清理引用,还要处理 target 的资源。

删除头节点是特殊情况:

head = head.next

很多链表 bug 都来自头节点、尾节点、空链表、单节点链表这些边界。

5. 哨兵节点

哨兵节点是一个不存真实数据的辅助节点。

dummy -> real1 -> real2 -> null

好处:

• 统一头部插入删除逻辑。
• 减少特殊判断。
• 让代码更稳定。

例如删除真实头节点时,仍然可以看成:

删除 dummy 后面的节点

哨兵不是必须,但它是处理链表边界的常用技巧。

6. 双链表

双链表节点保存两个方向:

prev
value
next

示意:

null <- [A] <-> [B] <-> [C] -> null

优点:

• 已知节点时,可以 O(1) 删除自己。
• 可以向前和向后遍历。

代价:

• 每个节点多一个指针。
• 插入删除要维护更多关系。
• 更容易指针不一致。

删除节点 x:

x.prev.next = x.next
x.next.prev = x.prev

边界节点要小心处理。

7. 循环链表

循环链表的尾节点指向头节点:

[A] -> [B] -> [C]

适合:

• 轮转调度。
• 循环缓冲。
• 需要从任意节点继续一圈的场景。

风险:

遍历时不能只等 null
否则会无限循环

需要明确停止条件,比如回到起点或计数达到节点数。

8. 链表为什么 cache 不友好

链表节点通常分散在内存中。

node1 在地址 A
node2 在地址 K
node3 在地址 Q

遍历时:

读 node1
根据 next 去 node2
读 node2
根据 next 去 node3

每次都依赖前一个节点的 next,CPU 很难提前连续预取。

这会造成:

• cache miss 多。
• 内存等待多。
• 指针追逐成本高。

所以链表理论上插入删除灵活,但实际性能不一定好。

9. 链表常见题型背后的真实能力

链表题不是为了背模板,而是训练:

这些能力也用于树、图、任务链、内存空闲链等结构。

机制深挖:快慢指针本质是维护距离不变量

快慢指针不是“一个走得快,一个走得慢”这么浅。它真正有用,是因为两根指针之间维持了某种距离或速度差不变量。

例 1:找中点。

slow 每次走 1 步
fast 每次走 2 步

当 fast 到达尾部时,slow 走过的距离约为 fast 的一半,所以 slow 在中间附近。

例 2:删除倒数第 k 个节点。

fast 先走 k 步
slow 再和 fast 同速前进

此时始终保持:

fast 和 slow 相差 k 个节点

当 fast 到达尾部,slow 正好在目标节点附近。

例 3:判断环。

slow 每次 1 步
fast 每次 2 步

如果有环,fast 会在环里不断追近 slow,距离差每轮缩小或变化,最终相遇;如果无环,fast 会先遇到 null。

排查快慢指针代码时,不要背模板,写出不变量:

只要不变量被破坏,边界测试一定会出问题:空链表、单节点、双节点、k 等于长度、有环入口在头部等。

10. 常见 bug

排查链表问题时,画图比盯代码有效。

11. 联系实际:什么时候选链表

链表适合:

1. 节点需要频繁从已知位置插入删除。
2. 不要求按下标访问。
3. 元素大小不固定或需要灵活连接。
4. 某些底层系统维护空闲块、任务链、LRU 链。
5. 需要双向移动或快速摘除已知节点。

链表不适合:

1. 大量按下标访问。
2. 大量顺序遍历且追求 cache 性能。
3. 元素很小但指针开销占比大。
4. 需要二分查找。

很多现代场景会用数组、分段数组、环形缓冲、树或哈希表替代纯链表,因为它们更 cache 友好。

排障卡:链表 bug 先画三类指针

排查链表时,不要只盯代码。先画图,标出:

然后检查不变量:

单链表:
每个节点最多一个 next
尾节点 next 为 null
从 head 能走到所有节点

双链表:
x.next.prev == x
x.prev.next == x

循环链表:
遍历必须有停止条件,不能等 null

如果出现遍历死循环、节点丢失、头尾异常,通常就是某一步指针更新破坏了这些不变量。

手推:删除节点时为什么要先保存 next

单链表删除当前节点 cur 时,常见动作是:

prev.next = cur.next

如果你后面还要继续遍历,就必须先保存:

next = cur.next
prev.next = next
cur.next = null
cur = next

否则可能出现两类问题:

链表操作的核心是入口不能丢:

任何还需要访问的子链,都必须至少有一个变量指向它。

这也是为什么画图时要标出 prev、cur、next。它们不是模板变量,而是在保护三段链表:

已处理部分 -> 当前节点 -> 未处理部分

反例:链表插入 O(1) 的前提是已经拿到位置

常见说法:

链表插入 O(1)

这句话有前提:你已经持有插入位置的前驱节点或目标节点。

如果只有下标:

在第 i 个位置插入

单链表必须先从 head 走到第 i-1 个节点:

查找位置 O(i)
改指针 O(1)
总成本 O(i)

所以链表适合的不是“任意位置按编号插入”,而是:

已经有节点引用;
需要频繁摘除/接入;

不需要按下标随机访问。

如果需求是大量按下标访问,链表会被数组打穿;如果需求是维护已知节点的顺序关系,链表才有价值。

12. 学完本章你能解决什么问题

学完这一章,你应该能解决或开始分析这些问题:

1. 链表如何用指针连接离散节点?
2. 为什么链表访问第 i 个元素是 O(n)?
3. 为什么“链表插入 O(1)”有前提?
4. 单链表、双链表、循环链表有什么区别?
5. 哨兵节点为什么能减少边界判断?
6. 链表为什么 cache 不友好?
7. 如何通过画图排查断链、成环、头尾错误?
8. 实际系统中什么时候链表仍然有价值?

链表的核心不是“会写节点类”,而是能稳定维护指针关系和结构不变量。

延伸阅读

• LinkedList
• from - zero · data-structures