为什么在LinkedList中循环添加操作比ArrayList要长？

Question

我不知道我错过了什么：

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

输出结果是：

尺码1000

尺码25,000

ArrayList差异：3

LinkedList差异：2

尺码3,125,000

ArrayList差异：104

LinkedList差异：1254

Answer 1

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

若要在头部插入，请同时传递索引。

list.add(0, i);

另请参见：如何用Java编写正确的微基准测试？