Introduction

Every time you push a value onto a stack, insert a node into a list, or rotate a tree, the old version vanishes. That is the default bargain in most programming: one structure, one present moment, no memory of the past.

Persistent data structures break that bargain. After every update you get a new version — but the previous version is still there, fully accessible, unchanged. You can keep a hundred versions of a list in memory and query any of them in the time it would take to query a single ordinary list.

The idea was formalized in a landmark 1986 paper by Driscoll, Sarnak, Sleator, and Tarjan — "Making Data Structures Persistent" — which gave us two elegant techniques: path copying (copy only the nodes on the path from root to the change) and fat nodes (store a timestamped history of values inside each node). Both achieve full persistence with only a logarithmic overhead over the ephemeral version.

Persistence is not just a theoretical curiosity. It is the backbone of functional programming, the engine behind version-control systems, and a key tool in computational geometry algorithms that need to query the past.

Try It: Time-Travel a List

This demo implements a persistent linked list using path copying. Each push creates a new head node pointing to the old head — the old version costs nothing extra to keep.

<p class="hint">Each push prepends a new node and creates a new version — old versions are never modified. Click a version badge to time-travel back to it.</p>
<div class="controls">
  <input id="val-input" type="text" placeholder="value (e.g. 42)" maxlength="6" />
  <button id="push-btn" type="button">Push</button>
  <button id="pop-btn" type="button">Pop</button>
  <button id="reset-btn" type="button" class="ghost">Reset</button>
