Implementing Structural Sharing: Persistent Data Structures in JavaScript

1. The Copying Problem with Immutable Updates

Immutable state management is the rule, not the exception, in modern JavaScript applications. The naive approach to implementing an update is a full deep copy of the entire object or array, followed by a change to the copy. For small, flat structures this is unproblematic. For large, deeply nested trees, for instance a document model with thousands of nodes, a full copy on every single update quickly becomes a performance problem.

Structural sharing solves exactly this problem. Instead of duplicating the entire structure, only the path from the root to the changed node is rebuilt, while every other, unchanged subtree is still referenced unchanged from the old version. The result is a new, fully immutable version of the structure that shares most of its memory with the previous version instead of duplicating it. This technique is known as structural sharing and underlies libraries such as Immutable.js as well as the persistent data structures in Clojure and Scala.

2. Basic Idea: Persistent Data Structures and Shared Subtrees

A persistent data structure fully preserves its previous version on every change instead of overwriting it. The term "persistent" here does not refer to disk storage, but to the persistence of the old version in memory: after an update, both the old and the new version exist simultaneously and both remain fully functional. Structural sharing is the implementation technique that makes this efficient, by sharing common, unchanged parts between both versions.

The core mechanism is called path copying: when a node in a tree or list structure changes, only that node and all its ancestors up to the root are newly created. Every newly created ancestor receives references to the unchanged sibling nodes of the old version instead of copying them. For a balanced tree with n nodes, this means only O(log n) nodes need to be created for an update, instead of all n nodes.

Another important aspect of persistence is the immutability of every single node itself. A node in a persistent data structure is never changed again after its creation, usually enforced with Object.freeze. This guarantee is the precondition for a node to be safely shared between multiple versions of the structure, without a later mutation on one version accidentally changing the other version too.

3. Path Copying on a Singly Linked List

Structural sharing is easiest to demonstrate on a singly linked list. Such a list consists of nodes that each contain a value and a reference to the next node. Inserting a new element at the front of the list only requires creating a new head node that points to the existing, unchanged rest of the list. The entire old list remains untouched and is fully shared with the new version.

It gets more interesting when inserting or changing an element in the middle of the list. Here, all nodes before the change point must be newly created, because their next reference needs to be adjusted, while all nodes after the change point are taken over unchanged from the old version. This is the core of path copying: only the path to the change is copied, the rest is shared.

// Immutable singly linked list with structural sharing
function cons(value, next) {
  return Object.freeze({ value, next });
}

function prepend(list, value) {
  // Only one new node is created, the rest is shared unchanged
  return cons(value, list);
}

function updateAt(list, index, newValue) {
  if (list === null) return null;
  if (index === 0) return cons(newValue, list.next); // shares list.next unchanged
  // Path copying: this node must be recreated because its "next" changes
  return cons(list.value, updateAt(list.next, index - 1, newValue));
}

const original = cons(1, cons(2, cons(3, null)));
const updated = updateAt(original, 1, 99);

console.log(original.next.value); // 2 — untouched
console.log(updated.next.value);  // 99 — new node
console.log(original.next.next === updated.next.next); // true — shared tail

4. Structural Sharing in a Binary Tree

Trees show the advantage of structural sharing even more clearly than linear lists, because every inner node typically has several child nodes, of which only one lies on the path to the change. Changing a value in the left subtree of a binary search tree means the right subtree does not need to be touched at all. The new root receives a new reference to the newly created left subtree and the same, unchanged reference to the old right subtree.

For a balanced tree with a thousand nodes, this principle reduces the number of nodes newly created on an update to about ten, the path from the root to the changed leaf. The remaining 990 nodes are shared unchanged between the old and new versions. This exact logarithmic behavior makes structural sharing practically relevant for large, frequently updated tree structures, for instance undo histories or collaborative editors.

// Immutable binary search tree with structural sharing
function node(value, left = null, right = null) {
  return Object.freeze({ value, left, right });
}

function insert(tree, value) {
  if (tree === null) return node(value);
  if (value < tree.value) {
    // Only the left path is recreated, the right subtree is shared
    return node(tree.value, insert(tree.left, value), tree.right);
  }
  if (value > tree.value) {
    // Only the right path is recreated, the left subtree is shared
    return node(tree.value, tree.left, insert(tree.right, value));
  }
  return tree; // value already present, no change needed
}

let treeV1 = null;
for (const v of [50, 30, 70, 20, 40]) treeV1 = insert(treeV1, v);

const treeV2 = insert(treeV1, 35);
console.log(treeV1.right === treeV2.right); // true — right subtree fully shared

