使用大型数组时LinkedList内存消耗与List

是的,那是准确的。LinkedList不使用数组进行存储,它实际上是一个引用链。与list不同,当需要存储大量元素时,在大型对象堆中不会得到垃圾,并避免地址空间碎片导致程序过早崩溃的问题。

当心它是 不 作为列表的替代,索引是o(n)而不是o(1)。区别很大,除非您总是按顺序迭代列表。当你需要做出这样尖锐的选择时,是时候开始考虑64位操作系统了。

由于链接列表只引用正向和反向引用,因此不绑定到连续内存分配。@汉斯的回答有很好的优点;但是,我不同意64位操作系统是唯一具有高性能索引的选项。

你只限于这两种选择吗?

如果要引用大量结构,可以考虑使用二叉树吗?使用树的好处是索引只是链表-o(log n)的一小部分。缺点是需要额外的工作来保持树的平衡。平衡是必须的-没有平衡,你最终会得到一个相当于链表的结果。

看看这个 MSDN article (6部分)从第3部分开始,使用二叉树。有几种基本的bst。