Implementing a Stack with a Linked List

Imagine you are told that a stack supports push and pop, and that you may build it in one of two ways. One way uses a linked list. The other uses an array. Before choosing, a practical question is worth asking: when a single stack operation runs, how much work could it end up doing, and does that amount of work depend on how full the stack already is?

The two implementations answer this question differently. One keeps every push and pop equally cheap no matter what. The other is cheap almost all of the time but has one situation in which a single push must do a great deal of work. The difference is more subtle than a simple fast-versus-slow comparison, so it is worth working through carefully.

When we analyze how long a stack operation takes, we first need a way to measure the size of the problem. For a stack, the natural choice is the number of items currently on the stack. Call that number n. The question then becomes how the running time of push or pop grows as n grows.

This choice of size matters because a stack's operations only ever touch the top of the stack. Whether the answer depends on n is the central question for each implementation. Some implementations never let n affect the work; others let it affect the work in specific situations.

In a linked list implementation, each stack item lives in a node, and each node holds a link to the node beneath it. The stack keeps track of the top through a head pointer. Pushing a new item means creating a node whose link points to the current top, then moving the head pointer to the new node. Popping means taking the node at the head, moving the head pointer down to the node it links to, and returning the removed item.

Notice what did not change. The nodes B and A were not visited, copied, or rearranged. Only the head pointer and the link of the new node were updated. The same is true of pop, which only moves the head pointer down past the removed node. Because the operations consist of a handful of simple assignments at the top of the stack, nothing in them requires visiting the other items.

For a linked list implementation, the worst-case run time of both push and pop is Theta(1). In plain terms, the run time is bounded by some fixed constant that does not depend on how many items the stack holds. Whether the stack has three items or three million, a single push or pop finishes within the same fixed amount of work.

This is the reason the linked list has predictable behavior. Every operation looks the same from the outside, regardless of history. The cost of the next push does not depend on the pushes that came before it.

An array has a fixed amount of storage. Most pushes simply place a new item into the next free slot, and for these the run time is Theta(1). The trouble comes when the array is full and there is no free slot left. At that moment the implementation cannot simply write one more item, so it must make room in a different way.

The method is to create a new, larger array and copy every existing stack item into it, after which the new item can be placed. Copying takes time in proportion to the number of items already on the stack. Because the copying loop touches each of the n items, a push that triggers it has a worst-case run time of Theta(n).

The worst case tells us how bad one operation can be. The average case tells us what to expect over a sequence of operations. For the array implementation these two measures give different pictures. The worst case of a single push is Theta(n), but that worst case occurs only rarely. Because of that rarity, there is a natural sense in which the average run time of push on an array remains Theta(1).

The source presents this average-case reasoning as a natural sense of average behavior rather than as a formal calculation, so it should be understood at that level. The key habit is to state worst-case and average-case claims separately. A single push on an array can cost Theta(n), and the same array's pushes can still average Theta(1) across a long sequence.

Placing the two implementations next to each other makes the contrast clearer. The linked list keeps every push and pop at a fixed cost regardless of stack size. The array keeps ordinary pushes cheap but accepts one expensive case, the push that finds the array full. Neither implementation is simply better in every respect; each trades one kind of predictability for another.