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。