跳转至

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

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

1. 顶层全景

  列表 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) 的指针手术

原书图 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)」的准确含义 (前提是你已经站在要动手术的位置)2。

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

3. 核心原理

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

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

操作 数组版 链表版
Create / Empty? / Size O(1) O(1) / O(1) / O(n)
At(按下标取) O(1) O(n)
Add / Remove(按位置) O(n) O(n)(走到位置)
Find O(n) O(n)

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

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

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

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

队列(queue) = 尾部进(enter/enqueue)、头部出(exit/dequeue)——像排队买票:队尾新来,队首先走。 单链表只给头指针的话,入队要走到尾才能接,退化成 O(n); 解法是把表示升级成 {first, last} 两个指针的对象8: - 入队:空队列两针同指新节点;否则 last.next = 新节点; last = 新节点,O(1); - 出队:first = first.next;特例:出空之后 first 是 null,last 也要归零—— 这是队列代码里最容易漏的一行9。 数组版队列的陷阱(习题 10.9):用 .unshift 在头插入,每次 O(n), n 次入队总 O(n²)——所以真要用数组实现队列得用「环形缓冲」, 这是书外的工程常识(补充,不在书里)。

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

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

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

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

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

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

4. 作者的判断与证据

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

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

5. 边界与局限

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

6. 可带走的

  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. 原文地图

主题 原书章 原文位置
列表 ADT 操作表 Basic Lists text/27-fm-basic-lists.txt:54(搜「Create a new list」)
数组版实现与性能 Basic Lists text/27-fm-basic-lists.txt:252(搜「newList」) · text/27-fm-basic-lists.txt:279(搜「Table 10-3」)
链表版实现 Basic Lists text/27-fm-basic-lists.txt:427(搜「newList = ()」) · text/27-fm-basic-lists.txt:445(搜「const add = (list, position, value)」)
链表版性能与不优结论 Basic Lists text/27-fm-basic-lists.txt:533(搜「Table 10-4」) · text/27-fm-basic-lists.txt:613(搜「best solution」)
栈:操作/实现/应用 Basic Lists text/27-fm-basic-lists.txt:643(搜「Table 10-5」) · text/27-fm-basic-lists.txt:775(搜「newStack」) · text/27-fm-basic-lists.txt:726(搜「interruptions」)
队列:结构/实现/特判 Basic Lists text/27-fm-basic-lists.txt:980(搜「first and last」) · text/27-fm-basic-lists.txt:1021(搜「newQueue」) · text/27-fm-basic-lists.txt:1052(搜「const exit」)
双端队列:双向指针/中间删 Basic Lists text/27-fm-basic-lists.txt:1282(搜「both directions」) · text/27-fm-basic-lists.txt:1323(搜「ptr.prev.next」)
循环列表 Basic Lists text/27-fm-basic-lists.txt:1628(搜「newCircularList」) · text/27-fm-basic-lists.txt:1636(搜「const add = (circ」)
习题与答案 Chapter 10 text/73-ch10-chapter-10.txt:10(搜「const size」) · text/73-ch10-chapter-10.txt:118(搜「hasALoop」) · text/73-ch10-chapter-10.txt:84(搜「[list.next, newList」) · text/73-ch10-chapter-10.txt:203(搜「_radixSort」) · text/73-ch10-chapter-10.txt:238(搜「IN and OUT」)

  1. 出处:「Basic Lists」第 258–270 段(text/27-fm-basic-lists.txt:258,搜「const add = (list, position, value)」)。原文:add 用 list.splice(...)、remove 用 splice(position)、at 用下标、find 用 .includes()。 ↩

  2. 出处:「Basic Lists」第 445–453 段(text/27-fm-basic-lists.txt:449,搜「position - 1」)。原文:递归版 add——position 为 0 或表空时 {value, next: list} 插在最前,否则 list.next = add(list.next, position - 1, value);「增删本身是 O(1) 操作(假设你已知道在哪里改)」见第 416 段。 ↩

  3. 出处:「Basic Lists」第 279–359 段(text/27-fm-basic-lists.txt:279,搜「Table 10-3」)与第 533–613 段(text/27-fm-basic-lists.txt:533,搜「Table 10-4」)。原文:数组版 at O(1)、增删 O(n);链表版 size/at/add/remove/find 全 O(n)。 ↩↩

  4. 出处:「Basic Lists」第 613 段(text/27-fm-basic-lists.txt:613,搜「best solution」)。原文:「这个差别说明,像前面那样单纯用指针实现数组不是最好的方案。不过,有些操作集更贴合特定需求的列表品种能取得更好的性能。」 ↩↩

  5. 出处:「Basic Lists」第 775–794 段(text/27-fm-basic-lists.txt:775,搜「newStack」)。原文:push = (stack, value) => ({value, next: stack});pop = (stack) => (isEmpty(stack) ? stack : stack.next);全 O(1) 见第 810 段表。 ↩

  6. 出处:「Basic Lists」第 723–729 段(text/27-fm-basic-lists.txt:723,搜「reverse Polish」)。原文:HP 计算器 RPN、FORTH/WebAssembly/PostScript、CPU 中断现场、「JavaScript 自身为调用实现了一个栈」。 ↩

  7. 出处:「Basic Lists」第 872 段(text/27-fm-basic-lists.txt:872,搜「moving the array」)。原文:数组版栈「push 可能要搬数组,变成 O(n)」。 ↩

  8. 出处:「Basic Lists」第 980 段(text/27-fm-basic-lists.txt:980,搜「first and last」)。原文:队列用带 first、last 两个指针的对象表示,元素有 next。 ↩

  9. 出处:「Basic Lists」第 1052–1061 段(text/27-fm-basic-lists.txt:1052,搜「const exit」)。原文:出队把 first 指向 next;「若队列被清空,还要修正 last 指针」。 ↩

  10. 出处:「Basic Lists」第 1320–1325 段(text/27-fm-basic-lists.txt:1323,搜「ptr.prev.next」)。原文:中间删除两行指针操作;「即使你从不用双端队列,双向链接和轻松摘除中间元素的概念也是本节要点」。 ↩

  11. 出处:「Basic Lists」第 1628–1674 段(text/27-fm-basic-lists.txt:1628,搜「newCircularList」)。原文:空表为 null;add 时空表新节点自环、否则插在 current 与 current.prev 之间并修四根指针;remove 时两侧互指后 current 后移;advance 即 circ.next。 ↩

  12. 出处:「Chapter 10」第 118–133 段(text/73-ch10-chapter-10.txt:118,搜「hasALoop」)。答案原文:ptr1 一步、ptr2 两步,有环必相遇、无环 ptr2 先到 null;O(1) 额外内存。 ↩

  13. 出处:「Chapter 10」第 81–88 段(text/73-ch10-chapter-10.txt:84,搜「[list.next, newList」)。答案原文:[list.next, newList, list] = [newList, list, list.next] 单步三变量旋转完成原地反转。 ↩

  14. 出处:「Chapter 10」第 238 段(text/73-ch10-chapter-10.txt:238,搜「IN and OUT」)。答案原文:入队 push 到 IN;出队时若 OUT 空先把 IN 全部倒过去;每个元素两次 push 两次 pop,摊还 O(1)。 ↩

  15. 出处:「Chapter 10」第 203–232 段(text/73-ch10-chapter-10.txt:203,搜「_radixSort」)。答案原文:桶改为 {first, last} 队列,入桶用队列进队,回收按桶顺序串回——比第 6 章数组版桶更高效。 ↩