链表已死？C++ 之父：O(1) 为什么不一定比 O(N) 快

今天，群里有人发了一个知乎上的问题，讨论得热火朝天。

我看了一下，风评两极分化的原因在于：不少实测数据反直觉，和教科书上那些“过时内容”也对不上号。甚至有人搬出了 C++ 之父 Stroustrup、Linus Torvalds 这些大佬的言论来撑腰。

结合网上老外的热议，大致分成了三派：

• 链表已死派：在性能敏感的场景里，链表几乎永远是最差选择。
• 输给数组派：链表没死，但大多数情况下确实输给了数组。
• 退居幕后派：链表没死，只是从舞台中央退到了幕后。

有意思的是，早在十多年前，国外顶级程序员就为这事“打过架”。C++ 之父甚至专门写了一篇短文回应：《Are lists evil?》。

链表也曾是主角

大学数据结构课上，数组和链表这对老冤家的标准结论大概是这样的：

数组查询快，链表插入快。数组插入删除要搬移元素，链表只需改改指针。

纯算法分析的语境下，这个结论天经地义——数组中间插入是 O(n)，链表是 O(1)。大 O 记号一摆，链表赢得干净利落。

但这个结论藏着一个隐藏前提：它假设“访问内存”是免费的，成本只算“基本操作次数”。

问题恰恰在于，现代计算机根本不是这么算账的。

内存墙与缓存

过去几十年，CPU 的运算速度指数级上涨，内存（DRAM）的延迟改善却极其缓慢。两者之间的鸿沟越拉越大，形成了所谓的“内存墙”（Memory Wall）。如今一颗桌面级 CPU，访问 L1 缓存只要几个时钟周期，访问一次主内存却可能要付出上百个周期的等待。

为了弥合这个鸿沟，现代 CPU 在寄存器和主存之间塞进了多级缓存（L1/L2/L3），并且依赖两个关键机制：

1. 缓存行预取：CPU 从不按字节取数据，而是按 64 字节左右的缓存行整块加载。你访问了一个 int，它隔壁的 int 也顺带进了缓存。
2. 硬件预取器：一旦发现访问地址线性递增，CPU 会提前把后续数据一起搬进缓存。

这就引出了著名的局部性原理（Locality）——空间上相邻、时间上相近的数据，才是现代 CPU 的“宠儿”。有讨论者总结得很直白：现代 CPU 的性能，极大程度取决于数据离核心有多近，而 Cache Miss 正是数据太远导致的。

链表恰好把这两条全踩中了：

• 节点分散在堆内存各处，每跳一次指针，都可能是一次缓存未命中。
• 遍历时“先读到指针，才知道下一个节点在哪”，硬件预取器对这种随机跳转完全无能为力。专业术语叫 pointer chasing（指针追逐）。

数组的“插入要搬移元素”听着很贵，但 memcpy 连续、预取友好，实际快得惊人；链表的“插入只改指针”听着很便宜，但找到插入位置的那一路指针跳跃，可能已经吃了几十上百次缓存未命中。

大 O 说链表赢，CPU 缓存说链表输。裁判永远是跑出来的真实时间。

老外们的“判决书”

部分程序员不待见链表，理由很充分。

C++ 之父 Bjarne Stroustrup 在 2012 年 Going Native 大会的 Keynote 中，展示了一个经典实验——这题出自《编程珠玑》作者 Jon Bentley：把随机整数按序插入一个序列，再按随机位置逐一删除，链表还是数组？

结果相当反直觉：std::list 完败于 std::vector，哪怕这个操作序列表面上全是“链表擅长”的插入删除。

这个实验后来被很多人断章取义成“Stroustrup 说链表是邪恶的”，逼得他在 isocpp.org 上专门发文澄清。这篇文章值得每个程序员读一遍。他的原话是：我的重点根本不在链表本身。链表有它的用途，但这个例子不属于那些用途。请注意我的结论里既没有出现 list 也没有出现 vector。

don't store data unnecessarily（不存储不必要的数据）

keep data compact（让数据保持紧凑）

access memory in a predictable manner（以可预测的方式访问内存）

我强调缓存效应的重要性。我的经验是，除了真正的专家，几乎所有人在讨论算法时都会忘记这一点。

结尾他还补了一刀：建议默认使用 std::vector。更一般地说，除非有充分理由，否则优先使用连续内存的表示方式。C 和 C++ 就是被设计成默认这样工作的。

说白了，C++ 之父给的结论是“默认用 vector”。

无独有偶，Google 的 LLVM 技术负责人、C++ 委员会核心成员 Chandler Carruth 在 CppCon 2014 的演讲《Efficiency with Algorithms, Performance with Data Structures》里，态度激烈得多。他的金句被无数课件引用：Discontiguous data structures are the root of all evil.（非连续的数据结构是万恶之源。）

Please say no to linked lists. There is almost nothing more harmful you can do to the performance of an actual modern microprocessor than to use a linked list data structure.（请对链表说不。在现代微处理器上，你几乎找不到比使用链表更有害于性能的事情了。）

