68

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

在 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 慢。如果插入只意味着一个 add(Object) 操作，这怎么可能慢？

4

11 回答 11

76

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

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

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

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

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

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

于 2012-05-18T16:38:21.280 回答
34

暂时忽略这个答案。其他答案，尤其是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，并且计划大量插入和删除并且没有随机访问，请运行一些基准测试以查看最快的。

于 2012-05-18T18:00:05.430 回答
16

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

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

ALinkedList是链表的包装类，具有用于管理数据的内部节点。

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

更多信息在这里：

于 2012-05-18T17:09:03.543 回答
5

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

在 ArrayList 中，您可以在 O(1) 中找到元素，但实际上删除或插入某些内容会使它成为 O(n)，因为需要更改以下所有元素。

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

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

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

于 2016-06-11T20:29:17.300 回答
4

数组列表

  • 如果我们的频繁操作是检索操作，ArrayList 是最好的选择。
  • 如果我们的操作是在中间插入和删除，ArrayList 是最糟糕的选择，因为在内部执行了几个移位操作。
  • 在 ArrayList 中，元素将存储在连续的内存位置，因此检索操作将变得容易。

链表：-

  • 如果我们的频繁操作是中间的插入和删除，LinkedList是最好的选择。
  • LinkedList 是最差的选择是我们的频繁操作是检索操作。
  • 在 LinkedList 中，元素不会存储在连续的内存位置，因此检索操作会很复杂。

现在来回答你的问题：-

1) ArrayList 根据索引保存数据，它实现了 RandomAccess 接口，这是一个标记接口，它提供了对 ArrayList 进行随机检索的能力，但 LinkedList 没有实现 RandomAccess 接口，这就是 ArrayList 比 LinkedList 快的原因。

2) LinkedList 的底层数据结构是双向链表，因此在 LinkedList 中的中间插入和删除非常容易，因为它不必像 ArrayList 那样每次删除和插入操作都移动每个元素（即如果我们的操作是中间的插入和删除，不建议这样做，因为内部执行了几次移位操作）。
资源

于 2019-04-06T18:07:04.397 回答
1

对 1 的回答：ArrayList 在后台使用一个数组。访问 ArrayList 对象的成员就像访问提供的索引处的数组一样简单，假设索引在后备数组的范围内。LinkedList 必须遍历其成员才能到达第 n 个元素。LinkedList 是 O(n)，而 ArrayList 是 O(1)。

于 2012-05-18T16:39:13.513 回答
1

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

  1. LinkedList 需要遍历 N 个元素才能获得第 N 个元素。ArrayList 只需要返回后备数组的元素 N。

  2. 需要为新大小重新分配后备数组，并复制该数组，或者需要向上移动删除元素之后的每个元素以填充空白空间。LinkedList 只需要将删除后元素的上一个引用设置为删除之前的元素，并将删除元素之前的元素的下一个引用设置为删除元素之后的元素。解释时间更长，但做起来更快。

  3. 与此处删除的原因相同。

于 2012-05-18T16:43:30.473 回答
1

我想添加一条关于性能差异的额外信息。

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

首先，使用 ArrayList，您可以立即访问索引，而使用 LinkedList，您可以遍历对象链。

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

但有趣的是，当您创建一个已经足够大以容纳所有插入的 ArrayList 时，它显然不会涉及任何数组复制操作。添加到它会比使用 LinkedList 更快，因为 LinkedList 必须处理它的指针，而巨大的 ArrayList 只是在给定索引处设置值。

在此处输入图像描述

查看更多ArrayList 和 LinkedList 的区别。

于 2019-06-18T15:45:19.137 回答
0

ArrayList : ArrayList 有一个类似数组的结构，它直接引用每个元素。所以 ArrayList 中的随机访问速度很快。

LinkedList：在 LinkedList 中，为了获取第 n 个元素，您必须遍历整个列表，与 ArrayList 相比需要时间。每个元素都有一个指向其前一个 & 嵌套元素的链接，因此删除速度很快。

于 2013-04-17T07:12:56.397 回答
0

ArrayList： ArrayList 类扩展了 AbstractList 并实现了 List 接口和 RandomAccess（标记接口）。ArrayList 支持可以根据需要增长的动态数组。它给了我们对元素的第一次迭代。

LinkedList： LinkedList 是按索引位置排序的，就像 ArrayList 一样，只是元素之间是双向链接的。此链接为您提供了从头或尾添加和删除的新方法（超出您从 List 接口获得的方法），这使其成为实现堆栈或队列的简单选择。请记住，LinkedList 的迭代速度可能比 ArrayList 慢，但是当您需要快速插入和删除时，它是一个不错的选择。从 Java 5 开始，LinkedList 类已得到增强，可以实现 java.util.Queue 接口。因此，它现在支持常见的队列方法：peek()、poll() 和 offer()。

于 2013-11-20T10:22:24.203 回答
-1

即使它们看起来相同（相同的实现接口列表 - 非线程安全），它们在添加/删除和搜索时间和消耗内存的性能方面给出不同的结果（LinkedList 消耗更多）。

如果您使用性能 O(1) 的高度插入/删除，则可以使用 LinkedLists。如果您使用性能 O(1) 的直接访问操作，则可以使用 ArrayList

此代码可能会清除这些注释，您可以尝试了解性能结果。（对不起样板代码）

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)));

    }

}
于 2016-02-05T08:40:28.000 回答