ArrayList和LinkedList之间的性能差异

Question

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

在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慢。如果插入仅意味着add（Object）操作，这怎么会慢呢？

Answer 1

如果我随机访问它的元素，ArrayList比LinkedList快。我认为随机访问的意思是“给我第n个元素”。为什么ArrayList更快？ArrayList具有对列表中每个元素的直接引用，因此可以在恒定时间内获得第n个元素。LinkedList必须从头开始遍历列表才能到达第n个元素。LinkedList的删除速度比ArrayList快。我明白这一点。ArrayList的速度较慢，因为需要重新分配内部备份阵列。ArrayList速度较慢，因为它需要复制阵列的一部分才能删除空闲的插槽。如果删除是使用ListIterator.remove()API 完成的，则LinkedList只需操纵几个引用即可；如果删除是按值或按索引完成的，则LinkedList必须先扫描整个列表以找到要删除的元素。如果这意味着将某些元素移回，然后将其放在中间的空白位置，则ArrayList应该更慢。是的，这就是这个意思。ArrayList确实比LinkedList由于必须在阵列中间释放一个插槽要慢。这涉及到移动一些引用，最坏的情况是重新分配整个数组。LinkedList只需操纵一些引用。