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慢.如果插入仅意味着添加(对象)操作,那么这怎么可能很慢？

Answer 1

如果我随机访问其元素,ArrayList比LinkedList更快.我认为随机访问意味着"给我第n个元素".为什么ArrayList更快？

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

LinkedList比ArrayList更快删除.我理解这个.由于需要重新分配内部备份阵列,因此ArrayList较慢.

ArrayList因为它需要复制部分数组才能删除已经空闲的插槽.如果使用ListIterator.remove()API 完成删除,LinkedList只需操作一些引用; 如果删除是通过值或索引完成的,LinkedList则必须首先扫描整个列表以找到要删除的元素.

如果它意味着移回一些元素然后将元素放在中间的空白点,则ArrayList应该更慢.

是的,这就是它的含义.ArrayList确实要慢,LinkedList因为它必须释放阵列中间的一个插槽.这涉及移动一些引用,并在最坏的情况下重新分配整个数组.LinkedList只需要操纵一些参考.

Answer 2

暂时忽略这个答案.其他答案,尤其是aix的答案,大多是正确的.从长远来看,他们是下注的方式.如果你有足够的数据(在一台机器上的一个基准测试,似乎大约有一百万个条目),ArrayList和LinkedList目前可以像广告一样工作.但是,在21世纪初,有一些优点适用.

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

ArrayList的缺点是它会在删除后挂起到内存空间,其中LinkedList在放弃条目时会占用空间.

数组和ArrayList 的更大缺点是它们会碎片释放内存并使垃圾收集器过度工作.随着ArrayList的扩展,它会创建新的更大的数组,将旧数组复制到新数组,并释放旧数组.内存充满了大量连续的可用内存块,这些内存对于下一次分配来说还不够大.最终没有适合该分配的空间.尽管90%的内存都是免费的,但没有一个单独的内容足以完成这项工作.GC会疯狂地移动,但如果重新排列空间需要很长时间,它将抛出OutOfMemoryException.如果它没有放弃,它仍然可以减慢程序的速度.

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

LinkedList使用小而精致的内存,GC喜欢它.当你使用99%的可用内存时它仍然可以正常运行.

因此,通常情况下,将ArrayList用于较小的数据集,这些数据集不可能删除大部分内容,或者您​​可以严格控制创建和增长.(例如,创建一个使用90%内存并使用它而不在程序期间填充它的ArrayList很好.继续创建和释放使用10%内存的ArrayList实例会杀死你.)否则,请使用LinkedList (如果需要随机访问,可以使用某种地图).如果您有非常大的集合(比如超过100,000个元素),不关心GC,并计划大量插入和删除以及无随机访问,请运行一些基准测试以查看最快的内容.

Answer 3

的ArrayList类是用于阵列的包装类.它包含一个内部数组.

public ArrayList<T> {
    private Object[] array;
    private int size;
}

A LinkedList是链表的包装类,具有用于管理数据的内部节点.

public LinkedList<T> {
    class Node<T> {
        T data;
        Node next;
        Node prev;
    }
    private Node<T> first;
    private Node<T> last;
    private int size;
}

注意,本代码用于显示类的可能性,而不是实际的实现.知道实施的可能性,我们可以做进一步的分析:

如果我随机访问其元素,ArrayList比LinkedList更快.我认为随机访问意味着"给我第n个元素".为什么ArrayList更快？

ArrayList的访问时间:O(1).LinkedList的访问时间:O(n).

在数组中,您可以通过使用来访问任何元素array[index],而在链接列表中,您必须从所有列表开始导航,first直到获得所需的元素.

LinkedList比ArrayList更快删除.我理解这个.由于需要重新分配内部备份阵列,因此ArrayList较慢.

ArrayList的删除时间:访问时间+ O(n).LinkedList的删除时间:访问时间+ O(1).

ArrayList中必须的所有元素,从移动array[index]到array[index-1]由项目开始删除索引.LinkedList应该导航到该项目,然后通过将其与列表分离来擦除该节点.

LinkedList比ArrayList更快删除.我理解这个.由于需要重新分配内部备份阵列,因此ArrayList较慢.

ArrayList的插入时间:O(n).LinkedList的插入时间:O(1).

为什么ArrayList可以采用O(n)？因为当您插入新元素并且数组已满时,您需要创建一个具有更大尺寸的新数组(您可以使用类似2*size或3*size/2的公式计算新大小).LinkedList只是在最后一个旁边添加一个新节点.

这种分析不仅适用于Java,还适用于其他编程语言,如C,C++和C#.

更多信息:

• http://en.wikipedia.org/wiki/Array_data_structure
• http://en.wikipedia.org/wiki/Linked_list

Answer 4

对于 ArrayList 和 LinkedList，remove() 和 insert() 的运行时效率均为 O(n)。然而，线性处理时间背后的原因来自两个截然不同的原因：

在 ArrayList 中，您可以在 O(1) 中获取元素，但实际上删除或插入某些内容会使其变为 O(n)，因为后面的所有元素都需要更改。

在 LinkedList 中，实际到达所需元素需要 O(n) 时间，因为我们必须从头开始，直到到达所需索引。一旦我们到达那里，删除或插入是不变的，因为我们只需要更改remove()的1个引用和insert()的2个引用。

两者中哪一个插入和删除速度更快取决于发生的位置。如果我们更接近开头，LinkedList 会更快，因为我们必须遍历相对较少的元素。如果我们更接近末尾，ArrayList 会更快，因为我们在恒定时间内到达那里，只需要更改后面的几个剩余元素。

额外奖励：虽然没有办法使 ArrayList 的这两个方法的复杂度为 O(1)，但实际上有一种方法可以在 LinkedList 中做到这一点。假设我们想要遍历整个列表，以我们的方式删除和插入元素。通常，您会使用 LinkedList 从每个元素的开头开始，我们也可以使用迭代器“保存”我们正在处理的当前元素。在迭代器的帮助下，我们在 LinkedList 中工作时，remove() 和 insert() 的效率为 O(1)。这是我所知道的 LinkedList 总是比 ArrayList 更好的唯一性能优势。