Linked Implementation of Stack
A singly linked list referenced by a head pointer naturally lends itself to the implementation of the Stack ADT.
Exercise Think about how to implement a stack using a singly linked list such that the core operations are constant time.
| Operation | How? | Time |
|---|---|---|
push | $O(1)$ | |
pop | $O(1)$ | |
top | $O(1)$ | |
empty | $O(1)$ |
Solution
The top of the stack would be the HEAD node of the singly linked list. This
works because every time we want to push an additional value to the stack,
we would create a new node and set it as the new HEAD node (with its .next
pointing to the original HEAD node, or NULL if the stack was empty). Then when
we want to pop a value from the top of the stack, we set the
HEAD to the current HEAD node's .next. As such, the HEAD node will always be
at the top of the stack, and calling top would return the value of the HEAD
node.
| Operation | How? | Time |
|---|---|---|
push | prepend the list and update the head | $O(1)$ |
pop | delete from front: head = head.next | $O(1)$ |
top | return head.data | $O(1)$ |
empty | check if head is null | $O(1)$ |