ArrayList与LinkedList的缓存局部性对比及性能影响问询

嘿，这个问题问得特别到位，很多刚摸Java集合的开发者都会有这个困惑——既然两种列表存的都是对象引用，为啥总说ArrayList在缓存局部性上更占优势呢？咱们掰开揉碎了说：

核心差异：内存布局完全不同 #

首先得搞清楚两种集合底层的内存存储逻辑：

• ArrayList：底层是一块连续的数组，数组里的每个元素都是指向实际对象的引用。这些引用在内存中是紧密排列的，占着一整块连续的内存区域。
• LinkedList：底层是双向链表，每个元素都被封装在一个Node对象里。这些Node对象在堆内存中是分散存放的，彼此之间只能靠prev和next这两个引用来关联，完全没有内存连续性可言。

缓存局部性到底在起什么作用？ #

CPU的高速缓存（L1/L2/L3）有个核心特性叫空间局部性：当程序访问某一块内存地址时，CPU会自动把这块地址周围的连续内存块预加载到缓存里——因为程序通常会倾向于连续访问相邻的数据，这样能大大减少从慢得多的主存中读取数据的次数。

对应到两种列表的性能表现 #

咱们拿最常见的遍历场景举例：

• 遍历ArrayList时，当你读取第一个元素的引用，CPU会把数组里后续的几个引用一起加载到缓存里。接下来访问下一个元素时，直接从缓存里取引用就行，速度快到飞起。哪怕实际对象在堆里是分散的，至少获取引用这一步是缓存友好的，能省掉大量主存访问的开销。
• 遍历LinkedList时，情况就完全不一样了：你拿到一个Node的引用后，下一个Node的内存地址是完全随机的，根本不在当前预加载的缓存块里。CPU每次都得从主存重新加载新的Node对象，这就是所谓的缓存未命中——每次未命中都会带来明显的性能损耗，毕竟主存的访问速度比缓存慢了好几个数量级。

解答你的核心疑问 #

你提到“访问元素都需要跳转到随机内存”，其实这里有个细节：
没错，最终访问实际对象的时候，确实可能是随机内存地址，但ArrayList赢在了引用本身的连续性。LinkedList不仅访问实际对象是随机的，就连获取下一个节点的引用这一步，都得跳去一个完全不连续的内存地址，相当于双重的随机访问；而ArrayList在获取引用这一步是连续的，缓存能帮上大忙，大大减少了主存访问的次数。

举个实际的例子：遍历一个包含10万元素的列表，ArrayList的遍历速度往往是LinkedList的3-5倍，核心原因就是缓存局部性带来的差异。

备注：内容来源于stack exchange，提问作者Marat Tim