Java，添加时间LinkedList与ArrayList

Question

正如我所知，ArrayList以2^n+1的大小复制数组。而linkedlist只更改节点

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次分配和复制（取决于列表的初始大小）。

若要添加到链表中，每次添加都需要：

1. 为新的链表节点分配内存并初始化。
2. 将新节点链接到列表末尾。