Java，添加时间 LinkedList 与 ArrayList

Question

只是将整数添加到Arraylist和Linkedlist，到最后一个位置，为什么在ArrayList中添加比LinkedList更快？我编译了很多很多次，在arraylist中添加速度更快，为什么？

据我所知，ArrayList 将数组复制 2^n+1 大小。而链表只改变节点

class Test1 {

public static void main(String[] args) {

    ArrayList<Integer> arrayList = new ArrayList<>();

    LinkedList<Integer> linkedList = new LinkedList<>();

    addToList(arrayList);

    System.out.println("-----------------");

    addToList(linkedList);

}

public static void addToList(List list) {

    long start = System.currentTimeMillis();

    for (int i = 0; i < 5_000_000; i++) {

        list.add(i);

    }

    long end = System.currentTimeMillis();

    System.out.println(end - start);

}

}

Answer 1

当您添加到 时ArrayList，您只需将整数存储在支持数组中。每隔一段时间，当后备数组填满时，您必须分配一个新数组并将所有旧项目复制到新数组。给定 500 万个整数，您必须执行大约 20 次分配和复制（取决于列表的初始大小）。要添加到链接列表，每次添加都要求您：为新的链表节点分配内存并初始化。将新节点链接到列表的末尾。所有这些额外的工作，对于 theArrayList和 theLinkedList都是通过该方法在幕后完成的add。500 万个链表节点分配和链接的开销高于 500 万个插入的开销，即使您计算了链表填满时必须进行的ArrayList20 次左右的分配和复制操作。ArrayList因此，虽然每个操作都需要常数时间（尽管在这种ArrayList情况下它实际上是摊销常数时间），但附加到链接列表的常数高于附加到ArrayList.

Answer 2

ArrayList不会每次都复制整个数组，而是每次当前数组中没有更多空间时都会创建一个大小加倍的新数组。因此，如果您有ArrayList3 个元素，则底层数组的大小可能为 4。因此，添加新元素不需要创建新数组并复制 3 个值，因此时间复杂度为 O(1)。它们现在都是 O(1)，但ArrayList只需要将值放在内存中的正确位置，而LinkedList需要分配新的空间（为新节点）。