c# - 为什么 Stack<T> 和 Queue<T> 用数组实现？

Question

我正在阅读 Albahari 兄弟的 C# 4.0 in a Nutshell，我遇到了这个:

Stacks are implemented internally with an array that's resized as required, as with Queue and List. (pg 288, paragraph 4)

我不禁想知道为什么。 LinkedList 提供 O(1) 头尾插入和删除(这对于堆栈或队列来说应该很好用)。一个可调整大小的数组具有 O(1) 分摊插入(如果我没记错的话)，但 O(n) 最坏的情况(我不确定删除)。而且它可能比链表使用更多的空间(对于大型堆栈/队列)。

还有更多吗？双向链表实现的缺点是什么？

Answer 1

but O(n) worst case

摊销的最坏情况仍然是 O(1)。长插入时间和短插入时间取平均——这就是摊销分析的重点(对于删除也是如此)。

数组使用的空间也比链表少(毕竟链表必须为每个元素存储一个额外的指针)。

此外，开销比链表少得多。总而言之，基于数组的实现对于几乎所有用例来说都(多)更有效，即使偶尔访问会花费更长的时间(事实上，队列可以通过采取稍微更有效地实现页面本身在链表中管理的优势——参见 C++ 的 std::deque 实现)。