为什么说现代计算机体系里链表已死？不是插入删除都是 O(1) 吗？

姐妹们我来说个踩雷故事。之前做游戏服务器，人物背包用链表存物品，想着删一个加一个方便嘛。结果上线后，玩家一打开背包就卡顿，尤其仓库里塞了上千件物品时，那遍历速度绝了。
后来一查性能，好家伙，每次打开背包要遍历所有物品做UI排序，链表每个节点地址不连续，UI线程卡了200ms。改成vector+对象池后，打开速度降到5ms。玩家反馈说“优化前像在玩PPT，优化后真流畅”。
所以链表不是不能用，但你要明确知道它的坑：不适合遍历、不适合随机访问、不适合大数据量。你发现宝藏了吗？数组+预先分配内存才是真香。

楼主你这个问题问得好，我一开始也是这个思路。后来有个场景直接让我破防了：之前做数据库索引，用链表存叶节点链，结果一条select查50万行，因为链表不连续，预取都救不回来，性能比B+树差了20倍。
当时组长让我改，我还不服，说复杂度都是O(n)啊。组长直接说：你去看看你这50万行数据在内存里分散了多少个页面。我一查，好家伙，50万个节点占了20万个不同的4KB页面，每个页面就装两三个值。这叫内存碎片，你CPU光等内存就等到天荒地老。
所以链表没死，但在高性能场景下，基本上就是个坑。你写几百个节点的小玩具当然感觉不出来。

这事儿还是得从我工作第四年一次优化经历说起。当时接手一个C++消息队列模块，用链表存的，处理100万条消息要8秒多。我一开始跟你想的一样，O(1)插入删除有什么好优化的？结果一profiling，热点全在内存访问上。
链表每个节点都在堆上乱分配，CPU缓存线一访问就miss。我把链表改成vector+位图，预分配一段连续内存，访问命中率从30%干到85%，处理时间直接降到1.2秒。那8秒里真正有用的计算可能不到1秒，剩下的全是在等内存。
所以不是链表算法复杂度有问题，是现代CPU的瓶颈已经从计算变成了内存访问。数组你能预加载一整条缓存线，链表你每个节点都得等一次cache miss。前提是数据量大到L2/L3放不下时，这个差距就是数量级的。
我后来总结：链表作为一个数据结构没错，但大多数人忽略了这个时代CPU才是真正的"老板"。

不同意楼上完全判链表死刑的看法。链表在嵌入式或实时系统里还有它的位置，比如内核里的双向链表，因为那里没法用vector那种动态扩容，而且节点数目少。但你说现代大型应用，服务器、游戏、数据库这些，确实不太行了。
我补充一个自己遇到的：之前做网络协议栈，消息队列用无锁链表实现，因为不需要复制整个数组，并发插入删除确实快。但后来发现，偶尔有节点在CPU缓存里被踢出去，导致生产者消费者延迟波动大。最后改成RingBuffer + CAS，稳定很多。
所以规律是：如果你对延迟抖动敏感，就别用链表；如果你就是写个几十个元素的链表玩玩，那随便。但那种场景你说"已死"也不合适，它只是从主角变成了特种兵。

家人们说破天了还是那句话：现代CPU最重要的优化就是缓存亲和性。链表天然就是缓存杀手。
我举个极端例子，你写个for循环遍历一个链表，每个节点都malloc一次，内存地址随机分配。CPU读第一个节点，等50ns（L3 miss）；读第二个节点，又等50ns。加起来就是100ns。但同样操作换成数组，两次连续地址，一次L1命中0.5ns就搞定了。
所以那些吹链表O(1)插入删除的，真的是活在算法书里。现实世界里你写个LRU缓存，核心操作不是插入删除，而是查找，查找链表你得O(n)遍历，数组虽然插入O(n)但查找O(1)而且能二分。最后谁赢？看场景。
我自己写代码到现在，除了写算法题面试，日常基本不用链表。真的会谢。