这场演讲在 YouTube 上有几十万播放，堪称“链表已死论”的源头之一。顺带一提，著名的 Reddit 梗图“Google 大佬说：别折腾了，用 List（数组）吧”，也是从这场演讲延伸出来的。

社区实测，输得有多惨？

口说无凭，看看社区里流传的实测。

有开发者复现了 Stroustrup 的实验，发现 list 直到元素体积达到 1KB 以上、且元素数量超过一万时，才开始在某些场景下反超 vector——此时 vector 搬移数据的成本才真正超过指针追逐的成本。

另一个更极端的例子来自 buddy 内存分配器的教学项目。同样的分配逻辑，用 std::vector 实现分配 1 GiB 内存花了约两分钟，换成 std::list 后慢到二十五分钟，相差十二倍以上。

在高性能 C++ 圈，“如果你在用 std::list，那你八成用错了；99% 的场合你该用 std::deque 或 std::vector”甚至成了某种编程正确。

链表真的死了吗？

有意思的是，哪怕是 Stroustrup 本人，也坚决反对“链表邪恶论”的极端版本。他说：“Obviously, that's absurd”（显然那很荒谬）。

事实上，链表从未死去，它只是换了个活法。

链表无处不在

打开 Linux 内核源码，list_head 这个侵入式双向链表随处可见：进程调度队列、内存管理、文件系统、定时器……几乎每一个子系统都在用它。

为什么内核偏爱链表？因为内核面对的是这样的约束：

• 节点生命周期由外部对象（进程、页框、inode）决定，不允许拷贝。数组式的“整体搬移”在内核里根本不可行。
• 要求 O(1) 摘除任意节点——一个进程随时可能被 kill，一个页框随时可能被回收。
• 链表节点里那 16 字节的前驱后继指针，不是负担，而是嵌入在对象身上的钩子。

Stroustrup 在 FAQ 里也承认，intrusive list 可以非常快。a vector is more compact and is therefore smaller and faster in many cases — even when you do inserts and erases（即使在插入删除时，vector 也往往更小更快），但这有个前提——“你真的需要一个 list”。在内核里，这个前提成立了。

链表依然有用

前面说过，元素体积超过 1KB、数量巨大时，vector 的搬移成本会让链表翻身。游戏引擎、物理引擎里的场景图、粒子系统，处理的都是这种大块头对象，链表（或基于链表的定制结构）依然是常客——大对象 + 插入删除密集，链表依然能够反杀。

学术研究里也有反例。2025 年一篇 arXiv 论文在真实 CPU 缓存层级下对比容器性能，发现在“大量摊还 O(1) 插入、极少遍历”的模式下，把 std::list 换成 std::vector 反而让整体运行时间增加了 30% 以上——链表是真 O(1) 指针操作，而 vector 的搬移在这个模式下成了主导成本。

大 O 分析没有骗人，只是它只在“内存访问成本可以忽略”的模式下才接近真相。

链表的新形态

今天的链表早已不是教科书里那个“一个数据域加一根指针”的朴素模样。它的思想活在大量现代数据结构中：

• 跳表（Skip List）：Redis 有序集合的核心实现，用多层链表换来 O(log n)。
• 无序链表化的 B 树 / B+ 树：数据库索引的底层，节点 fanout 拉满，兼具块局部性与 O(log n)。
• plf::colony、unrolled linked list（分组链表）：把多个元素塞进一个节点，减少指针追逐，是游戏业对链表的“现代化改造”。
• LRU 缓存：哈希表 + 双向链表的黄金组合，O(1) 定位 + O(1) 摘除，至今仍是工业标准答案。

这些结构继承了链表的“逻辑灵活性”，又用工程手段弥补了它的“物理局部性”。Chandler Carruth 自己在 CppCon 2016 的姊妹篇演讲里，讲的正是这种“混合数据结构”（Hybrid Data Structures）的设计哲学。

最后

回到开头的三派观点，其实各自都对了一半：

• 链表已死，对应用层业务代码成立。在大多数写 CRUD、遍历多于增删、元素又不大的场景里，无脑选数组（或 deque）几乎总是对的。Chandler Carruth 的话是对着这个“默认场景”说的。
• 链表输给了数组，对性能敏感场景成立。当访问模式确定、数据量上得去之后，缓存命中率就是生命线，连续内存就是王道。连 C++ 之父的建议都是“默认 vector，除非有充分理由”。
• 链表退到了幕后，对系统全貌成立。在内核、内存分配器、编译器、游戏引擎、数据库的深处，链表及其变体依然优雅地运转着。它们不再是课堂上的明星，却是支撑整个软件世界的“幕后工作者”。

其实从来不是“链表 vs 数组”谁赢谁输的问题。它给所有程序员上了一课：算法复杂度分析之外，还有一门课叫“计算机体系结构”；大 O 记号之上，还站着缓存行、预取器和内存墙。不要盲目相信 O(1) 一定比 O(N) 快。

如果你也对这类底层机制与数据结构选择的话题感兴趣，云栈社区上聚集了一批专注系统级开发的朋友，欢迎一起交流。