ArrayList 和 LinkedList 之间的性能差异

java arraylist doubly-linked-list

2022-08-31 13:28:15

是的，这是一个古老的话题，但我仍然有一些困惑。

在Java中，人们说：

ArrayList比LinkedList更快，如果我随机访问它的元素。我认为随机访问意味着“给我第n个元素”。为什么 ArrayList 更快？

LinkedList 的删除速度比 ArrayList 快。我理解这个。ArrayList 的速度较慢，因为需要重新分配内部备份数组。代码说明：

List<String> list = new ArrayList<String>();
list.add("a");
list.add("b");
list.add("c");
list.remove("b");
System.out.println(list.get(1)); //output "c"

LinkedList的插入速度比ArrayList更快。插入在这里意味着什么？如果这意味着将一些元素移回，然后将元素放在中间的空点，ArrayList应该比LinkedList慢。如果插入仅意味着添加（对象）操作，这怎么会很慢？

答案 1

ArrayList比LinkedList更快，如果我随机访问它的元素。我认为随机访问意味着“给我第n个元素”。为什么 ArrayList 更快？

ArrayList对列表中的每个元素都有直接引用，因此它可以在常量时间内获取第n个元素。必须从头开始遍历列表才能到达第n个元素。LinkedList

LinkedList 的删除速度比 ArrayList 快。我理解这个。ArrayList 的速度较慢，因为需要重新分配内部备份数组。

ArrayList速度较慢，因为它需要复制阵列的一部分才能删除已变为空闲的插槽。如果删除是使用ListIterator.remove（）API完成的，只需要操作几个引用;如果删除是按值或按索引完成的，则必须首先扫描整个列表以查找要删除的元素。LinkedListLinkedList

如果这意味着将一些元素移回，然后将元素放在中间的空点，ArrayList应该更慢。

是的，这就是它的意思。确实比因为它必须在数组中间释放一个插槽而慢。这涉及移动一些引用，并在最坏的情况下重新分配整个阵列。只需要操纵一些引用。ArrayListLinkedListLinkedList

答案 2

暂时忽略这个答案。其他答案，特别是艾克斯的答案，大多是正确的。从长远来看，他们是下注的方式。如果你有足够的数据（在一台机器上的一个基准测试上，它似乎大约是一百万个条目），ArrayList和LinkedList目前确实像广告一样工作。但是，在21世纪初有一些细节适用。

根据我的测试，现代计算机技术似乎给阵列带来了巨大的优势。数组的元素可以以疯狂的速度移动和复制。因此，在大多数实际情况下，数组和 ArrayList 在插入和删除方面的表现通常会显著优于 LinkedList。换句话说，ArrayList将在自己的游戏中击败LinkedList。

ArrayList的缺点是它倾向于在删除后挂在内存空间上，而LinkedList在放弃条目时会放弃空间。

数组和 ArrayList 更大的缺点是它们会占用可用内存，并使垃圾回收器过度工作。当 ArrayList 扩展时，它会创建新的、更大的数组，将旧数组复制到新数组，并释放旧数组。内存填充大的连续可用内存块，这些块不够大，无法进行下一次分配。最终，没有合适的空间用于该分配。即使90%的内存是空闲的，也没有一个单独的部分足够大来完成这项工作。GC将疯狂地移动东西，但是如果重新排列空间需要太长时间，它将抛出一个OutOfMemoryException。如果它不放弃，它仍然会减慢你的程序速度。

最糟糕的是，这个问题很难预测。您的程序将运行正常一次。然后，在可用内存稍少的情况下，在没有警告的情况下，它会变慢或停止。

LinkedList使用小而精致的内存，GC喜欢它。当您使用99%的可用内存时，它仍然运行良好。

因此，一般情况下，将 ArrayList 用于不太可能删除其大部分内容的较小数据集，或者当您严格控制创建和增长时。（例如，创建一个使用90%内存的ArrayList并在程序期间使用它而不填充它是可以的。不断创建和释放使用 10% 内存的 ArrayList 实例将会杀死您。否则，请使用LinkedList（或者如果您需要随机访问，则可以使用某种地图）。如果您有非常大的集合（例如超过100，000个元素），不担心GC，并且计划大量的插入和删除并且没有随机访问，请运行一些基准测试以查看最快的。