ArrayList和LinkedList之间的性能差异

https://stackoverflow.com//questions/10656471

11-12-2019
|

题

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

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

解决方案

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

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

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

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

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

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

其他提示

现在忽略这个答案。其他答案，特别是 AIX 的答案大多是正确的。长期来说，他们是赌注的方式。如果您有足够的数据（在一台机器上的一个基准上，它似乎是大约一百万条目）ArrayList和LinkedList当前正常工作。但是，在21世纪初，存在一些适用的精细点。

现代计算机技术似乎通过我的测试，为阵列提供巨大的边缘。阵列的元素可以在疯狂速度下移位并复制。作为结果阵列和ArrayList将在大多数实际情况下，往往略微显着地倾向于插入和删除的LinkedList。换句话说，ArrayList将在自己的游戏中击败LinkedList。

ArrayList的缺点是在删除后倾向于挂在内存空间上，其中LinkedList放弃了空间，因为它放弃了条目。

更大阵列和arraylist的缺点是它们碎片免费内存和过度劳动垃圾收集器。随着ArrayList扩展，它会创建新的更大数组，将旧阵列复制到新的阵列，并释放旧的阵列。内存填充了大型连续内存的免费内存，这不足以下一个分配。最终没有适当的分配空间。即使90％的内存是免费的，也没有个别件，足以做这项工作。 GC将疯狂地致力于移动事物，但如果需要太长以重新排列空间，它将抛出outofMemoryException。如果它没有放弃，它仍然可以减慢你的节目方式。

最糟糕的是这个问题可能很难预测。您的程序将一次运行很好。然后，具有较少的内存可用，没有警告，它会减慢或停止。

linkedlist使用小的，精致的记忆和gc的爱。当您使用99％的可用内存时，它仍然很好。

一般来说，使用ArrayList用于较小的数据集，这些数据不太可能删除其大部分内容，或者当您有严格控制创建和增长时。（例如，创建一个ArrayList，它使用90％的内存并在程序持续时间内使用它很好。不断创建和释放使用10％内存的ArrayList实例将杀死您。）否则，请与LinkedList一起使用（或者某种程序的地图如果需要随机访问）。如果您有非常大的集合（比如超过10,000元素），对GC没有担忧，并计划大量插入和删除以及没有随机访问，运行几个基准，以查看最快的基准。

该 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＃等其他编程语言中。

更多信息在这里:

remove（）和插入（）对于arraylist和linkedlists都有o（n）的运行时效率。然而，线性处理时间背后的原因来自两个不同的原因：

在ArrayList中，您将在O（1）中的元素中，但实际删除或插入某些内容使其成为O（n），因为需要更改所有以下元素。

在LinkedList中它需要O（n），以实际到达所需的元素，因为我们必须从一开始就开始，直到我们达到所需的索引。一旦我们到达那里，删除或插入是常量，因为我们只需要更改remove（）和2个引用的1个参考Insert（）。

插入和删除的哪一个更快地取决于它发生的位置。如果我们更接近开始，LinkedList将更快，因为我们必须经历相对较少的元素。如果我们更接近结束，ArrayList将更快，因为我们在不断的时间内到达那里，只需更改剩下的剩余元素。

奖金：虽然没有办法使这两种方法为ArrayList进行o（1），但实际上是在LinkedLists中执行此操作的方法。让我们说我们希望通过整个列表删除和插入元素。通常，您将从使用LinkedList开始的每个元素的开始，我们也可以“保存”当前元素，我们正在使用迭代器。在迭代器的帮助下，我们在LinkedList中工作时，可以获得删除（）和插入（）的o（1）效率。唯一一个唯一的性能受益，我知道LinkedList总是比ArrayList更好的位置。

arraylist

如果我们的频繁操作是检索操作，
ArrayList是最佳选择。如果我们的操作在中间插入和删除，则
ArrayList是最糟糕的选择，因为在内部执行了多个换档操作。
在ArrayList元素中将存储在连续的存储器位置，因此检索操作将变得容易。
linkedlist： -

LinkedList是最佳选择，如果我们的频繁操作在中间插入和删除。
linkedlist是最糟糕的选择是我们的频繁操作是检索操作。
在linkedlist中，元素将不会存储在连续存储器位置中，因此检索操作将是复杂的。
现在来临你的问题： -
1）ArrayList根据索引节省数据，它实现了WornalAccess接口，该接口是一个标记接口，它为ArrayList提供了随机检索的能力，但LinkedList不会实现RandalAccess接口，这就是ArrayList的速度而不是LinkedList的速度。
2）LinkedList的底层数据结构是双链接列表，因此在LinkedList中，中间插入和删除非常容易，因为它不必像ArrayList一样移动每个删除和插入操作的每个元素和每个元素（如果我们的操作在中间插入和删除，则不建议在中间删除时，因此执行了几个换档操作）。
source

