只是將整數添加到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);}}
2 回答
慕蓋茨4494581
TA貢獻1850條經驗 獲得超11個贊
當您添加到 時ArrayList，您只需將整數存儲在支持數組中。每隔一段時間，當后備數組填滿時，您必須分配一個新數組并將所有舊項目復制到新數組。給定 500 萬個整數，您必須執行大約 20 次分配和復制（取決于列表的初始大小）。
要添加到鏈接列表，每次添加都要求您：
為新的鏈表節點分配內存并初始化。
將新節點鏈接到列表的末尾。
所有這些額外的工作，對于 theArrayList和 theLinkedList都是通過該方法在幕后完成的add。
500 萬個鏈表節點分配和鏈接的開銷高于 500 萬個插入的開銷，即使您計算了鏈表填滿時必須進行的ArrayList20 次左右的分配和復制操作。ArrayList
因此，雖然每個操作都需要常數時間（盡管在這種ArrayList情況下它實際上是攤銷常數時間），但附加到鏈接列表的常數高于附加到ArrayList.
波斯汪
TA貢獻1811條經驗 獲得超4個贊
ArrayList不會每次都復制整個數組，而是每次當前數組中沒有更多空間時都會創建一個大小加倍的新數組。
因此，如果您有ArrayList3 個元素，則底層數組的大小可能為 4。因此，添加新元素不需要創建新數組并復制 3 個值，因此時間復雜度為 O(1)。
它們現在都是 O(1)，但ArrayList只需要將值放在內存中的正確位置，而LinkedList需要分配新的空間（為新節點）。
添加回答
舉報
0/150
提交
取消