只是將整數(shù)添加到Arraylist和Linkedlist，到最后一個(gè)位置，為什么在ArrayList中添加比LinkedList更快？我編譯了很多很多次，在arraylist中添加速度更快，為什么？據(jù)我所知，ArrayList 將數(shù)組復(fù)制 2^n+1 大小。而鏈表只改變節(jié)點(diǎn)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貢獻(xiàn)1850條經(jīng)驗(yàn) 獲得超11個(gè)贊
當(dāng)您添加到 時(shí)ArrayList，您只需將整數(shù)存儲(chǔ)在支持?jǐn)?shù)組中。每隔一段時(shí)間，當(dāng)后備數(shù)組填滿時(shí)，您必須分配一個(gè)新數(shù)組并將所有舊項(xiàng)目復(fù)制到新數(shù)組。給定 500 萬(wàn)個(gè)整數(shù)，您必須執(zhí)行大約 20 次分配和復(fù)制（取決于列表的初始大?。?/p>
要添加到鏈接列表，每次添加都要求您：
為新的鏈表節(jié)點(diǎn)分配內(nèi)存并初始化。
將新節(jié)點(diǎn)鏈接到列表的末尾。
所有這些額外的工作，對(duì)于 theArrayList和 theLinkedList都是通過(guò)該方法在幕后完成的add。
500 萬(wàn)個(gè)鏈表節(jié)點(diǎn)分配和鏈接的開銷高于 500 萬(wàn)個(gè)插入的開銷，即使您計(jì)算了鏈表填滿時(shí)必須進(jìn)行的ArrayList20 次左右的分配和復(fù)制操作。ArrayList
因此，雖然每個(gè)操作都需要常數(shù)時(shí)間（盡管在這種ArrayList情況下它實(shí)際上是攤銷常數(shù)時(shí)間），但附加到鏈接列表的常數(shù)高于附加到ArrayList.
波斯汪
TA貢獻(xiàn)1811條經(jīng)驗(yàn) 獲得超4個(gè)贊
ArrayList不會(huì)每次都復(fù)制整個(gè)數(shù)組，而是每次當(dāng)前數(shù)組中沒(méi)有更多空間時(shí)都會(huì)創(chuàng)建一個(gè)大小加倍的新數(shù)組。
因此，如果您有ArrayList3 個(gè)元素，則底層數(shù)組的大小可能為 4。因此，添加新元素不需要?jiǎng)?chuàng)建新數(shù)組并復(fù)制 3 個(gè)值，因此時(shí)間復(fù)雜度為 O(1)。
它們現(xiàn)在都是 O(1)，但ArrayList只需要將值放在內(nèi)存中的正確位置，而LinkedList需要分配新的空間（為新節(jié)點(diǎn)）。
添加回答
舉報(bào)
0/150
提交
取消