“链表已死”（或“linked list is dead”）这句话在现代高性能编程圈子里被反复提起，主要指的不是链表完全不能用，而是在当代主流计算机体系结构（2020年后尤其是消费级/服务器级硬件）下，单向/双向链表在绝大多数性能敏感场景里已经很难成为最优解，甚至经常成为明显最差的选项之一。
核心原因就一句话：
现代CPU的性能早已不再主要受“计算”主导，而是受“内存访问延迟 + 缓存命中率”主导，而链表是缓存不友好到极致的结构。
为什么链表在现代机器上表现这么差？
| 维度 | 数组 / vector / deque（连续内存） | 链表（分散指针） | 实际差距（典型场景） |
|---|---|---|---|
| 缓存局部性（cache locality） | 极好：一次cache line加载多个元素 | 极差：每个节点大概率跨不同cache line | 5–50× |
| 预取（hardware prefetcher）有效性 | 非常有效（顺序访问） | 基本失效（随机跳转） | 大 |
| TLB命中率 | 高（连续页） | 低（到处跳页） | 中等–大 |
| 平均内存访问延迟 | ~4–12 ns（L1/L2命中） | 经常落到主存 ~50–100+ ns | 10–30× |
| 遍历1亿个元素耗时（实测） | ~几十到几百ms | 几秒到十几秒（视内存碎片程度） | 10–50× |
| 随机插入/删除 | O(n) 但有批量优化空间 | O(1)（找到位置后） | — |
| 顺序插入/删除（尾部） | 均摊O(1)（vector） | O(1) | — |
一句话：现代CPU单次从内存取数据的时间 ≈ 执行几百到上千条指令的时间。
所以“少访存、命中缓存”比“少几条指令”重要得多。
链表最致命的几个场景（也是大家喊“已死”的地方）
- 游戏引擎 / ECS（Entity Component System）
每帧遍历几万–几十万实体 → 链表遍历直接把帧时间拉爆，改成SoA + 连续数组后性能提升几倍到十几倍很常见。 - 高频交易 / 低延迟系统
p99延迟差几微秒都致命，链表的内存跳跃让延迟抖动极大。 - 数据库 / KV存储热路径
跳表、链表桶在小数据量还行，一旦规模上去，cache miss把吞吐量干到地板。 - 排序、搜索、图遍历等算法教学 vs 实际
教科书里O(1)插入很美，但真实机器上cache miss把常数项拉到几十上百倍，整体性能反而输给vector。
那链表到底什么时候还能用？
能用，而且在某些场景仍然是好选择（或不得不用）：
- 数据量很小（几百个节点以内）
- 极频繁的中间插入/删除，且几乎不遍历（只做增删）
- 需要稳定的迭代器/指针不失效（std::list的经典优势）
- 作为“自由列表”（free list）管理内存块本身
- 极特殊的无锁并发场景（lock-free链表仍有价值）
现代“链表已死”更准确的说法
“作为默认数据结构或性能第一考虑的容器，链表已经基本死亡。”
主流建议排序（2024–2026年共识）：
- 需要顺序 + 经常遍历/查找 → 用
std::vector/std::deque/absl::InlinedVector/small_vector - 需要频繁中间插入且规模不大 → 用
boost::container::devector/std::deque/ 分块链表 - 真的需要O(1)插入 + 指针稳定 → 用侵入式链表（intrusive list）+ 内存池（减少cache miss）
- 教学 / 面试 / 写算法题 → 随便用链表，没人扣你cache miss
总结：
不是链表的算法复杂度错了，而是现代硬件把“内存访问模式”变成了新的复杂度，而链表在这场游戏里几乎是作弊级别的差选手。
你现在代码里还有大量用链表的地方吗？还是已经全部vector化了？