回答1：ArrayList在引擎盖下使用数组。访问ArrayList对象的成员就像在提供的索引处访问阵列一样简单，假设索引位于备份阵列的范围内。LinkedList必须通过其成员迭代到第n个元素。那个LinkedList的O（n），与ArrayList的O（1）。

在LinkedList中，元素在它之前和之后对元素引用。在ArrayList中，数据结构只是一个数组。

linkedlist需要迭代n个元素以获取第n个元素。ArrayList只需要返回备份阵列的元素n。
备份阵列需要重新分配用于新大小，并且在删除元素需要移动以填充空白区域后复制或每个元素复制的数组。一个LinkedList只需要在删除到删除的元素之前删除到删除到一个元素之前的元素之前的元素上的先前引用更长的是解释，但更快地做到。
与此处删除的原因相同。

arraylist ：arraylist具有与数组类似的结构，它可以直接引用每个元素。所以Rendom Access在ArrayList中快速。

linkedlist ：在linkedlist中获取nth elewht，您必须遍历整个列表，与ArrayList相比需要时间。每个元素都有一个链接到其上一个和巢元素，因此删除快速。

arraylist： arraylist类扩展了抽象列表并实现了列表界面和randomAscess（标记界面）。ArrayList支持可根据需要生长的动态阵列。它给我们首先迭代元素。

linkedlist： linkedlist按索引位置（如arraylist）命令，除了元素彼此双链接。此链接为您提供新的方法（超出列表界面的内容）以从开头或结尾添加和删除，这使其成为实现堆栈或队列的简单选择。请记住，LinkedList可能比ArrayList更慢，，但是当您需要快速插入和删除时，它是一个不错的选择。作为Java 5，LinkedList类已经增强以实现Java。util.queue界面。因此，它现在支持常见的队列方法：peek（），poll（）和优惠（）。

我想给她补充一条关于性能差异的额外信息。

我们已经知道，由于这样的事实， ArrayList 实施由一个 Object[] 它支持随机访问和动态调整大小和 LinkedList 实现使用对head和tail的引用来导航它。它没有随机访问功能，但它也支持动态调整大小。

第一件事是，使用ArrayList，您可以立即访问索引，而使用LinkedList，则可以遍历对象链。

其次，插入ArrayList通常较慢，因为一旦你达到它的边界，它就必须增长。它将不得不创建一个新的更大的数组，并从原始数组中复制数据。

但是 有趣的事情 那是你的时候吗？ 创建一个已经足够庞大的ArrayList 为了适应所有插入，它显然不会涉及任何数组复制操作。添加到它将比LinkedList更快，因为LinkedList将不得不处理它的指针，而巨大的ArrayList只是在给定的索引处设置值。

查看更多 ArrayList和LinkedList的区别.

即使它们似乎相同（相同的实现Inteface列表 - 非线程安全），它们在添加/删除和搜索时间和消费内存中的性能方面给出不同的结果（LinkedList更多）。如果您使用具有性能O（1）的高度插入/删除，可以使用

linkedlists。如果您使用具有性能O（1）的直接访问操作，可以使用ArrayLists

此代码可以清楚这些评论，您可以尝试了解性能结果。（对不起锅炉板代码）

public class Test {

    private static Random rnd;


    static {
        rnd = new Random();
    }


    static List<String> testArrayList;
    static List<String> testLinkedList;
    public static final int COUNT_OBJ = 2000000;

    public static void main(String[] args) {
        testArrayList = new ArrayList<>();
        testLinkedList = new LinkedList<>();

        insertSomeDummyData(testLinkedList);
        insertSomeDummyData(testArrayList);

        checkInsertionPerformance(testLinkedList);  //O(1)
        checkInsertionPerformance(testArrayList);   //O(1) -> O(n)

        checkPerformanceForFinding(testArrayList);  // O(1)
        checkPerformanceForFinding(testLinkedList); // O(n)

    }


    public static void insertSomeDummyData(List<String> list) {
        for (int i = COUNT_OBJ; i-- > 0; ) {
            list.add(new String("" + i));
        }
    }

    public static void checkInsertionPerformance(List<String> list) {

        long startTime, finishedTime;
        startTime = System.currentTimeMillis();
        int rndIndex;
        for (int i = 200; i-- > 0; ) {
            rndIndex = rnd.nextInt(100000);
            list.add(rndIndex, "test");
        }
        finishedTime = System.currentTimeMillis();
        System.out.println(String.format("%s time passed at insertion:%d", list.getClass().getSimpleName(), (finishedTime - startTime)));
    }

    public static void checkPerformanceForFinding(List<String> list) {

        long startTime, finishedTime;
        startTime = System.currentTimeMillis();
        int rndIndex;
        for (int i = 200; i-- > 0; ) {
            rndIndex = rnd.nextInt(100000);
            list.get(rndIndex);
        }
        finishedTime = System.currentTimeMillis();
        System.out.println(String.format("%s time passed at searching:%d", list.getClass().getSimpleName(), (finishedTime - startTime)));

    }

}

许可以下： CC-BY-SA 和归因

不隶属于 StackOverflow