Tracing the LinkedStack

Let’s trace the same sequence of operations we ran on ArrayStack, this time on LinkedStack. The behavior must be identical. But the structure underneath is different. Remember that head is the top. In each diagram below, the left end of the linked list is head, marked with the top label.

We start with new LinkedStack<>(). There is no array to allocate; an empty stack is just a head that is null:

         (empty stack — head is null)

push(4) allocates a node holding 4, points its next at the old head (which is null), and moves head to the new node:

         ┌───┐
top ───▶ │ 4 │ ──▶ null
         └───┘

push(9) does the same: a new node goes in front, and head moves to it. The node holding 4 does not move; it is second now:

         ┌───┐      ┌───┐
top ───▶ │ 9 │ ──▶  │ 4 │ ──▶ null
         └───┘      └───┘

push(6) repeats the pattern:

         ┌───┐      ┌───┐      ┌───┐
top ───▶ │ 6 │ ──▶  │ 9 │ ──▶  │ 4 │ ──▶ null
         └───┘      └───┘      └───┘

Next, top() returns 6, the value in the head node, and changes nothing.

Then pop() runs, and it is one assignment: head = head.next. The head advances to the node holding 9, and the node holding 6 is no longer reachable from the stack:

         ┌───┐      ┌───┐
top ───▶ │ 9 │ ──▶  │ 4 │ ──▶ null
         └───┘      └───┘

         ┌───┐
         │ 6 │   (no longer reachable)
         └───┘

We draw the detached node here to show what pop leaves behind.

A second pop() advances the head once more, leaving just 4:

         ┌───┐
top ───▶ │ 4 │ ──▶ null
         └───┘

push(2) puts a new node in front:

         ┌───┐      ┌───┐
top ───▶ │ 2 │ ──▶  │ 4 │ ──▶ null
         └───┘      └───┘

And a final top() returns 2 with no state change.

This trace never needed a size field, a capacity, or empty slots. When we traced ArrayStack, every step showed unused slots and a size field pointing at the next free slot. Here the linked list is exactly as long as the stack, and the top is the node head points at.