3.19 Stack via List

A stack is a last-in, first-out (LIFO) structure. A singly linked list implements a stack naturally by treating the head as the top. All operations occur at the head, which gives constant-time push and pop.

Structure

Use a singly linked list:

Node {
  value
  next : Node | null
}

Stack {
  head : Node | null
}

The invariant is:

head points to the top of the stack

Push

Insert at the head.

push(stack, value):
  node = Node(value)
  node.next = stack.head
  stack.head = node

This runs in O(1).

Pop

Remove and return the head.

pop(stack):
  if stack.head == null:
    error

  node = stack.head
  stack.head = node.next
  node.next = null

  return node.value

This also runs in O(1).

Detaching node.next helps avoid accidental reuse of links.

Peek

Return the top value without removing it.

peek(stack):
  if stack.head == null:
    error
  return stack.head.value

Empty Check

is_empty(stack):
  return stack.head == null

Execution Trace

Push sequence:

push(1) -> 1
push(2) -> 2 -> 1
push(3) -> 3 -> 2 -> 1

Pop sequence:

pop() -> returns 3, stack: 2 -> 1
pop() -> returns 2, stack: 1

Complexity

Space grows linearly with the number of elements.

Ownership Considerations

In a manual-memory setting, pop transfers ownership of the node to the caller.

node = stack.head
stack.head = node.next
node.next = null
return node

The caller is responsible for freeing or reusing the node.

In a garbage-collected setting, removing the node from the list makes it eligible for reclamation when no references remain.

Using Sentinel

A sentinel is optional for a stack because operations always occur at the head. If used, it simplifies some invariants.

dummy.next = null

Push becomes:

node.next = dummy.next
dummy.next = node

The top is dummy.next.

Persistent Stack

A persistent stack is a linked list where each push creates a new head and shares the tail.

push(head, value):
  return Node(value, head)

Each version is independent, and push runs in O(1) with structural sharing.

Common Failure Modes

• Losing the rest of the stack by overwriting head before saving it
• Forgetting to update head during pop
• Using a node after it has been detached or freed
• Returning a node while still leaving it linked

Use Cases

Stacks via linked lists appear in:

expression evaluation
depth-first search
backtracking
undo systems
call stacks in interpreters

Key Insight

A stack uses only one end of the list. This makes linked lists an optimal representation: insertion and removal at the head are constant-time and require only local pointer updates.