本博客日IP超过2000，PV 3000 左右，急需赞助商。
极客时间所有课程通过我的二维码购买后返现24元微信红包，请加博主新的微信号：xttblog2，之前的微信号好友位已满，备注：返现
受密码保护的文章请关注“业余草”公众号，回复关键字“0”获得密码
所有面试题(java、前端、数据库、springboot等)一网打尽，请关注文末小程序
【腾讯云】1核2G5M轻量应用服务器50元首年，高性价比，助您轻松上云
今天，群里有人发了一个知乎上的问题，在群里讨论的热火朝天。
我看了一下，造成大家风评的原因是，实测数据有些反直觉，和教科书上的“过时内容”也有些相违背。甚至有人拿出了知名大佬，比如 C++ 之父 Stroustrup、Linus Torvalds 等人的言论来支持自己的观点。
再结合网上一些老外的热议，大致分成了三派。
- 链表已死派：在性能敏感的代码里，链表几乎永远是最差选择；
- 输给数组派：链表没死，但在大多数场景下确实输给了数组；
- 退居幕后派：链表没死，但它已经从舞台中央退到了幕后。
有意思的是，早在十多年前，国外顶级程序员就为此“打过架”，C++ 之父甚至专门写了一篇短文回应：《Are lists evil?》。
链表也曾是主角
在大学里，相信大家都学过数据结构。其中，针对数组和链表大概率有这句话：
数组查询快，链表插入快。数组插入删除要搬移元素，链表只需改改指针。
在纯算法分析的课堂上，这个结论天经地义，数组中间插入是 O(n)，链表是 O(1)。大 O 记号一摆，链表赢得干净利落。
但这个结论有一个隐藏前提，它假设“访问内存”是免费的，成本只算“基本操作次数”。
问题就在于现代计算机恰恰不是这么算账的。
内存墙与缓存
过去的几十年里，CPU 的运算速度指数级上涨，而内存（DRAM）的延迟改善得极其缓慢。两者的差距越拉越大，形成了所谓“内存墙”（Memory Wall）。如今一颗桌面级 CPU，访问 L1 缓存大约只要几个时钟周期，而访问一次主内存，可能要多付出上百个周期的等待。
为了弥合这个鸿沟，现代 CPU 在寄存器和内存之间塞进了多级缓存（L1/L2/L3），并且有两个关键机制：
- 缓存行预取：CPU 从不按字节取数据，而是按 64 字节左右的缓存行整块加载。你访问了一个 int，它隔壁的 int 也顺带进了缓存；
- 硬件预取器：如果发现你的访问地址是线性递增的，CPU 会提前把后面的数据也搬进缓存。
这就引出了著名的局部性原理（Locality）。空间上相邻、时间上相近被访问的数据，才是现代 CPU 的“宠儿”。有讨论者总结得很直白，现代 CPU 的性能，极大程度上取决于数据离核心有多近，而 Cache Miss 正是由于要访问的数据太远所导致的。
文章多张配图参见：https://mp.weixin.qq.com/s/M-FKnd1kvdwvRtRNdsDK6g。
而链表，恰好把这两条全踩中了。
- 节点分散在堆内存各处，每跳一次指针都可能是一次缓存未命中；
- 遍历时”先读到指针，才知道下一个节点在哪”，硬件预取器对这种随机跳转完全无能为力，专业术语叫“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++ 之父 Bjarne Stroustrup 给的结论是“默认用 vector”，至少他个人是这样的。
无独有偶，大佬 Chandler Carruth 也说过：请对链表说“不”。
如果说 Stroustrup 还留了几分情面，那 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) 快。
最后，欢迎关注我的个人微信公众号：业余草（yyucao）！可加作者微信号：xttblog2。备注：“1”，添加博主微信拉你进微信群。备注错误不会同意好友申请。再次感谢您的关注！后续有精彩内容会第一时间发给您！原创文章投稿请发送至532009913@qq.com邮箱。商务合作也可添加作者微信进行联系！
本文原文出处：业余草： » 链表已死？C++ 之父，O(1) 不一定比 O(N) 快