时间戳

首页 > 解决方案 > 为什么在 LinkedList 中循环添加操作比 ArrayList 需要更长的时间？

java - 为什么在 LinkedList 中循环添加操作比 ArrayList 需要更长的时间？

问题描述

所以我知道当主要操作是不需要复制空槽用完的数组时，它LinkedList应该快得多（与 相比）。ArrayListadd

如此处所述：

当您从列表的头部添加或删除时，使用 LinkedList 的另一个好处是，因为这些操作是 O(1)，而对于 ArrayList，它们是 O(n)。

所以我创建了这个小程序来对其进行基准测试。令我惊讶的是，它反过来了，所以ArrayList更快。这似乎违反直觉。

我不确定我在这里缺少什么：

    public static void main(String[] args) {

    for (int i = 1000; i < 100000000; i *=5) {
        System.out.println(" - - - - ");
        System.out.println("size " + NumberFormat.getNumberInstance(Locale.US).format(i));
        List<Integer> list = new ArrayList<>();
        populateList(list, i);
        list = null;

        List<Integer>list2 = new LinkedList<>();
        populateList(list2, i);
    }

}

private static void populateList(List<Integer> list, long size) {
    long start = System.currentTimeMillis();
    for (int i = 0; i < size; i++) {
        list.add(i);
    }
    long after = System.currentTimeMillis();
    System.out.println(list.getClass().getCanonicalName() + " Diff: " + (after - start));
}

输出是：

大小 1,000

java.util.ArrayList 差异：0

java.util.LinkedList 差异：0

大小 5,000

java.util.ArrayList 差异：1

java.util.LinkedList 差异：0

大小 25,000

java.util.ArrayList 差异：3

java.util.LinkedList 差异：2

规模 125,000

java.util.ArrayList 差异：5

java.util.LinkedList 差异：4

规模 625,000

java.util.ArrayList 差异：20

java.util.LinkedList 差异：13

规模 3,125,000

java.util.ArrayList 差异：104

java.util.LinkedList 差异：1254

规模 15,625,000

java.util.ArrayList 差异：3274

java.util.LinkedList 差异：4490

规模 78,125,000

java.util.ArrayList 差异：14457

java.util.LinkedList 差异：88370

标签： javaarraylistlinked-listperformance-testing

解决方案

您将插入到列表的末尾，ArrayList因为LinkedList 实现是一个双向链表，它也有一个尾指针LinkedList。O(1)

要在头部插入，也要传递索引。

list.add(0, i);

另请参阅：如何在 Java 中编写正确的微基准测试？

推荐阅读