Persistent Data Structures

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.

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">{{hint}}</p>
<div class="controls">
  <input id="val-input" type="text" placeholder="{{placeholder}}" maxlength="6" />
  <button id="push-btn" type="button">{{btn_push}}</button>
  <button id="pop-btn" type="button">{{btn_pop}}</button>
  <button id="reset-btn" type="button" class="ghost">{{btn_reset}}</button>
</div>
<div id="versions-label" class="section-label">{{label_versions}} <span class="tip">({{tip_click}})</span></div>
<div id="versions" class="versions"></div>
<div id="list-label" class="section-label">{{label_current_list}}  <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; }

// Code not found

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)$ new nodes per update for trees, and just $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)$ time and space per version. Persistence does the same job for a fraction of the cost.

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)$ for balanced trees, $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 $n$ nodes, that is $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)$ extra space per change, but queries must search through the version history — $O(\log v)$ extra time where $v$ is the number of versions.
• Node copying (the full Driscoll–Sarnak–Sleator–Tarjan construction) combines both ideas to achieve $O(1)$ amortized extra space and $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)$ 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.

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(n \log^2 n)$ to $O(n \log n)$. A persistent segment tree answers "what did this range look like at time $t$?" in $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?

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