ArrayList与LinkedList在随机索引中插入项目时的对比？[副本]

Question

代码所做的是创建数组和链表，并为每个元素提供一个开始。然后，AddMoreItems(list 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会稍微快一些）。但是，实际的结果似乎表明，ArrayList比链表快得多，而不管您添加的元素数量如何（您可以在这里尝试一下）。

无论如何，我的猜测是，这可能与缓存有关，而且LinkedList将为插入的每个单独元素分配内存，而ArrayList将分配内存块以减少分配次数。

Answer 1

你的期望是不正确的。ArrayListJavadoc显式地表示（部分）¹

add操作以摊销常数时间运行，也就是说，添加n个元素需要O(n)个时间。所有其他操作都在线性时间内运行（粗略地说）。与LinkedList实现相比，常数因子较低。

由于常数系数较高，在LinkedList上的每个Add操作都比在ArrayList上的操作稍慢，因此您应该期望ArrayList更快。