第 01 章

数组与链表——一场关于秩序与自由的战争

正在加载交互实验…

第一季 · 人类如何驯服数据

想象一下，现在是1965年。你是一家银行的计算机工程师。银行最近引进了一台大型计算机。它占据整整一个房间，价格贵得惊人，性能却远远比不上今天最普通的手机。你的任务非常简单：管理一万名客户的账户。姓名、账号、余额，都要存进计算机。你想，这有什么难的？可是很快，你发现了一个问题。在现实世界里，工作人员可以随时把一张新客户的卡片插进档案柜。但在计算机里，事情没有那么简单。因为计算机的内存，并不是一个可以随意塞进东西的口袋。而我们的故事，就从这里开始。

第一幕：给一万个人安排座位

你面前有一万名客户。作为工程师，你决定让每个客户坐在一个固定编号的座位上，所有座位紧挨着排列。

银行客户的内存布局（简化示意）

001

002

003

004

005

006

007

008

009

010

011

012

每个客户占据固定大小的记录空间，记录按编号连续排列。

你发现，这种排列方式有一个惊人的好处。假设每条账户记录占用 32 字节，第一条记录的起始地址是 1000。那么：

第 1 条记录：1000
第 2 条记录：1032
第 3 条记录：1064
第 100 条记录：4168

根本不需要从第一条往后寻找。只要使用一个公式：

\text{地址}(i)=\text{起始地址}+i\times\text{记录大小}

这里的

i

从零开始计数。这就是数组最伟大的特征：随机访问（Random Access）。只要知道下标，计算机就能直接算出元素的位置，访问时间复杂度为

O(1)

。而你之前学过的 Python nums[3]，背后就利用了类似的原理。

可是麻烦出现了……

某天，银行经理找到你：“我们需要在第 3 号和第 4 号客户之间，插入一条新记录，并保持原有记录的顺序。”你愣住了。因为座位已经排满了。如果要插入一个新人，后面的客户就得依次向后挪动。

实验一：数组插入插入 X

A

B

C

D

E

F

·

原始数组，末尾留有一个空位。准备在 C 前插入 X。

阶段 1/3

如果数组里有一百万条记录，且在最前面插入一个元素，最坏情况下就需要移动一百万条记录。于是你认识了数组的另一面：

操作	时间复杂度
根据下标读取	$O(1)$
修改指定下标	$O(1)$
查找某个值（无序）	$O(n)$
在开头插入	$O(n)$
在开头删除	$O(n)$

这里讨论的是普通连续数组，且插入、删除后必须保持原有元素顺序。这时，你开始怀疑：如果数据不必连续摆放，会发生什么？

第二幕：一个更疯狂的想法——数据为什么一定要挨在一起？

我们暂时离开银行，来到另一个故事现场。这一次是真实的历史。

1955年：有人想让计算机证明数学定理

20世纪50年代中期，三位研究者开始尝试一件在当时非常大胆的事情：让计算机像数学家一样推理。他们是 Allen Newell、Herbert A. Simon 和 Cliff Shaw。问题是，数学推理并不像银行账户记录那样整齐。一个命题可以引用另一个命题；证明过程中可能突然出现新的推理分支；整个结构会随着计算不断变化。他们需要一种可以在运行时自由增长、自由连接的数据结构。于是，在1955—1956年前后，他们开发了早期链表处理技术和 IPL（Information Processing Language）。链式结构成为早期人工智能程序的重要基础。^{[国家科学院][SOVA, Smithsonian Institution][Hopl]}这也是链表历史上最有趣的一点：它不是单纯为了让插入操作更快，而是为了表示不断变化的复杂符号关系。

假设我们重新设计银行系统

这次，不再要求客户坐在相邻的位置。每位客户拿到一张卡片，卡片上只需要记住两件事：

自己存储的数据。
下一位客户在哪里。

于是，原本连续排列的数据，变成了一条由指针串起来的链。

链表在内存中的布局

查看 SVG 配图原件

01-008.svg · 点击查看大图

地址并不连续，但逻辑顺序仍然是 A → B → C。箭头表示节点保存的下一节点地址。

发现没有？我们把空间上的连续性，换成了逻辑上的连接关系。现在如果要在 A 和 B 中间插入 X：原来：A → B → C插入后：A → X → B → C只需要改变相关的指针，不必整体搬动 B、C 等节点。如果已经知道 A 节点的位置，单链表在 A 后插入 X 可以做到

O(1)

。但链表也失去了一项重要能力。假设经理要求：“马上告诉我第 5000 个客户是谁。”你无法像数组一样直接计算第 5000 个节点的地址，只能沿着 next 从头向后寻找。所以按位置访问的复杂度通常为

O(n)

。

第三幕：没有一种结构能赢得所有战争

数组与链表的能力对决

操作	数组	单链表
根据下标访问	O(1)	O(n)
按值查找	O(n)	O(n)
已定位位置后插入	O(n) 最坏	O(1)
删除头节点	O(n)	O(1)
空间局部性	通常较好	通常较差

假设数组需要维持顺序、单链表已持有指定节点或其前驱。单链表若必须先搜索插入位置，总耗时仍可达 O(n)。

还有一个经常被初学者忽视的事实：在现代计算机上，链表即使操作复杂度看起来更优，也不一定跑得更快。因为 CPU 有缓存。数组的连续内存布局通常更容易受益于缓存和预取；链表的指针跳转则可能增加缓存未命中。这也说明，时间复杂度不是实际运行时间的完整答案。

最后一幕：轮到你当发明者

现在假设你是1960年的工程师。你的程序需要管理一百万条数据。它们有以下特点：

每秒需要随机读取约十万次。
每秒仅有十次插入。
数据很少删除。
机器内存有限。

你会选择数组还是链表？

工程师的抉择

A. 数组：优先保证随机读取效率B. 链表：优先让插入更容易C. 两种结构结合，增加额外索引

本章真正要记住的

数组和链表之争，不是先进与落后的争论。它代表了计算机科学里一条贯穿至今的规律：为了让一种操作变得更快，我们常常必须在其他地方付出代价。数组牺牲部分插入灵活性，换取快速的下标访问。链表牺牲随机访问能力与空间局部性，换取灵活的节点连接。而那些更复杂的数据结构，本质上都是试图重新平衡这些代价。下一章，我们将进入一个非常有意思的故事：《栈与递归：为什么计算机必须记住自己从哪里来？》届时我们会看到，一种简单到只能“后进先出”的结构，为什么能够支撑函数调用、递归、表达式计算，甚至让计算机探索迷宫。