为什么说链表在现代程序里已经废了？我用 C 写过链表觉得还行啊

这事我也想问。大概 2023 年在一个订单处理中间件里，老代码用链表存待处理的订单队列。我看逻辑很清晰，插入删除 O(1)，以为捡到宝了。结果压测一跑，QPS 上来就掉到 3 位数，CPU 跑 90%。
后来我换成 vector + 内存池，QPS 直接翻了将近 6 倍。你也别说我代码写得烂，前提是你仔细看过 CPU 的缓存行命中率吗？链表节点是分散分配的，每次读下一个节点几乎都是 cache miss，现代 CPU 流水线一停，O(1) 都是假的。最后那段代码被组里大佬拿去做成了组件库的基础设施，我用 vector 的做法也被骂过结构太死板，但至少不出错。前提是你搞清楚瓶颈到底在哪，不是链表的锅就是我乱说了。
嗯，反正链表在数据结构课里没问题，放到实际服务器上，那一根根链子拉得 CPU 想哭。

我也亏过，2024 年优化一个内存数据库的 B+ 树实现，写到最后发现叶子节点内部用链表比数组慢 3 倍。我就是那个用 C 写过链表然后沾沾自喜的傻逼。
个事吧，我那批货是批量订单的状态机，每个订单的状态变化需要频繁在链表里前后插入删除。结果跑一次全量同步，CPU 的 DTLB miss 报了 40%，内存碎片一天涨 30M。最后改成 vector+小索引，问题解决。链表不是数学上不行，是硬件不惯着它了，内存随机访问就是比链表连续拜访慢一个数量级。
我看到你说你写 C 链表，我 2023 年也写过，现在回头看就是自嗨。不过我劝你别急着重构，先看看你的数据规模是不是大到可以忽略 cache 的影响。有时候在十来个节点的小链表里，链表确实不慢。

家人们，这个我真被坑过。2024 年在一个实时风控系统里，老代码用链表存 50 万个规则节点，每秒匹配数千次请求。结果 CPU 跑 80%，我把链表改成 hashmap + 连续数组，QPS 从 1200 提到了 6500。真的会谢。
刚毕业那会觉得链表好优雅，现在看就是坑。插入 O(1)？CPU 等缓存命中的时候你的请求排成队等着崩。后来我学乖了，设计数据结构第一先问"数据能连续存储吗"，第二才问"增删复杂度是多少"。顺序访问和随机访问在现代机器上不是一个量级，链表生错了年代。反正我就一句话：如果你还在用链表做核心数据结构，赶紧测一下 cache miss 率，崩的时候别怪我没说。

楼上说得对一半。链表不是死透了，是它的应用场景已经被 CPU 缓存和内存带宽压没了。
楼主你问为什么，我给你拆一下：现在内存访问延迟大约 100ns 一次，但连续访问一堆地址，因为 cache line 预取，你第二次可能只要几个 ns。链表每次读 next 几乎都是新地址，cache 对你没用。O(1)？那是数学复杂度，物理上是 O(cache miss count)。我现在做实时计算优化，2024 年的机器用链表处理每秒 50 万的流，直接绷不住，换成 flatbuffers 的定长数组才稳住。
补充一下，我觉得链表没有完全废，在那老时代硬件下它还能打。但现代 CPU 的主频和 cache 速度差距已经到了离谱的程度。你试试用链表存 50 万个节点，然后拿 perf 跑读一下，看看 l1d_loads 和 l1d_misses 的比例，就会懂了。反正我那次优化完性能提升 30%，就靠把链表干掉了。
所以别听那些教科书吹 O(1)，要听硬件说话。

其实你想反了。链表在物流和电商系统里反而活得不错，因为数据量小 + 对新增删除敏感。
我做跨境物流那几年，订单状态机里每个包裹的状态变更要用链表存最后一次操作的时间戳和操作员 ID。量不大，最多一个订单十几个状态，不到 50 个节点。链表插入 O(1) 的优势在这种规模下反而比数组快的多，因为不需要 memmove 整个数组。2024 年我给一个仓库系统做的 TMS 优化，老代码用 vector 存状态，每天处理 20 万票，删除一个中间状态要搬 20K 的内存，改成双向链表直接省掉 5% 的处理时间。
我跟楼上观点反过来：数据规模决定一切。你如果做企业级后台，链表未必死。做高并发缓存系统，那确实死透了。所以别一刀切。

姐妹们，这个我深有体会。2024 年我在做一个日志聚合系统，数据量大概一天几百 G，里面用链表做事件队列，本来想着快速插入删除很优雅。结果跑了一周，内存碎片化严重，最后 OOM 崩了一次，公司群直接炸了。后来我改成自定义 arena 分配器 + 固定大小的数组，直接省掉 30% 内存使用。
我一开始也觉得链表很"软工"，每个节点独立分配很灵活。但后来发现一个宝藏替代方案就是 intrusive list，节点数据就嵌在原结构体里，没有额外内存开销，而且可以连续分配。这不就是既要 O(1) 又要 cache 友好吗？踩了这个坑之后，我整个人的数据结构观都变了。现在看到教科书上链表插入 O(1) 我都想笑。
当然不是所有场景都能用 intrusive list，但至少比裸链表靠谱太多。