我用JavaScript写了个链表，性能测试结果意外

事情的开端很朴素：项目里有个列表，需要在中间频繁插入和删除元素。数组的 `splice` 每次都要搬移后面的所有元素，理论复杂度 O(n)，看得我心里发毛。于是我花了一个下午，用 JavaScript 手写了一个双向链表，信心满满地准备迎接性能飞跃。

结果跑完 benchmark，我盯着屏幕愣了很久——链表几乎全面落败，遍历甚至比数组慢了将近十倍。

我的实现与测试设计

实现没什么花哨的，就是标准的节点对象：

class Node {
  constructor(value) {
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

`push`、`insertBefore`、`remove`、`forEach` 一应俱全，插入和删除都是改几个指针的事，教科书意义上的 O(1)。

测试用了 10 万条数据，分四组：尾部追加、随机位置插入、全量遍历求和、随机删除。跑之前我的预期是：插入删除链表碾压，遍历数组略胜。

实际结果是：尾部追加数组快约 3 倍；随机插入在数据量小的时候数组反而快，只有到几十万量级链表才勉强追上；遍历数组快 8 到 10 倍；随机删除两者接近，但链表并没有明显优势。

为什么理论和现实差这么远

第一个原因是内存局部性。数组在内存里是一段连续空间，CPU 预取器能大摇大摆地把后面几十个元素一起拉进缓存。而链表的每个节点都是独立分配的堆对象，散落在内存各处，遍历一次就是一次指针追逐（pointer chasing），每一步都可能踩中缓存未命中。这个代价在现代 CPU 上非常昂贵，往往比多搬几个元素的成本还高。

第二个原因是对象的开销。数组里存 10 万个数字，V8 可以用紧凑的 `PACKED_SMI_ELEMENTS` 表示，基本就是一段原始内存。而链表每个节点都是一个带隐藏类（hidden class）的对象，除了 value 还要存两个指针，外加上对象头和可能的对齐填充。同样的数据量，链表占用的内存可能是数组的三四倍，GC 压力也随之上升。测试跑久了，我能明显看到链表那组的 GC 次数更多。

第三个原因是JIT。V8 对数组的遍历、`push`、甚至 `splice` 都有大量针对性优化，很多循环能被优化成接近机器码的紧凑形式。而指针跳跃的循环难以向量化，分支预测也更容易失败。

还有一个让我意外的点：`Array.prototype.unshift` 在 V8 里对小数组是有优化的，并没有我想象中那么慢。Big-O 里的那个 n，在 n 很小时根本打不过常数因子。

那链表真的没用吗

也不是。我后来复盘，链表在这几种场景依然有不可替代的价值：

- 持有节点引用做删除和插入时，数组的 `splice(index)` 需要先知道 index，而链表拿到节点就是 O(1)，这在 LRU 缓存、事件监听器链表这类结构里很关键；
- 数据量极大且插入极其频繁，数组每次搬移的成本被放大到无法忽视时；
- 需要稳定的迭代器，遍历过程中增删元素不会像数组索引那样错位；
- 避免大数组扩容抖动，链表按需分配，没有一次性扩容和复制的尖峰。

但这些场景都有个共同前提：你真的测过，而不是"我觉得链表应该更快"。

写在最后

这次经历给我最大的教训是：复杂度分析描述的是增长趋势，不是真实耗时。它默认所有基本操作代价相同，可现代硬件里，一次缓存命中可能比一次指针解引用快几十倍。JS 引擎的优化又把这层差距进一步放大。

所以现在我的习惯是，先写数组版本，只有当 profiling 明确指向这里的拷贝或搬移时，才考虑换数据结构，而且换完一定重新测。教科书上的数据结构没有过时，但它们是为抽象的机器写的，而代码跑在真实的硅片上。

链表我还是留着，只是从"默认更优解"降级成了"特定场景的工具"。