Using a Linked List to Implement a Stack

Our second implementation, LinkedStack, stores the items in a linked list of nodes, the way LinkedList did. As before, we will design before we code: pick the representation, then work through the operations and their costs.

Choosing Which End Is the Top

A linked list has two ends, the head and the tail, and again we must decide which one is the top of the stack. Recall from the linked list chapters what each end costs:

1. At the head, linking and unlinking a node is $O(1)$: point the new node at the old head, or move the head one node forward.

2. At the tail, adding is $O(1)$ if we keep a tail pointer, and removing is $O(1)$ if we use a doubly linked list (and keep a tail pointer).

Let’s choose the head as the top since we can use a singly linked list with only a head pointer and still get $O(1)$ for all operations.

Operations and Complexity

isEmpty(): The stack is empty exactly when the list has no nodes, that is, when the head reference is null. This is $O(1)$, and notice that we do not even need a count.

top(): The top item is in the head node, so we return its value. This is $O(1)$.

pop(): Move the head one node forward. The old head node is unlinked, and the second node (or null, if there is none) becomes the new top. There is no shifting and no traversal, so this is $O(1)$.

push(T item): Create a new node, point it at the old head, and make it the new head. This is addFirst from Chapter 6, and it is $O(1)$.

Every operation is $O(1)$ again. This time push is $O(1)$ in the worst case, not just amortized.