小探险家学算法

Appearance

9. 火车车厢（链表） ​

知识点：链表（linked list）—— 钩子连起来的一列

项目：组装一列玩具火车（插入、拆除、遍历）

故事开场：插一节餐车，为什么要挪动整列火车？ ​

你有一套玩具火车：车头、煤水车、客厢，一节一节钩在一起，开起来"哐当哐当"。

老师突发奇想："往车头后面加一节餐车，好不好？"

用数组来存这列火车的话，是这样的：

ts
let train = ["车头", "煤水车", "客厢"]

在"车头"和"煤水车"中间插入"餐车"……怎么做？

ts
train.splice(1, 0, "餐车")   // 在第 1 个位置插入
console.log(train)
// ["车头", "餐车", "煤水车", "客厢"]

train.splice(1, 0, "餐车") 的意思是：在第 1 号位置插入"餐车"。

可是你盯着数组看，发现了问题——"煤水车"和"客厢"的格子号都变了：

原来：  [车头, 煤水车, 客厢]
           0      1      2
插入后：[车头, 餐车, 煤水车, 客厢]
           0      1      2      3

"煤水车"从 1 号格挪到了 2 号格，"客厢"从 2 号格挪到了 3 号格。 插入一个，后面全挪位！

老师在旁边问了一句："如果这是一列 100 节的火车，往最前面插一节车厢， 要挪多少次？"

你答："99 次……"（插入在最前面，后面 99 节全要挪，O(n)！）

"那要拆掉中间的一节呢？"老师又问。

"也是几十次……"你嘟囔着，"怎么又是 O(n)，跟 shift 一个毛病。"

笨办法先行：数组的"挪位"从哪来？ ​

为什么数组插队要挪位？因为数组在内存里是一排紧挨着的格子， 第 0 格、第 1 格、第 2 格……必须连续。中间插一个， 后面的格子不往前补，就断了。

这是数组的规矩：下标 = 位置。位置一变，所有的下标全变。

可玩具火车根本不是这样的！火车的车厢不在"格子"里——每节车厢 只有一个钩子，钩住后面那一节。想插一节餐车？只要解开两个钩子、 重新钩上就行：

车头 ──钩──▶ 煤水车 ──钩──▶ 客厢

在中间插入餐车：
车头 ──钩──▶ 餐车 ──钩──▶ 煤水车 ──钩──▶ 客厢
      ▲改一个钩子▲     ▲再改一个钩子▲

改两个钩子，跟火车有多长完全无关——100 节还是 10000 节，都是改两个钩子！ 这就是 O(1)！

引出知识点：链表——"值 + 钩子"的节点串 ​

计算机里，这种"一节钩一节"的结构叫链表（linked list）。

每一节车厢是一个节点（node），节点只有两样东西：

车厢名字（值）钩子（next）
车头"车头"指向煤水车
煤水车"煤水车"指向客厢
客厢"客厢"指向空（null）

最后那节车厢的钩子钩着空气（null），表示"火车到头了"。 第一节车厢叫头节点（head）——想逛整列火车，必须从头开始， 跟着钩子一节一节走。

在 TypeScript 里，一个节点就是一个"有名字、有钩子"的对象：

ts
type Car = { name: string, next: Car | null }

function makeCar(name: string): Car {
  return { name: name, next: null }   // 新车厢的钩子先空着
}

（type 是"画一张图纸"：说明一辆 Car 有 name 和 next 两个东西。 next: Car | null 表示"钩子要么指向另一节 Car，要么空着"。）

你可能会问：那怎么"逛"整列火车？很简单——从车头开始， 跟着钩子一直走，走到钩子空了为止：

ts
function showTrain(head: Car): void {
  let current: Car | null = head   // 从车头出发
  let line = ""
  while (current !== null) {       // 钩子没空，就还有下一节
    line = line + current.name + " → "
    current = current.next        // 顺着钩子走到下一节
  }
  console.log(line + "终点")
}

动手实现：组装火车 ​

先把三节车厢钩起来：

ts
const car1 = makeCar("车头")
const car2 = makeCar("煤水车")
const car3 = makeCar("客厢")

car1.next = car2    // 车头钩住煤水车
car2.next = car3    // 煤水车钩住客厢

showTrain(car1)

输出：

车头 → 煤水车 → 客厢 → 终点

现在，插入一节餐车（改两个钩子）：

ts
const car4 = makeCar("餐车")

car4.next = car3    // 第一步：餐车的钩子，钩住客厢
car2.next = car4    // 第二步：煤水车的钩子，改钩住餐车

showTrain(car1)

输出：

车头 → 煤水车 → 餐车 → 客厢 → 终点

注意这两个步骤的顺序：先把餐车的钩子挂到客厢上（不然客厢就"掉"了）， 再把煤水车的钩子改挂到餐车上。两步，和火车多长没关系！

跑起来：拆车厢 + 数车厢 ​

拆掉餐车，也是改两个钩子——不，这次只改一个钩子就够了：

ts
car2.next = car3    // 煤水车的钩子，直接钩回客厢

showTrain(car1)

输出：

车头 → 煤水车 → 客厢 → 终点

