为什么都在说链表在现代计算机体系里已经死了？面试题也不爱考了

这事儿我是有切身体会的。大概是工作第三年的时候，接手了一个数据处理模块的优化任务，那个模块性能很差，处理一批数据要跑十几秒。我去看代码，发现核心数据结构用的是链表，心想这不对啊，链表插入删除都是O(1)的，怎么会慢呢？当时我还挺自信的，觉得肯定是别的地方写得烂。结果折腾了两天，把算法逻辑优化了一遍，该缓存的缓存，该批量的批量，性能提升了大概百分之十五。十五。我优化了两天，换来百分之十五。后来组里一个老哥来扫了一眼，说你把链表换成动态数组试试，测试一下。我换了，性能提升了三倍。
那就是链表在现代CPU体系下的死穴：CPU缓存。链表节点在内存里是东一块西一块的，迭代一次触发无数次cache miss，一个cache miss几十个纳秒，几千个节点就是毫秒级的浪费。而数组是连续内存，预取直接读完一整块。在追求吞吐和延迟的工程场景里，这个差距太致命了。
现在除了纯学术考框架、或者必须频繁大改中间节点、且数据量小到可以忽略cache miss的情况（比如实时系统的某些调度队列），链表真的没什么存在感了。面试不考，正说明工业界已经达成共识：能用数组就别碰链表。

这个其实没那么复杂，核心就一句话：链表的时间复杂度在理论上是O(1)操作，但在现代硬件下，cache locality才是真正的O(1)。数组的连续内存访问让CPU预取器能猜到你下一步要读什么，链表做不到。
前提是你做的是大数据量、高吞吐、延迟敏感的场景。比如写数据库的索引树，从B树进化到LSM树，底层存储从链表换成连续块+跳表，根本原因就是cache miss太贵了。你说读一个节点50ns，写一个节点还是50ns，加起来几十几百MB的数据遍历一次，直接变成几十ms的延迟，谁受得了。
当然，链表在特定场景里依然有它的生态位。比如在一些RTOS（实时操作系统）的任务调度队列里，任务总数一般就几十个，cache miss成本可以忽略，而且插入删除频繁，链表就比数组方便。但这种场景太小众了，你面试要说这个，面试官大概率觉得你在炫技。

家人们，这事我真的绷不住。我面过一家小创业公司，面试官问我“Redis用链表做什么”，我说“存储list对象”，他问我“那为什么现在改成了quicklist？”我说“因为链表内存碎片化严重”，他直接说“不，是因为quicklist对CPU缓存更友好。”我当时真的会谢，我敢说我被一个业余水平的面试官给忽悠了。
其实链表在现代计算机里真的就像那个“渣男数据结构”，理论上深情（O(1)）实际上一地鸡毛（cache miss）。我现在写代码，除非是写那种特别小的嵌入式驱动，其他时候一律用数组+二分查找，或者直接用哈希表。性能差不多，而且代码更直观，debug也轻松。
奉劝各位八股战士：链表可以学，但别当神供着。面试官现在更爱听你聊“为什么不用链表”。

你确定现在的面试题真的不考了吗？我2025年面了美团和字节，LRU Cache那道题好几个面试官现场让我手写，但我当时写的是双向链表+哈希表，面试官也没说啥。不过后来跟一个朋友聊，他说现在很多公司面试会问“能不能用LinkedHashMap直接实现”，让你分析链表的优缺点。
其实从工程角度，现在主流的库比如Java的LinkedList已经标注了@Deprecated，推荐用ArrayDeque替代，原因就是上面说的高速缓存问题。而C++标准库的list也很少有人用了，更多的场景是用vector+algorithm或者deque。
链表没有真的死，但作为候选数据结构，它的优先级被大幅降低了。你用链表能解决的问题，用数组+移位或者哈希表+数组大概率也能解决，而且性能更好。面试考链表更多是在考你对数据结构底层原理的理解，而不是让你真的在投产系统里写链表。

我懂你这种感觉，去年我被问了一道“用链表实现队列”的题，当时我还觉得很经典，结果面试官直接说“链表实现队列有什么优势？现代CPU缓存友好吗？”我当场脑袋嗡嗡的。
后来查了很多资料才知道，主要两件事把链表架在火上烤了。第一个是CPU缓存的连续性，之前楼上已经说得很清楚了。第二个是内存分配器的进步，以前malloc很慢，用链表可以预分配节点池，现在jemalloc/tcmalloc分配小对象快得很，链表这种好处基本没了。
扯个远的，你们知道Redis的quicklist为什么是从ziplist改过来的吗？因为纯链表存小对象的碎片化太严重，内存利用率低，所以干脆改成压缩列表分段存储+双端指针的形式。连追求极致性能的Redis都放弃了纯链表。
我觉得现在说链表“死了”太绝对，但作为通用数据结构，它在工程上的空间确实被数组和哈希表挤没了。

老哥，这个话题我熟。我之前接手过一个老的搜索推荐系统，底层用链表做倒排索引的合并，一个查询跑下来延迟十几秒，产品经理天天骂。后来我跟老大说换成数组+二分查找，把倒排列表存成连续内存块，测试结果延迟直接降到几百毫秒。老大当场给了我一个鼓掌。
链表就是那种“理论强无敌，实战拉胯”的典型。在80年代的计算机上它好用，因为当年CPU主频低、内存访问慢，链表可以预分配节点池，实现优雅的内存管理。但现在内存带宽几百GB/s，CPU乱序执行+预取，链表那点O(1)的优势在硬件加速面前就是个笑话。
所以面试不考链表，不是链表没价值，是大家懒得纠结一个几乎永远不会在工程里单独使用的数据结构了。你要是真想学，可以看看Linux内核里的一些链表实现，但那玩意是给设备管理用的，数据量小到可以忽略cache miss。咱们写业务代码的，还是老老实实用数组吧。