Why are Stack<T> and Queue<T> implemented with an array?

Question

I'm reading C# 4.0 in a Nutshell by the Albahari brothers and I came across this:

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

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?

Answer 1

but O(n) worst case

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).

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).