LinkedList內存消耗與使用大型數組時的列表

Question

任何人都可以告訴我，如果一個鏈表結構將被允許增長大於等效List（假設列表使用加倍策略來增加內部數組的大小） 。

因此給定一個結構，比如說40字節（我知道關於16字節和結構的東西，但我在這裏使用一些遺留代碼，它不會是一個簡單的選項，將結構更改爲類）我的理解是每次列表的內部數組被調整大小時，都需要爲新數組分配內存（new_array_size * 40）。因此，對於一個非常大的陣列，最終會導致內存不足，因爲沒有足夠大的連續空間來創建這個新陣列。我知道鏈表需要爲每個元素（節點）留出更多的空間，因爲它需要保持向前和反向指向列表中的項的指針，但是我的問題是這是否意味着要添加額外的元素，您只需要一個連續的內存插槽（40 + the_space_needed_for_the_pointers）。換句話說，鏈表不會因分配一個巨大的連續內存的新部分而受到影響。

Answer 1

是的，這是準確的。 LinkedList不使用數組進行存儲，它確實是一個引用鏈。當您需要存儲大量元素時，您不會在大對象堆中產生垃圾，與列表不同，避免地址空間碎片出現問題。

當心它是而不是替代List，索引是O（n）而不是O（1）。差別很大，除非您總是按順序迭代列表。當你需要做出這樣的尖銳選擇時，現在是開始考慮64位操作系統的時候了。

Answer 2

由於鏈接列表僅引用向前和向後引用，因此不會限制連續的內存分配。 @Hans的答案有很多優點;然而，我不同意64位操作系統是唯一具有高性能索引的選項。

你是否僅限於這2種選擇？

如果你要有大量的結構來引用，你可以考慮一個二叉樹嗎？使用樹的上限是索引是鏈表的一部分 - O（log n）。缺點是保持樹木平衡的額外工作。平衡是必不可少的 - 沒有平衡，你最終會得到相當於一個鏈表。

查看這MSDN article（6部分）從第3部分開始用二叉樹。有幾種基本的BST。