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

No. The amortized worst case is still O(1). It averages out – that’s the whole deal with amortization (and the same for deletion).

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

Answer 2

Here's a rough guestimation of the memory resources used for a stack of 100 System.Int32s:

An array implementation would require the following:

type designator                          4 bytes
object lock                              4
pointer to the array                     4 (or 8)
array type designator                    4
array lock                               4
int array                              400
stack head index                         4
                                       ---
Total                                  424 bytes  (in 2 managed heap objects)

A linked list implementation would require the following:

type designator                          4 bytes
object lock                              4
pointer to the last node                 4 (or 8)
node type designator         4 * 100 = 400
node lock                    4 * 100 = 400
int value                    4 * 100 = 400
pointer to next node  4 (or 8) * 100 = 400 (or 800)
                                     -----
Total                                1,612 bytes  (in 101 managed heap objects)

The main down-side of the array implementation would be the act of copying the array when it needs to be expanded. Ignoring all other factors, this would be a O(n) operation where n is the number of items in the stack. This seems like a pretty bad thing except for two factors: it hardly ever happens, since the expansion is doubled at each increment, and the array copy operation is highly optimized and is amazing fast. Thus the expansion is, in practice, easily swamped by other stack operations.

Similarly for the queue.