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

Answer 1

ArrayList类是数组的包装类。它包含一个内部数组。

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

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] 访问任何元素，而在链表中，您必须从第一个开始浏览所有列表，直到获得所需的元素。

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

ArrayList的删除时间：访问时间O（n）。LinkedList的删除时间：访问时间O（1）。

ArrayList必须从要删除索引的项开始，将所有元素从数组[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 2

暂时忽略这个答案。其他答案，特别是aix的答案，大多是正确的。从长远来看，它们是投注的方式。如果你有足够的数据（在一台机器上的一个基准测试上，它似乎是大约一百万个条目），ArrayList和LinkedList目前确实可以像广告宣传的那样工作。但是，有一些细节适用于21世纪初。

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

ArrayList的缺点是它在删除后往往会挂在内存空间上，LinkedList在放弃条目时会放弃空间。

数组和 ArrayList 更大的缺点是它们会碎片化可用内存并使垃圾回收器过度工作。随着 ArrayList 的扩展，它会创建新的、更大的数组，将旧数组复制到新数组，并释放旧数组。内存填充了大块连续的可用内存块，这些可用内存块不够大，无法进行下一次分配。最终没有合适的空间进行分配。尽管 90% 的内存是空闲的，但没有一个单独的部分足够大来完成这项工作。GC 会疯狂地移动东西，但如果重新排列空间需要太长时间，它将抛出 OutOfMemoryException。如果它不放弃，它仍然会减慢你的程序速度。

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

LinkedList使用小而精致的内存，GC喜欢它。当你使用99%的可用内存时，它仍然运行良好。

因此，一般来说，对于不太可能删除大部分内容的较小数据集，或者当你对创建和增长有严格控制时，使用ArrayList。（例如，创建一个使用90%内存的ArrayList，并且在程序运行期间不填充它是可以的。持续创建和释放使用10%内存的ArrayList实例会杀死你。）否则，使用LinkedList（或者某种地图，如果你需要随机访问）。如果你有非常大的集合（比如超过100,000个元素），不关心GC，并且计划大量插入和删除，没有随机访问，运行一些基准测试，看看什么是最快的。

Answer 3

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

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

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

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

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

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