# 3.14 Persistent Lists

A persistent list is a list that preserves older versions after an update. Instead of modifying nodes in place, the algorithm creates new nodes for the changed prefix and shares the unchanged suffix. This style is common in functional programming, immutable data structures, undo systems, and versioned state.

## Problem

You want to update a list while keeping the original list available.

For example, given:

```text id="uybq59"
old: 1 -> 2 -> 3 -> null
```

insert `0` at the front and keep both versions:

```text id="0v06jr"
new: 0 -> 1 -> 2 -> 3 -> null
old:      1 -> 2 -> 3 -> null
```

The two lists share the suffix `1 -> 2 -> 3`.

## Core Idea

A persistent list does not mutate existing nodes.

Instead of:

```text id="6czn24"
node.next = new_next
```

it creates replacement nodes:

```text id="4ccazg"
new_node = Node(value, old_suffix)
```

The old structure remains valid because none of its links are changed.

## Push Front

Adding a value to the front is O(1).

```text id="8n3ul5"
push_front(head, value):
  return Node(value, head)
```

This creates one new node and points it at the old list.

## Pop Front

Removing the front node is also O(1), because the new version is just the old head's successor.

```text id="26kcfi"
pop_front(head):
  if head == null:
    return null
  return head.next
```

This does not destroy the old list. It only returns another existing suffix as the new version.

## Insert at Position k

Insertion in the middle requires copying the prefix before the insertion point.

```text id="96si19"
insert(head, k, value):
  if k == 0:
    return Node(value, head)

  if head == null:
    error

  rest = insert(head.next, k - 1, value)
  return Node(head.value, rest)
```

For:

```text id="7bzbxy"
old: 1 -> 2 -> 4 -> null
```

inserting `3` at position `2` gives:

```text id="zv64qs"
new: 1' -> 2' -> 3 -> 4 -> null
old: 1  -> 2  -> 4 -> null
```

The nodes `1'` and `2'` are new copies. The suffix `4 -> null` is shared.

## Delete at Position k

Deletion also copies the prefix before the deleted node.

```text id="szt18l"
delete(head, k):
  if head == null:
    error

  if k == 0:
    return head.next

  rest = delete(head.next, k - 1)
  return Node(head.value, rest)
```

The deleted node is skipped in the new version, while the old version remains unchanged.

## Update at Position k

Changing a value is a prefix-copy operation.

```text id="mr7gne"
update(head, k, value):
  if head == null:
    error

  if k == 0:
    return Node(value, head.next)

  rest = update(head.next, k - 1, value)
  return Node(head.value, rest)
```

Only the path from the head to the updated node is copied.

## Complexity Summary

| Operation            | Time | Extra Space |
| -------------------- | ---: | ----------: |
| Push front           | O(1) |        O(1) |
| Pop front            | O(1) |        O(1) |
| Insert at position k | O(k) |        O(k) |
| Delete at position k | O(k) |        O(k) |
| Update at position k | O(k) |        O(k) |
| Traverse             | O(n) |        O(1) |

## Structural Sharing

Structural sharing is the reason persistent lists are efficient. New versions reuse unchanged tails instead of copying the whole list.

```text id="en1pgb"
v1: a -> b -> c -> null
v2: x -> a -> b -> c -> null
v3: y -> x -> a -> b -> c -> null
```

Each new version adds one node and points to an older version.

## Correctness Invariant

Existing nodes are immutable. Once a node is created, its `value` and `next` fields do not change.

This invariant guarantees that any old version remains valid. If mutation is allowed, structural sharing becomes unsafe because one version can silently change another.

## Use Cases

Persistent lists are useful when old states must remain accessible.

Common examples include:

```text id="7dw97u"
undo history
compiler environments
functional stacks
backtracking search
versioned configuration
persistent symbol tables
```

In these settings, each operation creates a new logical version while older versions remain available for later use.

## Common Failure Modes

The main error is accidentally mutating a shared node. For example:

```text id="i673a4"
old_tail.next = new_node
```

If `old_tail` belongs to an older version, this modifies that older version too.

Another error is assuming persistence gives efficient random access. A persistent linked list still has O(n) indexing.

A third error is overusing lists where a persistent vector or tree would be more appropriate. Lists are efficient near the front, but expensive near the middle and end.

## Key Insight

Persistence replaces mutation with path copying. A new version contains new nodes only along the changed prefix and shares the unchanged suffix with older versions. This gives simple versioning with predictable cost, provided that shared nodes are never mutated.