ArrayList和LinkedList之间的性能差异

Question

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

在爪哇，人们说：

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慢。如果插入只意味着添加（对象）操作，这怎么会慢呢？

Answer 1

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

ArrayList直接引用列表中的每个元素，因此可以在恒定时间内获得第n个元素。LinkedList必须从头遍历列表，才能找到第n个元素。

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

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

如果这意味着向后移动一些元素，然后将元素放在中间的空点，那么ArrayList应该会慢一些。

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