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

Question

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

如前所述 here :

Another benefit of using a LinkedList arise when you add or remove from the head of the list, since those operations are O(1), while they are O(n) for ArrayList.

所以我创建了这个小程序来对其进行基准测试。令我惊讶的是，它反过来了，所以 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

Answer 1

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

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

list.add(0, i);

另见：How do I write a correct micro-benchmark in Java?

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

Why looping an Add operations in LinkedList takes longer than ArrayList?

java

linked-list

arraylist

performance-testing