ArrayList vs LinkedList從內存分配的角度來看

我需要存儲大量的信息，比如說'名稱'在java List中。項目的數量可以改變（或者簡而言之，我不能預先確定尺寸）。我認爲，從內存分配的角度來看，LinkedList將是一個比ArrayList更好的選擇，對於ArrayList，一旦達到最大大小，內存分配會自動增加一倍，因此總會有分配更多內存的機會需要什麼。ArrayList vs LinkedList從內存分配的角度來看

我從這裏的其他帖子瞭解到，存儲在LinkedList中的單個元素比ArrayList需要更多空間，因爲LinkedList也需要存儲節點信息，但我仍然猜測我定義的LinkedList可能是更好的選擇。另外，我不想進入性能方面（取回，刪除等），這已經討論過了。

來源

2012-07-19 BP_EV

這似乎你已經有你的答案。鏈接列表會更好，因爲當達到最大值時它的大小不會加倍。可以說你有251個名字，然後當你達到250時，數組翻倍增加到500。然後，你在內存中分配了249個額外的空白點。基本上我想說的就是長期來說，Link-List> ArrayList就像內存一樣。 – 2012-07-19 15:43:53

@Eric Robinson：以下來自其他用戶的評論證明我的理解不正確。您也可以注意這一點。謝謝.. – 2012-07-19 21:45:57

看到這個答案的內存足跡視覺的兩個：http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist/7671021#7671021 – Numeron 2013-01-23 03:39:12

LinkedList可能會分配更少的條目，但這些條目比ArrayList的天文價格要高 - 就內存而言，即使是最差的情況下也是如此。

（僅供參考，我想你弄錯了; ArrayList增長以1.5時，它的全部，而不是2個。）

見例如http://code.google.com/p/memory-measurer/wiki/ElementCostInDataStructures：LinkedList每個元素消耗24個字節，而ArrayList最好消耗每個元素4個字節，最壞情況消耗每個元素6個字節。（結果可能會有所不同，具體取決於32位與64位JVM以及壓縮對象指針選項，但在那些比較中，LinkedList的成本至少爲36字節/元，並且ArrayList最多爲8，最差爲12。）

UPDATE：

我從其他職位明白這裏存儲在一個LinkedList各個元素需要比一個ArrayList更多的空間的LinkedList還需要存儲節點的信息，但我還在猜測的場景我已經定義LinkedList可能是一個更好的選擇。另外，我不想進入性能方面（取回，刪除等），這已經討論過了。

爲了清楚，即使在最壞的情況下，ArrayList爲4x比具有相同元件LinkedList小。獲得LinkedList勝利的唯一可能方式是通過以故意誇大的值調用ensureCapacity來故意修正比較，或者在添加之後從ArrayList中刪除大量值。

總之，這基本上是不可能使LinkedList贏得內存比較，如果你關心的空間，然後呼籲ArrayListtrimToSize()將立即巨大的優勢再次進行ArrayList勝利。認真。 ArrayList獲勝。

來源

2012-07-19 15:44:34

感謝您的回覆.. – 2012-07-19 21:35:40

FWIW，Joshua Bloch公開表示，他認爲有史以來寫LinkedList是一個錯誤，他應該堅持ArrayList。（不幸的是，我不記得我在哪裏看到這個聲明）。 – Tobias 2014-05-22 03:42:05

如果您有內存限制，還有一件事需要考慮 - 在增長ArrayList時，您需要在複製時將內存中的原始數組和新數組放在內存中，在最壞的情況下消耗比需要的多2.5倍。即便如此，ArrayList擊敗了LinkedList。 – Mifeet 2015-05-08 12:42:50

ArrayList.trimToSize()可滿足你。

將此ArrayList實例的容量修剪爲列表當前的大小。應用程序可以使用此操作來最小化ArrayList實例的存儲。

順便說一句，在ArrayList Java6中，它不是雙倍容量，大約是最大大小的1.5倍。

來源

2012-07-19 15:43:15

感謝您的答覆.. – 2012-07-19 21:40:46

ArrayList中使用的每個對象一個參考（或兩個時，其兩倍大小它需要）。這通常是4個字節。

鏈表只使用節點其需要的，但它們可以是每個24個字節。

所以即使在最糟糕的情況下ArrayList也會比LinkedList小3倍。

有關讀取的ArrayList支持隨機存取O（1）但鏈表爲O（n）。從末尾刪除，兩者都是O（1），用於從中間某處刪除ArrayList是O（n）

除非您有百萬條條目，否則集合的大小不太可能成問題。首先重要的是無論採用哪種集合，條目的大小都是相同的。

來源

2012-07-19 15:44:04

感謝您的回覆.. – 2012-07-19 21:40:12

...但我還在猜測，因爲我已經定義LinkedList的可能是一個更好的選擇

你的猜測是不正確的情況。

一旦你已經超過了數組列表的初始容量，後備的大小將在1到2次引用乘以條目數。這是由於用於增長支持數組的策略。

對於鏈接列表，每個節點至少佔用條目數的3倍，因爲每個節點都有一個next和prev引用以及條目引用。（實際上，由於節點的對象頭和填充使用了空間，所以它是3倍以上，取決於JVM和指針的大小，它可以高達6倍）。

唯一的如果您嚴重高估了陣列列表的初始容量，則鏈接列表使用的空間少於數組列表的情況。（而對於非常小的名單......）

當你想想看，唯一真正的優勢鏈表有超過數組列表，當你插入和刪除元素是。即使如此，這取決於你如何做到這一點。

來源

2012-07-19 15:45:52

感謝您的迴應.. – 2012-07-19 21:39:40

回到信封最壞情況的：在陣列

500000名尺寸以百萬= 500,000使用的，500000個空指針在所分配的陣列的未使用部分。

鏈接列表中的500,000個條目=每個條目3個指針（節點對象保存當前，前一個和下一個）=內存中的1,5000,000個指針。（然後你必須添加節點本身的大小）

來源

2012-07-19 15:47:05 Affe

@ Affe ..yup ..簡而言之即使在這種情況下（有點最壞的情況下）ArrayList將消耗比鏈接列表更少的內存.. – 2012-07-19 21:43:13

ArrayList vs LinkedList從內存分配的角度來看

回答

相關問題