餐车呢？它孤零零地钩着客厢，但没人钩着它——它不在火车上了。 （程序里没人引用它，以后会被"垃圾回收"悄悄收走。）

再来个有用的功能：数一数有几节车厢。链表没有"长度"属性， 只能从头走到尾数一遍（O(n)）：

ts
function countCars(head: Car): number {
  let count = 0
  let current: Car | null = head
  while (current !== null) {
    count++
    current = current.next
  }
  return count
}

console.log("一共有 " + countCars(car1) + " 节车厢")

输出：

一共有 3 节车厢

链表 vs 数组：各有所长 ​

事情数组链表
按下标找第 k 个O(1)，一步！O(n)，要一节节数过去
在中间插入/删除O(n)，后面全挪位O(1)，改两个钩子
内存一排紧挨着，必须连续散落各处，钩子连起来

看出来了吗？数组擅长"找"，链表擅长"改"。一个按下标直取， 一个插拔自如。哪个更好？看你要干什么——点名用数组， 频繁插队拆队用链表。

生活中也有"链表"：贪吃蛇的身体（每节记住下一节在哪）、 火车本身、游乐园的过山车、一个人的朋友圈（好友的好友……）。

小挑战 ​

  1. 加长火车：自己再加两节车厢（"行李车"、"卧铺车"）， 加在车尾，打印整列火车。
  2. 反转火车：让车头变车尾、车尾变车头——整个火车掉头！ （提示：从车头开始走，每到一个节点，把它的钩子掉个头 指向前一节；需要用一个变量记住"我刚刚路过谁"。）
  3. 数一数：写一个 findCar(head, name) 函数，报一个车厢名， 返回它是第几节（从 1 开始数）；找不到返回 -1。 （提示：遍历时用一个计数器，找到了就返回。）

课后练习 ​

第 1 题（动手题）：我的五节火车 ​

用 makeCar 造一辆 5 节 的火车（随便什么名字）， 打印它，然后数一数有几节。再拆掉最中间那一节，重新打印。 （提示：中间那节的前一节，钩子改挂到中间那节的后一节。）

参考答案（点开查看）
ts
const a1 = makeCar("车厢1")
const a2 = makeCar("车厢2")
const a3 = makeCar("车厢3")
const a4 = makeCar("车厢4")
const a5 = makeCar("车厢5")
a1.next = a2
a2.next = a3
a3.next = a4
a4.next = a5

showTrain(a1)          // 车厢1 → 车厢2 → 车厢3 → 车厢4 → 车厢5 → 终点
console.log(countCars(a1))   // 5

// 拆掉中间的车厢3：让车厢2 直接钩住车厢4
a2.next = a4
showTrain(a1)          // 车厢1 → 车厢2 → 车厢4 → 车厢5 → 终点

注意顺序：先要找到"车厢3 的前一节（车厢2）"和"后一节（车厢4）"， 再把前面的钩子改挂到后面。拆最中间，就是改它前面那一节的钩子。

第 2 题（思考题）：为什么链表找不到"第 k 节"？ ​

数组 arr[5] 一步就能拿到第 5 个元素；链表想拿第 5 节车厢， 为什么必须从头一节一节数？画一画你就懂了。

参考答案（点开查看）

因为链表没有"编号"：数组的格子是按顺序挨在一起的， 知道第 0 格在哪，往前走 5 格就是第 5 格（内存地址 + 5，一步算出）。

链表的车厢散落在内存各处，每节只知道自己后面的那节。 想知道第 5 节是谁，只能从车头开始：车头 → 车厢2 → 车厢3 → 车厢4 → 车厢5，一步步跟着钩子走，走 5 次才知道，所以是 O(n)。

"按下标找"是数组的绝招，也是链表的短板——各有所长嘛！

第 3 题（思考题）：数据结构的"规矩" ​

栈的规矩是"后进先出"，队列是"先进先出"，数组是"按下标连续排列"， 链表是"钩子一个连一个"。每种结构的规矩，都决定了它擅长什么。 那请你判断：下面这些场景，用数组、栈、队列、链表里的哪一个最合适？

① 浏览器的后退按钮 ② 打印店叫号 ③ 贪吃蛇的尾巴（蛇每次移动，头前进一步，尾缩回去一格） ④ 按学号（1~50）存全班成绩

参考答案（点开查看）

① 栈：后进的网页先退（后进先出）。 ② 队列：先来的先打（先进先出）。 ③ 链表：蛇身每一节记住"我后面是谁"，头动一下、尾动一下， 中间一节节跟着走——也可以说是"移动的链表"。贪吃蛇是最经典的 链表比喻！（用数组也能做，但每节都要挪，麻烦。） ④ 数组：学号连续，直接用下标存/取，O(1)。

判断口诀：看它最常做的事是什么——退回去用栈，排队用队列， 频繁插删用链表，按下标存取用数组。

预告：数据结构篇结束了！你已经认识了栈、队列、哈希表、链表—— 四大"数据结构的法宝"。下一卷《查找与排序篇》我们要用它们去 解决真问题：在一万个数里找一个数，在乱糟糟的成绩单里排好队。 还记得第 1 章的 O(1)、O(n)、O(log n) 吗？它们要正式登场了！