链表为什么缓存局部性差？它和数组遍历性能有什么区别？

简化版

链表节点通常分散在内存中，遍历时要不断跟随指针跳转，CPU 缓存和预取很难发挥作用；数组连续存储，顺序遍历能很好命中缓存。因此链表即使理论上插入删除方便，实际遍历性能也常不如数组。

详细版

链表和数组的复杂度差异不能只看大 O。数组遍历是 O(n)，链表遍历也是 O(n)，但常数差距可能很大。

原因包括：

• 数组元素连续，CPU 一次加载缓存行可能带来多个相邻元素。
• 链表节点分散，访问下一个节点前必须先读当前节点的 next。
• 指针跳转让硬件预取更难预测。
• 每个链表节点还要额外存指针，内存占用更高。

所以工程上不是“频繁插入删除就一定用链表”。如果主要操作是遍历、随机访问、批处理，数组或动态数组常常更快。

完整版教学

一、为什么 O(n) 不能说明全部性能

大 O 描述的是输入规模增长时的趋势，不直接描述常数成本。数组遍历和链表遍历都是 O(n)，但一次数组访问可能只是读取相邻地址，一次链表访问可能伴随缓存未命中和指针解引用。

假设访问 1000000 个整数：

数组：连续读 arr[0], arr[1], arr[2]...
链表：读 node，再读 node.next 指向的未知地址

两者都访问 n 个元素，但硬件感受到的内存访问模式完全不同。现代 CPU 很快，内存相对慢，缓存命中率会显著影响实际时间。

二、缓存行如何偏爱数组

CPU 不会每次只从内存拿一个字节，通常会按缓存行加载，比如 64 字节。如果数组元素是 4 字节整数，一条缓存行可能装下 16 个整数。

顺序遍历数组时：

加载 arr[0] 所在缓存行
arr[1] 到 arr[15] 很可能已经在缓存里

链表节点如果分散在不同位置，加载当前节点不一定带来下一个节点。每走一步都可能访问新的缓存行。这个差距不会出现在复杂度公式里，但会出现在真实耗时里。

三、指针追逐为什么难预取

硬件预取擅长识别规律地址，比如连续递增。数组遍历地址像 base + i * size，规律清楚。

链表的下一个地址藏在当前节点的 next 字段里：

必须先读 node.next，才知道下一步去哪

这叫 pointer chasing。它形成依赖链：下一次访问地址依赖上一次读取结果。CPU 很难提前把后续节点加载进缓存，所以流水线可能等待内存返回。

四、链表节点的额外内存成本

链表每个节点除了业务值，还要存指针。单链表至少一个 next，双向链表还要 prev。在 64 位系统中，一个指针通常是 8 字节。

对比：

结构	每个元素额外信息	局部性	随机访问
数组	很少	好	O(1)
单链表	next 指针	差	O(n)
双向链表	prev + next	更差一些	O(n)
块状链表	块内数组 + 指针	折中	块内较好

如果元素本身很小，指针开销可能比数据还大。比如存一个 4 字节整数，单链表节点光指针就可能 8 字节，还不算对象头和内存分配开销。

五、链表仍然适合哪些场景

链表不是没用，而是适用条件更具体。它适合已知节点位置后的 O(1) 插入删除、需要稳定节点引用、频繁把节点从一个位置摘下再接到另一个位置的场景。

例如 LRU 缓存中，哈希表能 O(1) 找到节点，双向链表能 O(1) 移动节点。这里链表不是用来遍历快，而是用来重连快。

如果你只有“按值查找再删除”，链表并不占优，因为查找已经 O(n)。面试中能说出这个前提，会比简单说“链表插删快”更准确。

六、工程选型怎么回答

工程选型要看操作分布。读多、遍历多、随机访问多，优先数组或动态数组；已知节点引用后频繁插删，考虑链表；既想局部性又想减少搬移，可以考虑块状链表、Gap Buffer、Rope 等折中结构。

记忆钩子：数组赢在“连续”，链表赢在“重连”；遍历看缓存，插删看是否已知节点。

七、常见误区与追问

• 误区：链表插入删除一定比数组快。 前提是已经知道插入删除位置；如果还要查找，整体可能仍是 O(n)。
• 误区：数组和链表遍历都是 O(n)，所以一样快。 缓存局部性和预取会让数组遍历常数小很多。
• 误区：链表省内存。 节点指针、对象头和分散分配可能让链表更占内存。
• 追问：为什么链表随机访问是 O(n)？ 因为只能沿 next 一个个走，没有下标到地址的直接计算。
• 追问：什么时候链表特别合适？ 哈希表已定位节点后，需要频繁移动或删除节点，比如 LRU。

八、加强记忆

这题要从硬件视角补足复杂度视角：数组连续，缓存一行带来一串元素；链表跳转，下一步地址要读了当前节点才知道。回答时别把链表说成“插删永远快”，要补上“已知节点位置”这个条件，才是成熟答案。