第 10 章 列表 — 指针穿针引线的基本功Copy Anchor Link

这一章讲什么: 用「对象里存一个指向下一个对象的引用」这种最朴素的 动态内存,把列表 ADT 做一遍,再收束成栈、队列、双端队列、循环列表四个特化。 它在全书链条里的位置: Part III 地基。后面所有复杂的结构(树、堆、图) 都是节点 + 指针的变体;本章的指针操作(remove 中间节点那两行 ptr.prev.next = ptr.next)会在每一章重现。

1. 顶层全景Copy Anchor Link

  列表 ADT:create / isEmpty / size / add(位置) / remove(位置) / at / find
      │
      ├─ 数组版:splice 解决一切
      │    at O(1);增删 O(n)(中段插入要搬后半截)
      │
      ├─ 链表版:节点 {value, next},空表 = null
      │    增删本身是 O(1),但要先走到位置 → 也是 O(n)
      │    at O(n);size 递归数一遍 O(n)
      │
      └─ 收束操作集 → 四个全 O(1) 的特化:
           栈      只动顶:push/pop/top
           队列    头出尾进:first+last 双指针
           双端队列 双向指针 prev+next,两端进出一律 O(1),中间删也是
           循环列表 无头无尾,current 指针,add 插在 current 前、remove 删 current

  图说:操作集越收越窄,性能越来越好——数据结构设计的常规范式。

2. 主线例子:链表 add(1, 80) 的指针手术Copy Anchor Link

原书图 10-2 的场景:链表 [22, 9, 60, 12](每个节点是 {value, next}), 要在位置 1(即 9 之前)插入 80。

递归代码只有四行:

const add = (list, position, value) => {
  if (isEmpty(list) || position === 0) {
    list = {value, next: list};        // 造新节点,指向原来的头
  } else {
    list.next = add(list.next, position - 1, value);  // 去下一站
  }
  return list;
};

走一遍:add(head, 1, 80):position 不是 0,递归 add(9节点, 0, 80): 位置到了——造 {80, next: 9节点},返回;上一层的赋值 22节点.next = {80…} 把 22 的指向改掉。全过程中只有新节点和 22 节点的指针被动过, 9、60、12 三个节点纹丝未动——这就是「增删 O(1)」的准确含义 (前提是你已经站在要动手术的位置)¹。

对比数组版:add(list, position, value) 一行 splice(position, 0, value), 语义相同,但中段插入要挪动后面所有元素,所以是 O(n)²。

3. 核心原理Copy Anchor Link

3.1 数组版与链表版的性能对账Copy Anchor Link

同一 ADT 两张性能表,值得并排看(书中 Table 10-3 与 10-4)³:

两个教训。第一,「链表增删 O(1)」有前提——你已经握着那个位置的指针; 从头走过去的账不能不算。第二,纯列表场景链表版全面不优,书里的结论很直白: 「用指针模拟数组不是好方案」;链表的价值在于收束操作集之后的特化结构⁴。 数组版还有一个隐形代价:扩容时整体搬迁(第 4 章摊还分析的那个翻倍策略)。

3.2 栈:LIFO,四个操作全 O(1)Copy Anchor Link

栈(stack)= 只能从顶进出的列表,像一摞盘子:push(放顶)、pop(拿顶)、 top(看顶)、isEmpty。链表实现漂亮到全是单行:push = (s, v) => ({value: v, next: s})—— 新节点的 next 指向旧栈顶,新栈顶就是新节点本身;pop 返回 stack.next⁵。 应用场景书里列了一串:HP 计算器的逆波兰(RPN)、FORTH/WebAssembly/PostScript 的 操作数栈、CPU 中断保存现场、以及 JS 自己的函数调用栈——「递归时当前状态 被 push,返回时 pop」,第 5 章的递归在这里有了物理图像⁶。 数组版栈(习题 10.5)用 .push/.pop 即可,但 push 可能触发扩容搬迁, 摊还 O(1) 而非保证 O(1)⁷。

3.3 队列:FIFO,靠 first + last 双指针Copy Anchor Link

队列(queue) = 尾部进(enter/enqueue)、头部出(exit/dequeue)——像排队买票:队尾新来,队首先走。 单链表只给头指针的话,入队要走到尾才能接,退化成 O(n); 解法是把表示升级成 {first, last} 两个指针的对象⁸:

