我目前正在阅读 C# In a Nutshell，书中提到 Queue 数据结构的底层实现使用了一个根据需要调整大小的数组。这种调整大小当然会产生成本，所以我想知道使用它而不是说双链表的理由是什么？鉴于我们只关心第一个和最后一个元素，并且双链表比数组更有效地调整大小，为什么要使用数组？数组会占用更少的内存，但这是唯一的理由吗？
编辑：抱歉，刚刚意识到这几乎与此完全相同： 为什么 Stack<T> 和 Queue<T> 用数组实现？ （他们的问题甚至来自同一本书）。无论如何，感谢您的所有回答！
问问题
3095 次
3 回答
6
出于同样的原因，许多其他数据结构，如堆栈、哈希表、邻接表等，都是使用数组而不是链表实现的：
- 使用事实上的标准调整大小策略，指数增长，即使您从一个空数组开始并插入几百万个项目，您也只需要两打调整大小操作。前几个调整大小操作只会复制几个字节。
- 特别是队列很少无限制地增长，因此您可以避免调整大小。
- 它不仅更紧凑一点，公共值类型 ( ) 的引用类型的双向链表
int比等效数组大三倍，甚至没有考虑到每个对象的分配开销。如果我们诚实并考虑到这些，我们必须添加一个或两个单词的每个节点标题，所以它更像是 4 倍或 5 倍大。这使阵列可能具有的任何过度分配相形见绌。 - 由于是连续的，该数组几乎无限地更好地利用了各种缓存。这实际上会影响您可以对队列执行的任何操作，除了询问其大小，包括调整大小。
- 所有这些列表节点都必须被分配和垃圾收集。虽然分代 GC 应该使分配非常便宜，并且应该很容易地拾取只在队列中花费很少时间的节点，但这仍然是很多不必要的工作，如果队列很大或很少使用，许多节点在一次次要 GC 之前幸存下来被从队列的末端弹出，所以就是这样。
于 2013-08-21T20:03:07.870 回答
3
正如他们所做的那样，将数组用作循环缓冲区对于可以假定具有最大大小的队列来说更好。数组的增长是使它变得更昂贵的部分，因此如果您假设队列大小不会持续扩大，或者在创建队列时提供了有效的最大值，则使用数组比双向链表更可取. 众所周知的 Wikipedia上有对循环缓冲区（甚至特别提到队列）的一个很好的解释：
对于具有固定最大大小的队列，循环缓冲是一种很好的实现策略。如果队列采用最大大小，那么循环缓冲区是一个完全理想的实现；所有队列操作都是常数时间。然而，扩展一个循环缓冲区需要移动内存，这是比较昂贵的。对于任意扩展队列，可能首选链表方法。
简而言之，因为大多数用例不会涉及任意扩展队列，并且因为对于那些关心性能的人来说，可以从一开始就提供一个最大值，所以使用了一个用作循环缓冲区的后备数组。
于 2013-08-21T19:53:00.650 回答
1
恕我直言，双链表在概念上很漂亮。但理论上它需要为每个节点分配一个独立的内存块，这是相当昂贵的。我相信任何认真的双链表实现实际上都应该使用一个预先分配的内存块，它可以根据需要按部分扩展/收缩。这就是为什么数组实际上是实现队列的理想后端。
于 2013-08-21T20:00:01.223 回答