03 - 数组 vs 链表

数组和链表是最基础的两种「线性结构」（数据排成一条线）。它们俩是一对经典的「对头」——一个的优点正好是另一个的缺点。把这一对讲透，你就理解了数据结构世界里最核心的取舍。

数组：一整排连续的座位

数组把数据存在内存里一块连续的空间中，像电影院里连号的一排座位：

下标:   0     1     2     3     4
      ┌────┬────┬────┬────┬────┐
      │ 10 │ 20 │ 30 │ 40 │ 50 │
      └────┴────┴────┴────┴────┘

因为是连续排列、每个元素大小一样，所以只要知道「第几个」（下标），就能直接算出它在内存的位置，一步取到。

• 按下标读取/修改：O(1) —— 想要第 3 个？直接跳过去拿，超快。这是数组最大的优点。（还记得组成原理篇「内存是按地址访问的一排格子」吗？数组正是直接利用了这一点。）

但连续排列也带来大麻烦——中间插入/删除很费劲：

• 想在第 1 位后面插一个新数？后面的 20、30、40、50 全都得往后挪一格给它腾地方。
• 删掉中间一个？后面的又都得往前补位。
• 中间插入/删除：O(n) —— 平均要挪动一半的元素。

数组像电影院固定连号的座位：找第几排第几座（读取）一步到位；但想在中间硬插一个人，后面整排都得起身挪位子。

链表：一串用绳子系起来的珠子

链表不要求连续。每个数据单独存放（叫一个节点），节点里除了存数据，还存一个「指向下一个节点在哪」的指针，像一串用绳子串起来的珠子：

┌────┬──┐   ┌────┬──┐   ┌────┬──┐   ┌────┬────┐
│ 10 │ ●┼──▶│ 20 │ ●┼──▶│ 30 │ ●┼──▶│ 40 │ 空 │
└────┴──┘   └────┴──┘   └────┴──┘   └────┴────┘
 头节点                                  尾节点

节点们在内存里可以七零八落，全靠指针「牵手」连成一条链。

• 插入/删除快：想在 10 和 20 之间插一个数？只要改几根「指针」——让 10 指向新节点、新节点指向 20 就行，其他节点原地不动。删除同理。
• 中间插入/删除（已知位置时）：O(1) —— 这是链表最大的优点。

但「靠指针牵手」也带来大麻烦——没法直接跳到第几个：

• 想要第 3 个节点？没有连续地址可算，只能从头节点出发，顺着指针一个个数过去。
• 按位置查找：O(n)。

链表像一列手拉手的人：想在中间加个人，让两边松手拉住新人就行（插入快）；但想找「第 5 个人」，只能从排头开始一个个数（查找慢）。

正面对比

一句话记忆：

数组「读得快、改得慢」；链表「改得快、读得慢」。 一个的软肋正好是另一个的强项。

到底该用哪个？

看你的操作以谁为主：

• 频繁按位置读取、数据量稳定 → 用数组。（比如存一批固定的配置、要频繁随机访问的表。）
• 频繁在中间增删、大小变化大 → 用链表。（比如实现一个需要频繁增删节点的队列。）

补充：实际编程里你用的 Python list、Java ArrayList 大多是「动态数组」（数组的升级版，能自动扩容）；而很多语言的「链表」用得反而少——因为现代 CPU 的缓存（组成原理篇第 06 章）特别偏爱数组那种连续内存，链表分散的内存对缓存不友好。这也是「理论最优」和「实际好用」有时不一致的一个好例子。

小结

• 数组：连续存放，靠下标一步取到（读取 O(1)），但中间插入/删除要挪动大量元素（O(n)）。
• 链表：节点分散、靠指针牵手，中间增删只改指针（O(1)），但查找要从头数（O(n)）。
• 一句话：数组读快改慢，链表改快读慢，互为对头。
• 选型看主要操作：多读取用数组，多中间增删用链表。
• 实践中数组（动态数组）更常用，因为它对 CPU 缓存友好。

下一章 → 04 - 栈：只能从一头进出 ｜ 回到 README 目录