我正在阅读 Albahari 兄弟的 C# 4.0 in a Nutshell，我发现了这个:
I'm reading C# 4.0 in a Nutshell by the Albahari brothers and I came across this:
堆栈是通过根据需要调整大小的数组在内部实现的，就像队列和列表一样.(第 288 页，第 4 段)
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) 最坏的情况(我不确定删除).它可能比链表使用更多的空间(对于大堆栈/队列).
I can't help but wonder why. LinkedList provides O(1) head and tail inserts and deletes (which should work well for a stack or queue). A resizable array has O(1) amortized insert (if I remember right), but O(n) worst case (I'm not sure about delete). And it probably uses more space than the linked list (for large stacks/queues).
还有比这更多的吗?双向链表实现的缺点是什么?
Is there more to it than that? What is the downside to a doubly linked list implementation?
推荐答案但 O(n) 最坏情况
but O(n) worst case
摊销的最坏情况仍然是 O(1).长短插入时间平均 - 这就是摊销分析的重点(删除也是如此).
The amortized worst case is still O(1). Long and short insertion times average out – that’s the whole point of amortised analysis (and the same for deletion).
数组也比链表使用更少的空间(毕竟链表必须为每个元素存储一个额外的指针).
An array also uses less space than a linked list (which after all has to store an additional pointer for each element).
此外，开销比链表少得多.总而言之，对于几乎所有用例来说，基于数组的实现只是(很多)更有效，即使偶尔访问会花费更长的时间(实际上，队列可以通过以下方式更有效地实现本身在链表中管理的页面的优势——参见 C++ 的 std::deque 实现).
Furthermore, the overhead is just much less than with a linked list. All in all, an array-based implementation is just (much) more efficient for almost all use-cases, even though once in a while an access will take a little longer (in fact, a queue can be implemented slightly more efficiently by taking advantage of pages that are themselves managed in a linked list – see C++’ std::deque implementation).
更多推荐
为什么 Stack<T>和队列 T用数组实现?
发布评论