为什么老码农都说现代计算机体系里链表已死？我写个LRU缓存还用不用

老哥，你这个问题问得好，但你想反了。你以为是数据结构的问题，其实是内存模型的问题。
链表已死不是因为 O(1) 没用了，而是因为它把数据散得到处都是。你想想，你一次 Cache Miss 要等几百个时钟周期，这期间 CPU 能跑多少条指令？你插入删除省下的那点时间，全被内存访问的延迟吃回去了。
我自己写高性能服务的时候，别说链表，连 vector 里存指针都嫌 Cache Miss 多。都是直接用内存池分配连续内存，然后用索引代替指针。你 LRU 真要写，建议用数组存 key，再搞个单调递增的时间戳来淘汰，那性能绝对比你用链表舒服。
别被教科书绑架了，你是在真机上跑，不是在做算法题。

楼上说得对一半。链表已死其实是个伪命题，它只是从"主力结构"降级成了"特定场景专用"。
前提是你得区分两个概念：逻辑上的链表和物理上的链表。逻辑链表是用指针串起来的，物理链表是在一块连续内存里用索引模拟的。现代系统里，物理链表（内存池/预分配）还活得很好，因为它能保证 Cache 友好。逻辑链表（std::list）才是真的死透了。
你的 LRU 场景就是典型例子。容量 1000 以内的 LRU，用数组完全够了；容量上百万的，纯逻辑链表会把你性能拖垮。所以答案是：不用纠结，量小用数组，量大用哈希表 + 物理索引链表。教科书里的链表，留给面试就好。

我懂你这种困惑，我当年也是从教科书里学完链表，兴冲冲去优化项目，结果被现实教育了。
去年我被分配优化一个订单状态机的模块，逻辑里用了大量链表来管理状态流转。我花了一周把逻辑理清楚，就是没用。后来我把链表换成定长数组 + 索引维护，同样逻辑，处理时间从 4 秒降到 0.6 秒。因为订单状态流转是有上限的，几十个状态而已，数组根本不需要 O(1) 插入删除，我直接预分配，顺序访问快得一批。
所以别迷信 O(1)，数据量小的时候，一切复杂度都是纸老虎，Cache 才是爸爸。你的 LRU 要是容量固定，用数组 + 时间戳轮转就行，比链表简单多了。

这事我也想问，但后来想明白了，就是一句话：算法复杂度骗人，Cache Miss 吃人。
家人们，我 2025 年优化过一个消息队列的消费者，用的链表存待处理消息，结果吞吐量卡在 2 万条/秒。改成环形数组后，直接干到 8 万。你说链表 O(1) 插入有毛用，排队用的还是数组。
你那个 LRU 别纠结了，直接上数组 + 时间戳，真不行加个哈希表辅助，绝对够用。真的会谢，教科书害我。

姐妹，这事我太有共鸣了。我去年实习的时候，mentor 让我优化一个用户 session 管理模块，我看代码里用了链表存活跃 session，觉得挺经典的，没敢动。结果压测一出来，QPS 上不去，CPU 全在等内存。
后来 mentor 带我改成了数组 + 时间戳淘汰，代码量少了三分之一，性能翻了一倍。我当时心里就是：这就是传说中的教科书陷阱吧。宝藏 mentor 跟我说，真实工程里，数据结构的选择第一看的是 Cache 局部性，不是算法复杂度。
所以宝子，你的 LRU 用数组没问题，只要容量够小，时间戳轮转的方式又简单又高效，比链表好维护多了。踩过一次雷，现在就特别信这个。

楼上说链表已死的，大概率是被面试题洗脑了。兄弟你想想，你写业务是天天在千万数据里做 O(1) 插入删除，还是天天在几万条记录里查个值？后者数组二分查找 O(log n) 比链表遍历快几十倍。
至于 LRU，工业级实现早就不用纯链表了，都是哈希表 + 双向链表混合，或者直接用 Timestamp 排序的数组。你去看 Redis 的实现，早改成跳表了。
真要写 LRU，建议先看看现代 CPU 的缓存行是多大，你那个节点指针把内存都打散了，Cache Miss 比你插入删除省的时间多多了。这就是为什么老码农说链表已死。

其实这个没那么复杂。核心问题就一句话：CPU 的缓存系统按 64 字节对齐访问，链表节点分散在内存各处，每次访问都是 Cache Miss，而数组连续存储，一次加载能命中多个元素。
实测数据：在 2.6GHz 的 CPU 上，访问链表节点（Cache Miss）耗时约 100ns，访问数组元素（Cache Hit）约 1ns。差了 100 倍。你要插入删除是 O(1) 也没用，因为你在 O(1) 时间里只做了一次操作，但那次操作本身要等 100ns。
所以我的建议是：LRU 容量小于 1 万，用数组；大于 1 万，用哈希表 + 数组索引，别碰指针链表。这不是个人偏好，是硬件架构决定的。