为什么数组的连续内存和缓存局部性很重要？

简化版

数组元素通常连续存放，CPU 读取一个元素时会把相邻一段内存一起加载到 cache，所以顺序遍历数组非常快。链表虽然插删灵活，但节点分散、指针跳转多，缓存命中率通常不如数组。

详细版

数组的 O(1) 随机访问来自地址计算：addr = base + index * element_size。连续内存还带来缓存局部性，例如一次 cache line 读取 64 字节，如果 int 是 4 字节，就可能顺便带进 16 个连续整数。顺序遍历时 CPU 能预取后续数据，减少内存访问等待。

面试里要说清楚：复杂度不是全部。数组和链表都能遍历，时间复杂度都是 O(n)，但数组更容易命中缓存，实际常数更小；这也是很多工程场景偏爱数组、动态数组、紧凑结构的原因。

完整版教学

一、数组为什么能 O(1) 访问

数组的核心特征是同类型元素连续存放。只要知道数组首地址、元素大小和下标，机器就能直接算出目标地址。

addr(a[i]) = base + i * element_size

如果 int 占 4 字节，数组首地址是 1000，那么 a[3] 地址就是 1000 + 3 * 4 = 1012。这个计算不需要从头遍历，所以随机访问是 O(1)。

记忆钩子：数组快，不只是因为下标，还因为下标能直接换成地址。

二、连续内存带来空间紧凑

数组通常只保存元素本身，不需要每个元素额外保存指针。链表节点除了值，还要保存 next，双向链表还要保存 prev。

结构	每个元素额外信息	内存形态
数组	通常没有节点指针	连续紧凑
单链表	1 个 next 指针	分散节点
双链表	prev 和 next	更大节点

假设 64 位系统里指针 8 字节，一个 int 值 4 字节。单链表节点可能至少要 12 字节以上，还会有对象头、对齐和分配器开销。数组则更接近纯数据存储。

三、CPU cache 为什么偏爱数组

内存比 CPU 慢很多，CPU 不会每次只取 4 字节，而是以 cache line 为单位加载一段连续内存。常见 cache line 大小是 64 字节。

1 cache line = 64 bytes
int = 4 bytes
一次加载可能覆盖 16 个 int

遍历数组时，访问 a[0] 后，a[1] 到 a[15] 很可能已经在 cache 里了。链表节点分散在堆上，访问下一个节点要跟着指针跳到未知地址，cache 命中率更差。

这就是“同样 O(n)，数组遍历常常比链表快”的底层原因。

四、预取让顺序访问更快

现代 CPU 会根据访问模式做预取。数组顺序遍历模式很规律：

a[0] -> a[1] -> a[2] -> a[3] -> ...

硬件容易预测你接下来要访问后面的地址，于是提前把数据搬进 cache。链表访问模式是：

nodeA -> nodeX -> nodeM -> nodeQ

下一个地址藏在当前节点的指针里，必须读到当前节点后才知道下一步去哪，预取效果通常差很多。

五、缓存局部性会影响算法选择

面试中很多人只背复杂度：数组插入 O(n)，链表插入 O(1)。这句话只有在“已经拿到节点位置”时才完整。

如果要在第 50000 个位置插入，链表先找位置就要 O(n)，而且遍历过程 cache 不友好。数组虽然移动元素，但移动连续内存可以由底层优化，实际可能并不慢。

操作	数组	链表
顺序遍历	O(n)，缓存友好	O(n)，指针跳转
随机访问	O(1)	O(n)
已知节点后插入	需要搬移	改指针即可
内存占用	紧凑	指针和分配开销

工程上，大量读、多遍历、数据规模适中时，数组经常更占优。

六、连续内存也有代价

数组要求一段连续空间。小数组问题不大，大数组或扩容时就可能需要申请更大的连续区域。

动态数组扩容时会申请新数组并复制旧元素：

old capacity = 1024
new capacity = 1536
copy 1024 elements

所以数组的连续性既是优势，也是约束。它换来了随机访问和缓存友好，但中间插入删除、扩容搬迁、大对象连续分配都要付成本。

七、常见误区与追问

误区：数组和链表遍历都是 O(n)，实际速度一定差不多。 复杂度相同不代表常数相同，数组缓存局部性通常更好。
误区：链表插入一定比数组快。 如果没有现成节点位置，链表找位置仍要 O(n)，且缓存不友好。
误区：数组连续内存只有随机访问一个好处。 它还带来空间紧凑、cache line 命中和预取优势。
追问：cache line 对数组有什么影响？ 一次加载相邻多个元素，顺序遍历时后续元素更可能已在 cache 中。
追问：数组为什么适合批量计算？ 地址规律、数据紧凑，CPU 预取和向量化优化更容易发挥作用。
追问：连续内存有什么坏处？ 扩容需要搬迁，大数组需要连续空间，中间插删要移动元素。

八、加强记忆

数组的性能要从“地址公式 + 缓存局部性”一起记。base + i * size 让随机访问 O(1)，连续内存让 cache line 一次带入多个相邻元素，顺序遍历和批量计算都很舒服。链表的优势是局部改指针，但节点分散、指针多、cache 不友好，所以面试时不要只比较大 O，还要说实际常数和内存布局。

简化版

详细版