为什么都说“链表已死”？我用了十年C++，感觉链表还是很有用的啊，是时代变了吗？

楼上说得对一半吧。我补充一个：现代编程语言里的vector或list，底层也可能是数组+内存拷贝，但人家优化得好，几十万次插入也就几十毫秒的事。除非你业务场景特别变态（比如几十W个节点频繁插入删除），否则链表那点优势根本体现不出来。家人们，别跟链表死磕了，大部分时候用数组加个reserve就够用。不然真的会谢，优化到半夜发现瓶颈不在数据结构，在I/O，那才叫破防。

其实你想反了。说“链表已死”的人，大多是针对通用高性能场景，比如数据库、搜索引擎、高频交易。这些地方数据量大、对延迟敏感，连续内存的数组才是爹。但你要是做底层驱动、内存受限的系统，链表反而香，因为它能动态伸缩，不用预先分配一大片内存。所以我一直觉得，不是链表死了，是编程的大众场景变掉了，现在谁还手撸链表？STL不香吗？

我也亏过。2022年一个项目，用链表做LRU缓存，自我感觉良好，上线后延迟高得离谱。查了两天，发现链表查找某个key时，每次都得从头遍历，复杂度O(n)啊。后来换成哈希表+双向链表，查找O(1)、删除O(1)，才救回来。链表不是不能用，是你得知道它适合啥场景：频繁插入删除头尾、不依赖随机访问。你要是满世界遍历查找，那它必死。

这事我也想问呢，老哥。我之前做后端，一段数据处理模块全用链表写的，自以为很nb。结果压测一跑，QPS直接拉胯，比旁边用vector的同事慢了6倍。我当时心态炸了，不是说插入删除快吗？后来一查，插入删除确实是O(1)，但你遍历一遍数据，cache miss严重到爆，CPU等内存的时间比算数据的时间还长。真别迷信理论复杂度，现实里硬件不答应。

楼主你这个数据靠谱吗？我自己以前写游戏服务器，用链表做玩家列表管理，内存池手动分配节点，让节点内存紧挨着放，遍历速度其实不比vector差多少。关键是你得会用。很多人直接new一个链表，节点在堆上到处散着，那肯定死。说链表已死的，多半是没玩明白。当然你要是图省事，无脑用数组确实更稳。

这个其实没那么复杂。现代CPU搞了三级缓存，数据读进L1是几个纳秒，从内存读要上百纳秒。链表的节点在内存里东一个西一个，遍历的时候CPU疯狂等内存，能不慢吗？而数组是一片连续内存，预取机制直接把整块拉进缓存，遍历速度碾压链表。所以说“链表已死”不是夸张，是硬件演进的结果。当然你嵌入式代码量小、节点少，无所谓，但大规模数据处理就别犟了。