假设我们有一个未排序的数组和链表。为两种数据结构搜索元素时最坏的情况是 O( n (，但我的问题是：
由于在缓存中使用了空间局部性，数组是否仍然更快，或者缓存是否会利用分支局部性允许链表与任何数组一样快？
我对数组的理解是，如果访问了一个元素，那么该内存块和许多周围的块就会被带入缓存中，从而允许更快的内存访问。
我对链表的理解是，由于遍历列表的路径是可预测的，因此缓存将利用该路径并仍然存储适当的内存块，即使列表的节点在堆中可能相距很远。
您对数组情况的理解大多是正确的。 如果按顺序访问数组，许多处理器不仅会获取包含该元素的块，还会预取后续块，以最大程度地减少等待缓存未命中所花费的周期。 如果您使用的是英特尔 x86 处理器，您可以在英特尔 x86 优化手册中找到有关此内容的详细信息。 此外，如果数组元素足够小，则加载包含元素的块意味着下一个元素可能位于同一块中。
不幸的是，对于链表，从处理器的角度来看，负载模式是不可预测的。 它不知道在地址 X 处加载元素时，下一个地址是 (X + 8( 的内容。
举个具体的例子，顺序阵列访问的加载地址序列很好，而且是可预测的。例如，1000、1016、1032、1064 等。
对于链表，它看起来像：1000、3048、5040、7888 等 很难预测下一个地址。