说实话，我看到网上太多文章一开口就是“数组查询快，插入慢；链表插入快，查询慢”，然后配一张工资对比图就完事了。这种说法不能说错，但会把人带偏。比如我负责一个用户行为分析服务，用链表存活跃会话，结果一到高峰期CPU使用率飙到85%，接口P99延迟从30ms涨到了450ms。拿火焰图一看，不是业务计算，全耗在遍历一个200万节点的链表上。
问题出在哪？链表每个节点都是malloc出来的，在堆上乱糟糟地分布。你遍历它，相当于每访问一个节点就要跳一次内存地址，CPU的cache line每次都只抓住一个节点，还没等用完就丢了。而数组是连续内存，一次预取能加载好几个元素到L1 cache。我查了linux下perf的数据，数组遍历的cache miss率大约在2%左右，链表随便就超过30%。这在现代CPU上是数量级的差距，教科书里根本没讲这些物理细节。
有人说那用B+树啊，innodb都在用。但你要分清场景。Redis的quicklist其实是一个双向链表加ziplist的组合，还引用了skiplist做有序集合查询。它为什么不用B+树？因为Redis是内存数据库，它的瓶颈是内存分配和复制，而不是磁盘IO。B+树的设计是为了减少磁盘寻道次数，单次查询可能要碰几个节点，在内存里反而不如紧凑的ziplist连续遍历快。我做过一个小测试，往Redis里塞100万个整数，用LPUSH 100万次再LRANGE全取，quicklist的整块分配让内存碎片率只有1.2%，而用普通的skiplist当list用，碎片率直接到了5.8%，内存多了快15MB。
所以重要的不是选哪个数据结构，而是要知道它背后的物理约束。比如你要设计一个高频写入的日志系统，用链表也可以，但最好用内存池来分配节点，让节点在物理上尽量连续。你甚至可以把链表改成“数组链表”，也就是你先分配一个大数组，然后用下标当指针。我看到LMAX Disruptor源码里就是这么干的，它用环形数组加序列号，避免了锁和GC，每秒钟能处理600万订单。那种用std::list来存高频事件的，我只能说线程池再大也救不了你。
对了，还有跳表。很多人把它当成链表的平替，其实跳表的本质是“空间换时间的概率化索引”。它每个节点的层数由硬币决定，所以最坏情况会退化成链表。我遇到过一个线上问题，一个库存扣减服务用跳表维护待出库订单，结果随机种子因为哨兵节点被重复构造，导致所有节点都只有一层了，性能从O(log n)掉到O(n)，订单积压报警。后来我改成固定层数3层的确定性跳表，或者干脆用数组二分定位，虽然灵活性降了，但再也不怕概率翻车。
最后说点实际的吧。如果你面试被问“数组和链表到底怎么选”，别只回答复杂度，你可以从这几个角度拆：容器的内存区域是堆还是栈？数据规模是固定还是动态增长？操作是遍历多还是插入多？你能不能让CPU的预取器摸到规律？举个我自己的经验，动态路由表的匹配节点，我用的是数组加二分，而每个节点后面的子节点才用链表，因为子节点数量通常很小，链表的不连续开销可以忽略。这样总体相比纯链表快了2.3倍，代码也就多了二十行。