5. From Tree to Trie: Scaling to Larger Structures

An unbalanced binary tree can degenerate in the worst case into a linked list, where an update again copies O(n) instead of O(log n) nodes. Production ready implementations of structural sharing, for example in Clojure or in Immutable.js, therefore use so called hash array mapped tries: wide, shallow trees with typically 32 children per node, indexed via parts of the hash value or index of a key.

The higher branching factor of a trie drastically reduces the effective tree depth: even with a million entries, the depth stays at about four to five levels, because each level reduces the search space by a factor of 32 instead of just a factor of 2. For an update, only four to five nodes need to be newly created, regardless of the total size of the structure. This construction is the reason structural sharing remains practical even for very large, frequently updated collections.

6. Using Reference Equality as a Side Effect

An important practical benefit of structural sharing lies outside pure memory savings: because unchanged subtrees are guaranteed to keep the same reference, a simple reference comparison with === becomes a correct and extremely cheap test for content equality. A subtree that has not changed is, after an update, still exactly the same object reference as before, never a copy with identical content.

This exact effect is the foundation for the fast comparisons in React via shouldComponentUpdate or React.memo: instead of an expensive deep equality check, a simple reference comparison suffices, because unchanged parts of the state tree are guaranteed to keep the same reference through structural sharing. Without this guarantee, every component would have to perform a full content check on every update, which would be noticeably slower for complex applications.

7. Memory Behavior: What Actually Gets Shared

A common misunderstanding is that structural sharing would reduce memory consumption to zero. In reality, every update still allocates the path from the root to the changed node anew, so this memory is needed in addition to the old version. The gain lies in the fact that the size of this newly allocated path grows logarithmically instead of linearly with the total size of the structure.

It is also important that old versions can only free memory once no reference to them exists anymore. Anyone who deliberately keeps many old versions of a structure around for debugging or undo reasons prevents garbage collection of those versions, even though structural sharing keeps the memory requirement per version low. For an undo history with hundreds of intermediate steps, this adds up to noticeable memory consumption despite sharing, which should be deliberately bounded, for instance through a maximum history depth.

In practice, it is worth looking at the actual update frequency before deciding on structural sharing. A configuration structure that is created once at program start and never changed afterward does not benefit from the technique, because there are simply no repeated updates whose cost could be amortized. The advantage only shows up for structures that are repeatedly and frequently updated during runtime.

8. Limits: When Structural Sharing Is Not Worth It

For small, flat objects with few fields, structural sharing brings no measurable advantage over a simple shallow copy with the spread operator. The implementation effort for trie based persistent structures only pays off above a certain size or update frequency, typically for collections with hundreds to thousands of elements that are updated frequently.

A second edge case concerns structures that change almost completely on every update, for instance a sorted array after inserting a new smallest element. Here there are hardly any unchanged subtrees that could be shared, and structural sharing brings no advantage in this specific case compared to a full rebuild. The technique unfolds its value primarily for localized, targeted changes to large structures, not for global overhauls of the entire data.

A practical rule of thumb: as soon as a state tree grows beyond a few dozen entries and is updated several times per second, for instance in a collaborative editor or a real time data visualization, the benefit of structural sharing clearly outweighs the additional implementation effort compared to a naive full copy.

9. Structural Sharing Compared to Alternatives

The following table contrasts structural sharing with the common alternatives for immutable updates and shows the respective trade offs in performance and implementation effort.

For many applications, a ready made library is the more pragmatic path, but understanding the underlying path copying technique helps to diagnose performance problems in your own state updates precisely and to decide when structural sharing actually justifies the implementation effort.

Teams evaluating structural sharing for the first time often start with the linked list example above, since it isolates the path copying idea without the added complexity of branching.

Once that mental model is solid, moving on to trees and eventually tries becomes a natural extension rather than a conceptual leap.

10. Summary

Structural sharing solves the copying problem of immutable updates by rebuilding only the path from the root to the changed node, while every unchanged subtree is shared untouched with the old version. This technique, known as path copying, reduces update cost from linear to logarithmic for balanced trees and to nearly constant for wide tries with high branching.

The practical benefit reaches beyond pure memory savings: guaranteed reference equality for unchanged parts makes simple === comparisons a correct replacement for expensive deep equality checks, an effect that React and other frameworks exploit for fast re-render decisions. For small, flat structures a simple copy remains sufficient, for large, frequently updated trees and collections structural sharing is the technique that guarantees performance and correctness at the same time.

11. FAQ: Implementing Structural Sharing Yourself