java - ArrayList 和 LinkedList 之间的性能差异

Question

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

在 Java 中，人们说:

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

2. 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"
   

3. LinkedList 的插入速度比 ArrayList 快。这里的插入是什么意思？如果是指将一些元素往回移动，然后将元素放在中间的空白处，ArrayList 应该比 LinkedList 慢。如果插入只意味着一个 add(Object) 操作，这怎么可能慢？

Answer 1

ArrayList is faster than LinkedList if I randomly access its elements. I think random access means "give me the nth element". Why ArrayList is faster?

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

LinkedList is faster than ArrayList for deletion. I understand this one. ArrayList's slower since the internal backing-up array needs to be reallocated.

ArrayList 较慢，因为它需要复制数组的一部分才能删除已空闲的插槽。如果删除是使用 ListIterator.remove() API，LinkedList 只需要操作几个引用；如果删除是按值或按索引完成的，LinkedList 必须先扫描整个列表以找到要删除的元素。

If it means move some elements back and then put the element in the middle empty spot, ArrayList should be slower.

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