使用LinkedList或ArrayList进行迭代

Question

如果我要向List中添加未知数量的元素,并且该列表只会被迭代,那么LinkedList会比特定实例中的ArrayList更好(使用Java,如果它有任何相关性)

Answer 1

之间的性能权衡ArrayList,并LinkedList进行了讨论之前,但在短:ArrayList往往是大多数真实的使用场景更快.ArrayList将导致更少的内存碎片并且将更好地使用垃圾收集器,它将消耗更少的内存并允许更快的迭代,并且对于在列表末尾发生的插入将更快.

因此,只要列表中的插入始终出现在最后一个位置,就没有理由选择LinkedList- ArrayList是明显的赢家.

Answer 2

好的，已经回答了，但我仍然会尝试提出我的观点。 ArrayList迭代速度比 快LinkedList。原因是一样的，因为它arrayList是由一个数组支持的。让我们尝试了解为什么数组迭代会更快linkedList。

有两个因素对其起作用

• 数组存储为contiguous memory locations（你可以说
  什么？）
• 系统缓存比访问内存快得多

但是你可以问 Cache 是如何适应这里的。在这里检查一下，CPU 尝试通过将数据存储在缓存中来利用缓存。它使用Locality of refrence。现在有 2 种技术是

参考参考位置

时间局部性 如果在某一时刻引用了特定的内存位置，则很可能在不久的将来再次引用相同的位置。对同一内存位置的相邻引用之间存在时间上的接近性。在这种情况下，通常会努力将引用数据的副本存储在可以更快访问的特殊内存中。时间局部性是空间局部性的一种特殊情况，即当预期位置与当前位置相同时。

空间局部性 如果在特定时间引用特定存储位置，则很可能在不久的将来会引用附近的内存位置。在这种情况下，通常会尝试猜测当前参考周围区域的大小和形状，因此值得准备更快的访问。

因此，如果一次访问一个数组位置，它也会在缓存中加载相邻的内存位置。但是等待它不会加载所有。这取决于CACHE_LINES。很好地CACHE_LINES定义一次可以在缓存中加载多少位。

所以在进一步潜水之前，不要提醒我们所知道的

• 数组是 contiguous memory locations
• 当数组的一个内存位置被相邻访问时也加载到内存中
• 内存中加载多少数组内存位置由CACHE-LINES容量定义

因此，每当 CPU 尝试访问内存位置时，它都会检查该内存是否已经在缓存中。如果它存在它匹配其他它的cache miss.

因此，从我们在阵的情况下，知道会有少cache_miss相比，random memory locations在linked list。所以这是有道理的

最后从这里Array_data_structure 来自维基百科它说

在元素大小为 k 的数组和缓存行大小为 B 字节的机器上，迭代包含 n 个元素的数组需要最少的天花板 (nk/B) 缓存未命中，因为其元素占据连续的内存位置。这大约比访问随机内存位置的 n 个元素所需的缓存未命中数好 B/k 倍。因此，数组上的顺序迭代在实践中明显比在许多其他数据结构上的迭代快，这个属性称为局部性

我想这回答了你的问题。