</div>
<div id="versions-label" class="section-label">Versions <span class="tip">(click to time-travel)</span></div>
<div id="versions" class="versions"></div>
<div id="list-label" class="section-label">Current list (version  <span id="cur-ver">0</span>)</div>
<div id="list-view" class="list-view"></div>
<div id="status" class="status"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 15px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.controls { display: flex; gap: .4rem; flex-wrap: wrap; margin-bottom: .9rem; }
#val-input { font: 14px system-ui; padding: .42rem .6rem; border: 1px solid #b0b8c5; border-radius: 7px; width: 110px; }
button { font: 600 13px system-ui; padding: .42rem .85rem; border: 1px solid #1d3557; background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:hover { opacity: .88; }
.section-label { font-size: .78rem; font-weight: 700; letter-spacing: .06em; text-transform: uppercase; color: #6b7a8d; margin: .2rem 0 .35rem; }
.tip { font-weight: 400; text-transform: none; letter-spacing: 0; color: #9aabb8; }
.versions { display: flex; flex-wrap: wrap; gap: .35rem; min-height: 2rem; margin-bottom: .9rem; }
.ver-badge { display: inline-flex; align-items: center; gap: .3rem; padding: .28rem .65rem; border-radius: 20px; border: 1.5px solid #c0cad6; background: #f0f4f8; cursor: pointer; font-size: .82rem; font-weight: 600; color: #344a60; transition: all .12s; }
.ver-badge:hover { background: #dde5ee; }
.ver-badge.active { background: #1d3557; color: #fff; border-color: #1d3557; }
.ver-badge .dot { width: 7px; height: 7px; border-radius: 50%; background: #7fa4c6; flex-shrink: 0; }
.ver-badge.active .dot { background: #9fd3ff; }
.list-view { display: flex; align-items: center; flex-wrap: wrap; gap: .3rem; min-height: 3rem; margin-bottom: .6rem; }
.node { display: inline-flex; flex-direction: column; align-items: center; }
.node-box { width: 48px; height: 38px; display: flex; align-items: center; justify-content: center;
            font: 700 15px ui-monospace, monospace; border-radius: 8px; border: 1.5px solid #b0c4d8;
            background: #e8f0f7; color: #1d3557; }
.node-box.shared { background: #d8f0e0; border-color: #7ec49a; color: #1a5c34; }
.node-box.new { background: #fff3cd; border-color: #d4a435; color: #7a5800; }
.arrow { color: #7a96b0; font-size: 18px; line-height: 38px; }
.nil { font: 600 13px ui-monospace, monospace; color: #9aabb8; line-height: 38px; }
.status { font-size: .92rem; font-weight: 600; min-height: 1.3em; color: #555; }
.status.ok { color: #0a7d33; }
.empty-msg { color: #9aabb8; font-style: italic; font-size: .9rem; line-height: 38px; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Persistent linked list via path copying (prepend-only for simplicity).
// Each version is just a pointer to the head node.
// Nodes are shared across versions — no full copies ever made.
//
// Node structure: { val, next, id, isNew }
// Versions: array of head node references (or null for empty list).

let nodeCount = 0;
function makeNode(val, next) {
  return { val: String(val), next: next, id: ++nodeCount };
}

// versions[i] = head node of version i (null = empty list)
const versions = [null]; // version 0: empty list
let currentVer = 0;
let lastPushedId = -1; // track which node is "new" in the current render

function getList(head) {
  const out = [];
  let n = head;
  while (n) { out.push(n); n = n.next; }
  return out;
}

function push(val) {
  const currentHead = versions[currentVer];
  const newHead = makeNode(val, currentHead);
  lastPushedId = newHead.id;
  versions.push(newHead);
  currentVer = versions.length - 1;
}

function pop() {
  const currentHead = versions[currentVer];
  if (!currentHead) return false;
  lastPushedId = -1;
  versions.push(currentHead.next);
  currentVer = versions.length - 1;
  return true;
}

function renderVersions() {
  const el = document.getElementById('versions');
  el.innerHTML = '';
  versions.forEach((head, i) => {
    const badge = document.createElement('span');
    badge.className = 'ver-badge' + (i === currentVer ? ' active' : '');
    const dot = document.createElement('span');
    dot.className = 'dot';
    const len = getList(head).length;
    badge.appendChild(dot);
    badge.appendChild(document.createTextNode('v' + i + ' [' + len + ']'));
    badge.addEventListener('click', () => {
      currentVer = i;
      lastPushedId = -1;
      renderAll();
      setStatus(fmt('Jumped to version %i% — %len% element%v%.', { i: i, len: len, v: len !== 1 ? 's' : '' }), 'ok');
    });
    el.appendChild(badge);
  });
}

function renderList() {
  const el = document.getElementById('list-view');
  el.innerHTML = '';
  document.getElementById('cur-ver').textContent = currentVer;
  const nodes = getList(versions[currentVer]);
  if (!nodes.length) {
    const m = document.createElement('span');
    m.className = 'empty-msg';
    m.textContent = 'empty list';
    el.appendChild(m);
    return;
  }
  nodes.forEach((n, i) => {
    const wrap = document.createElement('div');
    wrap.className = 'node';
    const box = document.createElement('div');
    box.className = 'node-box' + (n.id === lastPushedId ? ' new' : ' shared');
    box.textContent = n.val;
    box.title = fmt('node #%id%', { id: n.id });
    wrap.appendChild(box);
    el.appendChild(wrap);
    if (i < nodes.length - 1) {
      const arrow = document.createElement('span');
      arrow.className = 'arrow';
      arrow.textContent = '→';
      el.appendChild(arrow);
    }
  });
  const nilSpan = document.createElement('span');
  nilSpan.className = 'arrow';
  nilSpan.textContent = '→';
  el.appendChild(nilSpan);
  const nil = document.createElement('span');
  nil.className = 'nil';
  nil.textContent = 'nil';
  el.appendChild(nil);
}

function renderAll() {
  renderVersions();
  renderList();
}

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t;
  s.className = 'status ' + (cls || '');
}

document.getElementById('push-btn').addEventListener('click', () => {
  const inp = document.getElementById('val-input');
  const v = inp.value.trim() || String(Math.floor(Math.random() * 99) + 1);
  push(v);
  inp.value = '';
  renderAll();
  setStatus(fmt('Pushed "%v%". Version %currentVer% created — old versions unchanged.', { v: v, currentVer: currentVer }), 'ok');
  // Log for verification
  console.log('push', v, '-> versions:', versions.length, '| version', currentVer, 'head:', versions[currentVer]?.val);
});

document.getElementById('pop-btn').addEventListener('click', () => {
  const removed = versions[currentVer] ? versions[currentVer].val : null;
  if (!pop()) {
    setStatus('Cannot pop — list is already empty.', '');
    return;
  }
  renderAll();
  setStatus(fmt('Popped "%removed%". Version %currentVer% created — previous versions still intact.', { removed: removed, currentVer: currentVer }), 'ok');
  console.log('pop', removed, '-> versions:', versions.length, '| version', currentVer, 'head:', versions[currentVer]?.val ?? 'nil');
});

document.getElementById('reset-btn').addEventListener('click', () => {
  versions.length = 1;
  versions[0] = null;
  currentVer = 0;
  nodeCount = 0;
  lastPushedId = -1;
  renderAll();
  setStatus('Reset to version 0 — empty list.', '');
});

// Verify structural sharing: two versions share nodes when one is a prefix of the other.
// After push('A'), push('B'): v2.head.next === v1.head (same object reference).
(function selfTest() {
  const testVersions = [null];
  let nc = 0;
  function tMakeNode(v, next) { return { val: v, next, id: ++nc }; }
  function tPush(head, v) { return tMakeNode(v, head); }

  const v0 = null;
  const h1 = tPush(v0, 'A'); testVersions.push(h1);
  const h2 = tPush(h1, 'B'); testVersions.push(h2);
  const h3 = tPush(h2, 'C'); testVersions.push(h3);

  // Structural sharing: h2.next === h1 (exact same node object)
  console.assert(h2.next === h1, 'FAIL: h2.next should be h1 (structural sharing)');
  console.assert(h3.next === h2, 'FAIL: h3.next should be h2 (structural sharing)');
  // Version 1 still has only 'A'
  console.assert(h1.next === null, 'FAIL: h1.next should be null');
  // Lengths
  function len(h) { let c=0, n=h; while(n){c++;n=n.next;} return c; }
  console.assert(len(h1) === 1, 'FAIL: v1 length should be 1');
  console.assert(len(h2) === 2, 'FAIL: v2 length should be 2');
  console.assert(len(h3) === 3, 'FAIL: v3 length should be 3');
  // Pop: v3 without top = h2
  const afterPop = h3.next;
  console.assert(afterPop === h2, 'FAIL: pop of v3 should yield v2 head');
  console.log('Self-test passed: structural sharing verified, all lengths correct.');
})();

renderAll();
setStatus('Push values to create versions. Green = new node, teal = shared node.', '');
Result
Console

Notice that clicking any past version instantly restores it. No data was ever copied in bulk — each version shares all the unchanged tail nodes with every later version. This structural sharing is what makes persistence cheap: only O(log⁡n)O(\log n) new nodes per update for trees, and just O(1)O(1) for this prepend-only list.

Compare this with a naive "snapshot" approach that copies the whole structure on every update — that would cost O(n)O(n) time and space per version. Persistence does the same job for a fraction of the cost.

The Real Complexity

How expensive is it to never throw anything away?

  • Ephemeral (ordinary) structures discard the old version on every update. Update and query are as cheap as the structure allows — O(log⁡n)O(\log n) for balanced trees, O(1)O(1) amortized for stacks.
  • Path copying rebuilds only the spine — the path from root to the modified node. For a balanced binary tree with nn nodes, that is O(log⁡n)O(\log n) new nodes per update. Queries on any version are just as fast as on the original tree. This is the technique used in most functional languages.
  • Fat nodes keep all old values inside each node, tagged by version. Updates are O(1)O(1) extra space per change, but queries must search through the version history — O(log⁡v)O(\log v) extra time where vv is the number of versions.
  • Node copying (the full Driscoll–Sarnak–Sleator–Tarjan construction) combines both ideas to achieve O(1)O(1) amortized extra space and O(log⁡n)O(\log n) query time for any pointer-based structure — the theoretical optimum.

The proven result (Driscoll et al., 1989): any ephemeral pointer-based data structure can be made fully persistent with O(1)O(1) amortized extra space per update and no asymptotic slowdown on queries. This is a solved result — there is no open question about whether it is possible, only engineering choices about which technique fits a given use case.

Compare this with problems like P vs NP where we do not even know if an efficient solution exists. Persistence is the rare case where theory gives us a complete answer.

Where It Matters

Keeping every past version alive turns out to be useful almost everywhere:

  • Functional programming: languages like Haskell, Clojure, and Elm build their entire data model on persistent (immutable) structures. Every "update" produces a new value; the old one is shared by whoever still holds a reference to it. This makes concurrent code safe without locks.
  • Version control: Git's object store is a persistent tree. Each commit is a new root that shares unchanged subtrees with its parents. Branching and time-travel are free because the old nodes are never deleted.
  • Undo / redo: any application with an undo stack — text editors, graphics tools, spreadsheets — is maintaining a linear history of persistent snapshots. Persistent trees make this cheap even for large documents.
  • Computational geometry: the "persistence trick" (Sarnak & Tarjan, 1986) is the key step in reducing plane sweep algorithms from O(nlog⁡2n)O(n \log^2 n) to O(nlog⁡n)O(n \log n). A persistent segment tree answers "what did this range look like at time tt?" in O(log⁡n)O(\log n).
  • Databases: multi-version concurrency control (MVCC) — the mechanism that lets Postgres and SQLite readers never block writers — is essentially persistence applied to database pages.

The common thread is the same idea explored in dynamic shortest paths: when the world changes, can we update our answer without starting over?

Conclusion

Most data structures live only in the present — update them and the past is gone. Persistent structures flip that assumption: every version stays alive, accessible in the same time it would take to query a single copy, thanks to structural sharing.

The theory is complete. Driscoll, Sarnak, Sleator, and Tarjan proved in 1989 that any pointer-based structure can be made fully persistent with O(1)O(1) amortized extra space per update — a rare case where the theoretical question is settled and the only remaining work is choosing the right technique for each application.

The next time you hit undo in a text editor, pull a branch in Git, or write a purely functional update in Haskell, you are standing on that foundation: a structure that never forgets.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/persistent-data-structures/Content licensed under CC BY-NC 4.0.