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:

old: 1 -> 2 -> 3 -> null

insert 0 at the front and keep both versions:

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:

node.next = new_next

it creates replacement nodes:

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).

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.

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.

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:

old: 1 -> 2 -> 4 -> null

inserting 3 at position 2 gives:

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.

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.

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

Structural Sharing

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

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:

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:

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.