# 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:

```text id="s1k4m7"
Node {
  value
  next : Node | null
}

Stack {
  head : Node | null
}
```

The invariant is:

```text id="q9r2x6"
head points to the top of the stack
```

## Push

Insert at the head.

```text id="d7p3v1"
push(stack, value):
  node = Node(value)
  node.next = stack.head
  stack.head = node
```

This runs in O(1).

## Pop

Remove and return the head.

```text id="m6t8c4"
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.

```text id="y2n5k8"
peek(stack):
  if stack.head == null:
    error
  return stack.head.value
```

## Empty Check

```text id="c4h7p9"
is_empty(stack):
  return stack.head == null
```

## Execution Trace

Push sequence:

```text id="z8v1q3"
push(1) -> 1
push(2) -> 2 -> 1
push(3) -> 3 -> 2 -> 1
```

Pop sequence:

```text id="x3f9r2"
pop() -> returns 3, stack: 2 -> 1
pop() -> returns 2, stack: 1
```

## Complexity

| Operation | Time | Space |
| --------- | ---: | ----: |
| Push      | O(1) |  O(1) |
| Pop       | O(1) |  O(1) |
| Peek      | O(1) |  O(1) |
| is_empty  | O(1) |  O(1) |

Space grows linearly with the number of elements.

## Ownership Considerations

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

```text id="w5g2k6"
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.

```text id="t1z6m4"
dummy.next = null
```

Push becomes:

```text id="u7p3n2"
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.

```text id="r9k4b7"
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:

```text id="p6x2q8"
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.