• 入队:空队列两针同指新节点;否则 last.next = 新节点; last = 新节点,O(1);
• 出队:first = first.next;特例:出空之后 first 是 null,last 也要归零—— 这是队列代码里最容易漏的一行⁹。 数组版队列的陷阱(习题 10.9):用 .unshift 在头插入,每次 O(n), n 次入队总 O(n²)——所以真要用数组实现队列得用「环形缓冲」, 这是书外的工程常识(补充,不在书里)。

3.4 双端队列:双向指针,中间删除也 O(1)Copy Anchor Link

双端队列(deque,读作 deck) = 两端都能进出。每个节点加一根 prev 指针 指向前驱,操作对两端完全对称。最重要的两行是「从中间删任意节点」:

ptr.prev.next = ptr.next;
ptr.next.prev = ptr.prev;

前提是你手里有指向该节点的指针——双向链表让「摘除已知节点」成为 O(1), 这是它在调度器、工作队列里的核心价值¹⁰。 两端操作依然是边界特判(空队列、删到空),逻辑与队列同构。

3.5 循环列表:没有头尾,current 转圈Copy Anchor Link

循环列表(circular list):最后一个节点的 next 指回第一个, 没有 first/last,只维护一个 current 指针。add 把新节点塞到 current 之前 并让它成为新 current(空表时新节点自环:next = prev = 自己); remove 摘 current、current 前移一格;advance 就是 current = current.next¹¹。 应用:轮转调度(操作系统进程轮询)、第 15 章斐波那契堆的兄弟链表。 四个操作全 O(1),是本章第五个全常数结构。

4. 作者的判断与证据Copy Anchor Link

• 「指针模拟数组不是好方案」是明确的反面结论——两版性能表对账后得出, 链表的正当性来自操作集收束(栈/队列/双端队列/循环列表),不是通用列表⁴。
• 操作集收束是本章真正的设计方法论:ADT 的粒度决定性能上限; 你越知道「用这个结构要干什么」,就越能为它定制出全 O(1) 的实现。
• 习题答案即面试题库:判环用快慢指针(快指针每次两步,有环必相遇)¹²; 链表原地反转用三变量一次解构交换¹³;双栈模拟队列摊还 O(1), 第 18 章还会回来¹⁴;队列版基数排序兑现第 6 章「桶用列表模拟」的预告¹⁵。
• 所有性能结论都给了表,且说明数组版的例外(push 搬迁、unshift O(n)), 没有无条件宣称³。

判断(我们的,不是书里的): 本章的隐藏主线是「表示的升级」: 栈把表示压成一个头指针就够;队列发现一根不够,升级到 {first, last}; 双端队列再升级到双向;循环列表干脆取消头尾概念。 每一步升级都对应一类新操作,O(1) 从来不是免费的,是表示买的。 这个「表示先行」的思维方式,比任何一段指针代码都值得带走。 如果错,会错在: 「表示升级」的叙述是我们从四节结构里读出的, 书里按 ADT 逐个讲、没有把这层抽象说破;且 JS 的对象引用 让「指针」与「引用」混为一谈,C/Rust 背景读者需要自行翻译。

5. 边界与局限Copy Anchor Link

• 没有给迭代器/遍历协议:链表遍历全靠手写 for 循环或递归; JS 的 for...of/生成器如何适配这些自定义结构没讲(补充,不在书里)。
• 持久化未提:这些结构全是可变的;不可变链表(第 18 章)要等到全书末。
• 队列的数组环形缓冲方案缺席(习题 10.9 只给了慢的 unshift 版), 工程读者需另行补课。
• 并发安全没有:多协程共享一个栈/队列会发生什么,本书范围之外。
• 栈的「最大栈」(习题 10.8,每个节点顺手记当前最大值)这类增强只给思路不给完整代码。

6. 可带走的Copy Anchor Link

1. 数组版列表:splice 定乾坤,at O(1)、增删 O(n);扩容搬迁是隐形税。
2. 链表版:节点 {value, next}、空表 null;增删本身 O(1) 但「走到位置」另算。
3. 纯列表场景链表不优;链表的价值在收束操作集后的特化结构。
4. 栈:push/pop/top 全 O(1);递归 = JS 调用栈的 push/pop。
5. 队列:必须维护 first+last 双指针;出空时 last 要归零。
6. 双端队列:ptr.prev.next = ptr.next; ptr.next.prev = ptr.prev 摘除任意节点 O(1)。
7. 循环列表:current 指针 + 自环节点;add 插在 current 前,remove 删 current。
8. 标准面试三件套:快慢指针判环、三变量解构反转链表、双栈模拟队列(摊还 O(1))。
9. 队列版基数排序:桶 = 队列,按位分桶再串回,兑现第 6 章的预告。

7. 原文地图Copy Anchor Link