为什么.NET中队列的底层实现使用数组？

Question

我现在正在阅读C#在一个Nutshell中,书中提到Queue数据结构的底层实现使用了一个根据需要调整大小的数组.这个调整大小当然会有成本,所以我想知道使用它的背后的理由是说双链表是什么？鉴于我们只关心第一个和最后一个元素,并且双链表比数组更有效地调整大小,为什么要使用数组呢？数组会占用更少的内存,但这是唯一的理由吗？

编辑:对不起,刚刚意识到这几乎与此完全重复: 为什么Stack <T>和Queue <T>用数组实现？ (他们的问题甚至来自同一本书).无论如何,谢谢你的所有答案!

Answer 1

出于同样的原因,使用数组而不是链接列表实现了许多其他数据结构,如堆栈,哈希表,邻接列表等:

• 有了事实上的标准大小调整策略,指数增长,你只需要二十几尺寸调整操作,即使你开始与空数组,并插入一个几百万的项目.而前几个调整大小操作只会复制几个字节.
• 特别是队列很少没有限制地增长,所以你大多可以避免调整大小.
• 它不仅仅是更紧凑,一个双向链接的参考类型的公共值类型(int)比同等数组大三倍,甚至没有考虑每个对象的分配开销.如果我们诚实并考虑到这些,我们必须添加一个或两个单词的每节点标题,因此它更像是4x或5x更大.这使得阵列可能具有的任何过度分配相形见绌.
• 由于连续,阵列使各种缓存的使用大致无限好.这实际上影响了您可以对队列执行的任何操作,除了询问其大小,包括调整大小.
• 必须分配所有这些列表节点并进行垃圾收集.虽然分代GC应该使分配非常便宜,并且应该很容易选择只在队列中花费很少时间的节点,但仍然需要做很多不必要的工作,如果队列很大或很少使用,那么许多节点在以前的小GC中存活下来从队列的末尾弹出,所以就是这样.