先看一个很常见的导入逻辑。后台要从 Excel 里读五万行订单,逐行塞进一个链表,读完再统一处理。写的时候觉得链表「插入方便」,于是每读一行就创建一个节点,从头开始找尾节点,再把新节点接上去。数据量一万的时候感觉不到,到了五万,导入卡了将近两秒;再翻一倍,时间不是翻一倍,而是翻了四倍。
问题不在链表本身,而在「每次追加都要从头找尾」。链表确实能在常数时间内把新节点接在某个已知节点后面,但「找到尾节点」这件事本身要遍历整条链。每一行都找一次,总成本就是 1 加 2 加 3 一直加到 n,约等于 n 的平方除以二。数组的追加则是在末尾写一个元素,绝大多数时候是一次赋值,偶尔遇到容量不够才整体搬一次。
这篇要把两边每一种操作的完整成本摊开,而不是只记「数组查得快、链表插得快」。这两句话都有前提:数组在尾部追加便宜,在中间插入要搬移;链表在已知位置插入便宜,但找到那个位置通常要线性时间。搞不清前提,就会写出「用链表做导入反而更慢」的代码。
现场:每次追加都从头找尾
错误版本的结构很直白。节点只有值和后继,链表只有 head,没有 tail。每来一行数据,先创建一个节点,然后从 head 一路走到最后一个节点,把它的 next 接上新节点。
function appendSlow(head, value) {
const node = { v: value, next: null };
if (!head) return node;
let p = head;
while (p.next) p = p.next; // 每次都要走完整条链
p.next = node;
return head;
}
本机用 Node.js 24 跑了五万次追加。数组 push 耗时约 0.78 毫秒;链表每次从头找尾耗时约 1781 毫秒,两者差了三个数量级。改成维护 tail 指针之后,同样的五万次追加降到约 3.5 毫秒。差别不在节点创建,而在那 12.5 亿次多余的指针跳转。这是一次「看起来是 O(1)、实际是 O(n)」的典型翻车。
正确版本只要多存一个尾部引用:
function appendFast(state, value) {
const node = { v: value, next: null };
if (!state.head) { state.head = state.tail = node; }
else { state.tail.next = node; state.tail = node; }
}
所以第一个结论要说得准确:链表不是「追加快」,而是「在已知尾节点后面追加快」。没有尾指针,追加就是 O(n);有了尾指针,追加才是 O(1)。很多性能问题不是数据结构选错,而是选了之后少维护一个指针。
数组:连续内存与容量
数组(array)是一块连续的内存,元素按顺序挨着放。知道起始地址和每个元素的大小,就能用「起始地址加下标乘元素大小」直接算出第几个元素在哪。这个计算是常数时间,不需要从头走,所以数组的随机访问是 O(1)。这也是数组最核心的优势,其他所有差异都从这里派生。
数组通常有两个数字:长度(现在存了几个元素)和容量(这块内存最多能放几个)。长度是业务概念,容量是实现概念。追加元素时,如果长度还没到容量,直接在末尾写;如果已经满了,就要申请一块更大的内存,把旧元素全部复制过去,再释放旧内存。这个过程叫扩容。
扩容本身是 O(n),但它不是每次都发生。容量通常按倍数增长,比如 1.5 倍或 2 倍,扩容一次之后能撑很多次追加。把扩容成本摊到每一次追加上,平均仍然是常数,这就是均摊分析要讲的事。这里先记住结论:数组追加的「最坏一次」很贵,「平均每次」很便宜。
数组在中间插入或删除则不一样。下标 5 空出来一个位置,后面所有元素都要整体后移一格;删除时则要整体前移。这个搬移是按元素个数算的,平均要动一半的元素,所以是 O(n)。这一点和链表正好相反:数组在中间插入贵,链表在已知位置插入便宜。但链表要先找到那个位置,这一段往往被忽略。
链表:分散的节点与稳定的引用
链表(linked list)的节点单独分配,地址不连续,每个节点自己记住下一个节点在哪。它没有「容量」概念,来一个节点就申请一个节点,理论上可以一直加下去,不需要整体搬移。代价是失去按下标直接定位的能力:第 k 个节点在哪,只能从头数。
链表真正的优势有两个。第一个是「已知位置」的插入和删除是常数时间,不需要搬移其他元素。第二个是「引用稳定」:往数组中间插入一个元素,后面所有元素的地址都可能变;链表的节点一旦创建,地址就不变,其他结构可以放心地长期持有指向它的引用。这两点在 LRU 缓存、事件监听器列表、图邻接表里非常有用。
但这两个优势都有使用条件。插入删除必须已经拿到节点或其前驱,否则查找成本要算进去;引用稳定只在节点不被删除时成立,删掉之后旧引用就是悬挂指针。很多「链表比数组快」的结论,都是在已经持有节点引用的理想条件下测出来的,真实业务里往往还要先查一遍。
数组的强项
按下标随机访问、尾部追加、批量顺序遍历、二分查找、内存连续带来的缓存友好。适合读多写少、数据量可预估、需要频繁定位的场景。
链表的强项
已持有节点的插入删除、元素数量增长不可预测、节点引用需要长期稳定、大量小对象不适合整体搬移的场景。适合写多、位置已知、结构会频繁变动的场景。
把每种操作的成本摆在一起
笼统说「谁快」没有意义,要按操作逐个看。下面这张表假设数组是动态数组(长度和容量分开),链表是带 head 的单链表;「已知位置」指已经持有节点引用或下标。
| 操作 | 动态数组 | 单链表 | 说明 |
|---|---|---|---|
| 按下标读取 | O(1) | O(n) | 数组是地址计算,链表要逐节点走 |
| 尾部追加 | 均摊 O(1) | 有 tail 时 O(1),无 tail 时 O(n) | 数组偶尔扩容搬移,链表要找尾 |
| 头部插入 | O(n) | O(1) | 数组要把所有元素后移,链表改 head |
| 中间插入(已知位置) | O(n) | O(1) | 数组搬移后半段,链表改两个指针 |
| 中间插入(按值查找) | O(n) | O(n) | 两边都要先找位置,链表不占便宜 |
| 删除(已知前驱) | O(n) | O(1) | 数组前移,链表跨过节点 |
| 顺序遍历 | O(n),缓存友好 | O(n),指针跳转 | 大 n 时数组通常更快 |
| 内存占用 | 元素本身加少量冗余 | 每个节点多一个指针和分配开销 | 链表通常更占内存 |
表里最值得盯的是第三行和第五行。很多人只记住「链表插入 O(1)」,却忘了按值查找也是 O(n),于是总成本并没有比数组好。只有当插入位置已经拿在手里,比如遍历过程中顺手记下了节点、或者哈希表已经定位到节点,链表的 O(1) 才真正兑现。
局部性:为什么顺序访问差这么多
理论上数组和链表的顺序遍历都是 O(n),但实际耗时可以差好几倍。原因是 CPU 读内存不是一次读一个字节,而是一次读一整条缓存行(常见是 64 字节)。数组的元素挨在一起,读第一个元素时,后面十几个元素已经被带进缓存,下一次访问大概率直接命中;链表的节点散落在堆上,每读一个节点都可能是一次新的缓存未命中。
本机用 Node.js 24 做了带预热的对照:20 万个整数顺序求和,数组约 0.128 毫秒,链表约 0.573 毫秒;随机访问第 15 万个元素 100 次,数组约 0.0059 毫秒,链表约 28.9 毫秒。顺序遍历差四倍多,随机访问差几千倍。这些数字会随语言、JIT、对象布局变化,不能直接搬到 Java 或 C 上,但「数组在顺序和随机访问上占优」这个方向是稳定的。
局部性还解释了一个反直觉现象:同样是 O(n),数组遍历往往比链表快,哪怕链表每个节点只多存一个指针。因为瓶颈不在指令数量,而在等内存。数据量小的时候两者都在缓存里,差距看不出来;数据量大到超过缓存,差距才会显现。这也是为什么「小数据量下链表够用」这句话经常成立,但它不能推广到大数据量。
链表真正划算的几个场景
第一个场景是 LRU 缓存。哈希表负责 O(1) 定位节点,双链表负责 O(1) 把节点挪到头部、O(1) 摘除尾部。这里链表的价值不在「插入快」,而在「已经拿到节点后能常数时间改结构」,数组做不到,因为挪动一个元素要搬移其他元素。
第二个场景是事件监听器或任务队列。监听器注册后地址稳定,删除时只需要改前后指针,不需要把整个数组重新排列。如果监听器数量很大、增删频繁,链表的优势会体现出来;但如果只是遍历触发,数组反而更简单、更快。
第三个场景是稀疏图的邻接表。每个顶点挂一条链表,只存真实存在的边,空间和边数成正比。换成邻接矩阵,空间是顶点数的平方,稀疏图上绝大部分是零。这里选链表不是为了插入快,而是为了不浪费空间。
第四个场景是元素本身很大、搬移成本高。数组在中间插入要复制整个元素,如果每个元素是几百字节的结构体,搬移会非常贵;链表只改指针。但现代语言里数组通常存引用而不是元素本身,这个优势会被削弱,要看具体实现。
反过来说,下面这些场景优先用数组:需要排序或二分、需要按下标分页、需要批量遍历、数据量可以预估、读远多于写。绝大多数业务列表都属于这一类。不要因为「链表听起来更算法」就选它,数组在真实项目里赢得更多。
现象、原因与第一步排查
下面这些症状经常被误判成「数据丢了」或「内存不够」,实际上都和数组、链表的成本模型有关。
| 现象 | 真实原因 | 第一步查什么 |
|---|---|---|
| 导入数据越往后越慢 | 每次追加都从头找尾,总成本变成平方级 | 链表是否维护了 tail 指针 |
| 数组中间插入后其他引用失效 | 扩容或搬移让元素地址改变,旧引用指向旧位置 | 是否在插入前缓存了元素引用 |
| 数组追加偶发卡顿 | 容量刚好用满,触发一次整体复制 | 是否能在导入前预设容量 |
| 链表遍历比数组慢好几倍 | 节点分散,缓存未命中,指针跳转成本高 | 是否真的需要链表,能否换成数组 |
| 按值删除链表元素很慢 | 找前驱本身是 O(n),删除的 O(1) 没兑现 | 是否已经持有节点或前驱引用 |
| 数组头部插入很慢 | 每次插入都要把全部元素后移 | 是否可以用双端队列或反向存储 |
| 链表内存占用远超预期 | 每个节点都有对象头和指针开销,分配器还有碎片 | 节点数量与单节点实际字节数 |
| 分页接口越翻越慢 | 按下标取第 k 个,链表要线性走,数组是常数 | 分页是否依赖随机访问 |
第一行和第五行是链表最常见的两个坑:一个是「以为追加是常数,其实每次都在找尾」,另一个是「以为删除是常数,其实每次都在找前驱」。判断方法很朴素:把「查找位置」和「改指针」两段成本分开算,不要只算后半段。凡是需要先遍历的,总成本就不会是常数。
边界与代价
数组的边界主要来自容量和搬移。扩容会短暂占用双倍内存,数据量大时可能触发内存峰值;搬移期间如果别的代码持有元素地址,旧地址会失效。预设容量能避免反复扩容,但预设过大又浪费内存。中间插入删除的搬移成本无法消除,只能通过选择别的结构绕开。
链表的边界主要来自分配和局部性。每个节点单独分配,分配器要记录空闲块,节点之间可能有碎片;节点越多,垃圾回收或引用计数的压力越大。指针跳转让缓存命中率下降,遍历时 CPU 经常在等内存。除此之外,链表没有下标,不能二分,不能高效分页,这些都是结构性限制,不是优化能解决的。
还有一个常被忽略的代价:代码复杂度。链表的插入删除要维护多个指针,边界情况多,空链表、单节点、头尾操作都要单独考虑;数组的边界主要是容量和下标,逻辑更直。维护成本也是成本,尤其是在团队协作里,能用一个数组解决的问题,不该为了「理论上的插入优势」换成链表。
真正该做的判断是:先写出最直白的数组版本,测量它在真实数据量下的表现;只有当中间插入删除成为瓶颈,并且已经能拿到位置引用时,再考虑链表。不要反过来,先选链表再找理由。
当天能做的练习
- 用本文的
appendSlow和appendFast,分别追加 1 万、2 万、4 万条,记录耗时,画出「数据量翻倍、时间大约翻四倍」的对照。 - 实现一个动态数组,手动维护长度和容量,容量按 2 倍增长,统计插入 10 万条时一共复制了多少个元素。
- 在数组中间反复插入 2000 次,再在链表已知节点后插入 2000 次,记录耗时,并解释为什么数组慢、链表快。
- 写一个顺序遍历函数,分别遍历 20 万个元素的数组和链表,预热后各跑五次,记录平均耗时,说明缓存局部性在结果里起了什么作用。
- 把一个「按值删除」的链表函数改成「持有节点引用删除」,对比两种写法的遍历次数,确认 O(1) 只在后一种成立。
小结与下一篇
三句话收一下:数组的随机访问来自地址计算,链表的已知位置插入来自改指针,两者的优势都有前提;数组的扩容是均摊便宜、单次昂贵,链表的追加只有在维护 tail 时才是常数;缓存局部性让同样的 O(n) 在真实机器上差出好几倍。
下一篇进入 B 树与 B+ 树。数组和链表解决的是「内存里怎么排元素」,而数据库面对的是「磁盘上一页一页读」。B 树把多个 key 放进一个节点,降低树高;B+ 树再把所有数据放到叶子并串成链表,让范围查询不用回到上层。理解了这一篇的成本模型,下一篇的「一次查询读几页」就不会只是背结论。