java - ArrayList 与 ArrayList LinkedList - 插入时间

Question

当我(分别)运行时:

package containers;

import java.util.*;

    public static void main(String[] args) {

    List<Integer> arLst = new ArrayList<Integer>();
    List<Integer> lnLst = new LinkedList<Integer>();

    long start = System.currentTimeMillis();

    for (int i = 0; i < 10000000; i++) {
        arLst.add(i);
    }

    System.out.println("Array list: "+Long.toString(System.currentTimeMillis()-start));

    start = System.currentTimeMillis();

    for (int i = 0; i < 10000000; i++) {
        lnLst.add(i);
    }

    System.out.println("Linked list: "+Long.toString(System.currentTimeMillis()-start));
}

我得到了大致相同的执行时间。我知道 LinkedList 的添加时间应该更快。我想知道为什么......(对于中间插入和最后一个元素都是有意义的 - 因为数组知道在 O(1) 中插入哪里，不像 LinkedList 必须遍历整个列表，我记得)。

Answer 1

两个列表都知道列表末尾在哪里，因此插入时间几乎相同。我预计 LinkedList 会稍微慢一些，因为它为每个元素创建一个节点并使用更多内存。

我明白了

TIntArrayList - 141 ms
ArrayList<Integer> - 810 ms
LinkedList<Integer> - 5190 ms.

TIntArrayList 不会更有效地使用缓存为每个元素创建一个对象。