ArrayList和LinkedList之间的性能差异

24 浏览
0 Comments

ArrayList和LinkedList之间的性能差异

这个问题在这里已经有答案了：

在Java中什么时候使用LinkedList而不是ArrayList？

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

在Java中，人们说：

  1. 如果我随机访问其元素，ArrayList比LinkedList更快。我认为随机访问的意思是“给我第n个元素”。为什么ArrayList更快？
  2. 对于删除操作，LinkedList比ArrayList更快。我理解这个。ArrayList更慢，因为需要重新分配内部备份数组。代码解释：

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

  3. 对于插入操作，LinkedList比ArrayList更快。这里的插入是什么意思？如果它意味着移动一些元素并将元素放在中间的空位上，那么ArrayList应该比LinkedList更慢。如果插入只是指add（Object）操作，那么为什么会慢呢？
admin 更改状态以发布 2023年5月24日
0

2 答案

0 Comments

暂时忽略这个答案。其他答案，尤其是 aix 的答案，大多数是正确的。从长远来看，它们是值得赌的方法。如果您拥有足够的数据（在一台机器上的一个基准测试中，它似乎大约是一百万个条目），ArrayList 和 LinkedList 确实像广告宣传的那样工作。然而，在21世纪初有一些细微之处需要注意。

现代计算机技术似乎在数组方面具有巨大优势。数组的元素可以以惊人的速度移动和复制。因此，在大多数实际情况下，数组和 ArrayList 将在插入和删除操作上表现出色，通常是显著的。换句话说，ArrayList 将在 LinkedList 的领域击败它。

ArrayList 的缺点是在删除后它倾向于保留内存空间，而 LinkedList 会随着条目的释放而释放空间。

数组和ArrayList更大的缺点是它们会破坏自由内存并使垃圾收集器过度工作。随着ArrayList扩展，它会创建新的、更大的数组，将旧数组复制到新数组中，并释放旧数组。内存中会填充大块连续的空闲内存，但它们不足以满足下一次分配的需求。最终没有适合分配的空间。即使有90%的内存可用，也没有一个单独的空间足够大来完成任务。垃圾收集器会拼命地移动东西，但如果重新排列空间所需时间太长，它就会抛出OutOfMemoryException。即使它不放弃，它仍然会使程序变得非常慢。

最糟糕的是，这个问题很难预测。你的程序有时候会运行得很好。然后，在可用内存少一点的情况下，没有任何警告，它就会变慢或停止。

LinkedList使用小而精致的内存块，垃圾收集器很喜欢它。即使使用了99%的可用内存，它仍然可以正常运行。

因此，通常对于那些不太可能删除大部分内容的较小数据集，或者在创建和增长方面具有严格控制的情况下，使用ArrayList是可以的。（例如，创建一个使用90%内存的ArrayList，然后在程序运行期间使用它而不填充它是可以的。而连续创建和释放使用10%内存的ArrayList实例将会使你死亡。）否则，使用LinkedList（或某种Map，如果需要随机访问）。如果您有非常大的集合（比如超过100,000个元素），不必担心GC，并且计划进行大量插入和删除操作而没有随机访问，则运行一些基准测试以查看哪个更快。

0
0 Comments

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

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

对于删除操作，LinkedList比ArrayList更快。我理解这个。ArrayList更慢，因为需要重新分配内部备份数组。

ArrayList 更慢是因为它需要复制部分数组以便删除已经空闲的槽位。如果使用 ListIterator.remove() API 进行删除操作，LinkedList 只需操作几个引用；如果通过值或索引进行删除操作，LinkedList 可能需要先扫描整个列表以查找要删除的元素。

如果插入的意思是移动一些元素，然后把元素放在中间的空位上，ArrayList应该更慢。

是的，这就是插入的意思。ArrayList 确实比 LinkedList 更慢，因为它必须在数组中释放出一个中间的空位。这涉及到移动一些引用，最坏的情况下可能需要重新分配整个数组。而 LinkedList 只需操作一些引用。

0