所以我偶然发现了这段代码，并特别想知道为什么java.util.ArrayList比java.util.LinkedList显着地更快。

代码要做的是创建一个数组和一个链表，并为每个表提供一个元素。 addmoreItems(List<Integer> vals)将同时在两个数组中运行，并且每个数组将在数组中的某个随机索引处插入一个随机值。它将添加到每个数组的值的数量取决于用户的输入。

private static int amount = 0;

public static void main(String[] args) {

    Scanner scan = new Scanner(System.in);
    System.out.print("Enter amount of elements to add: ");
    amount = scan.nextInt();

    LinkedList<Integer> linked = new LinkedList<Integer>();
    ArrayList<Integer> array = new ArrayList<Integer>();

    linked.add(0);
    array.add(0);

    // Bench mark linked list speed
    long start = System.nanoTime();
    addmoreItems(linked);
    long end = System.nanoTime() - start;

    // Bench mark array list speed
    long start2 = System.nanoTime();
    addmoreItems(array);
    long end2 = System.nanoTime() - start2;

    System.out.println("Linked list took: " + (end / 1000000.0) + "ms");
    System.out.println("Array list took: " + (end2 / 1000000.0) + "ms");

}

public static void addmoreItems(List<Integer> vals) {

    Random r = new Random();

    for (int i = 0; i < amount; i++)
        vals.add(r.nextInt(vals.size()),r.nextInt());

}

因此，从根本上讲，人们会认为addmoreItems()函数将花费相同的时间返回两种列表类型（也许LinkedList会稍快一些）。但是， actual 的结果似乎表明ArrayList的速度明显快于链接列表，而不考虑要添加的元素数量（you can try it out here）。

无论如何，我的猜测是可能与缓存有关，也许与LinkedList会为插入的每个元素分配内存这一事实有关，而ArrayList会分配内存块减少分配数量。

为什么ArrayList更快？