Immutable Data Structures Deep Dive
Learn persistent data structures, structural sharing, and the benefits of immutability.
What you'll learn
- Why immutability eliminates whole classes of bugs
- Structural sharing for7 efficient immutable updates
- Persistent vectors and maps
- Immutability in React and state management
Concept
Immutable Data Structures Deep Dive
Immutable data cannot be changed after creation. Instead of modifying, you create a new version with the changes. This sounds expensive, but structural sharing makes it efficient: only the changed parts are copied; the rest is shared between old and new versions.
Why Immutability?
- No aliasing bugs: if two variables reference the same data, neither can surprise the other by mutating it. 2. Cheap equality: if references are equal, the data is equal. 3. Thread safety: immutable data can be shared between threads without locks. 4. Undo/redo for free: keep references to old versions. 5. Easier reasoning: a function receiving immutable data cannot modify it.
Structural Sharing
Consider an immutable array [1, 2, 3, 4, 5]. To set index 2 to 99, you create [1, 2, 99, 4, 5]. Naively this copies all 5 elements. But with a tree structure (like Clojure persistent vector), only log(n) nodes are copied - the rest are shared. For n = 1,000,000, that is about 20 copies instead of a million.
Persistent Vectors
A persistent vector is a tree with a branching factor (usually 32). Updates copy the path from root to leaf (log32 n levels) and share the rest. Reads are O(log32 n) approx O(1) for practical sizes. This is how Immutable.js and Immer achieve near-array performance with full immutability.
Immutability in Practice
React relies on immutability for change detection: if you return a new state object, React re-renders; if you return the same reference, it skips. Redux enforces immutability in reducers. Libraries like Immer use proxies to let you write mutable code that produces immutable results.
Example
// Manual immutable updates with spread
const state = { user: { name: 'Ada', age: 36 }, posts: [{ id: 1, title: 'Hello' }, { id: 2, title: 'World' }] };
// Update user age - shallow copy changed path only
const updatedAge = { ...state, user: { ...state.user, age: 37 } };
console.log(state.user.age, updatedAge.user.age);
// Update a post title immutably
const updatedPost = { ...state, posts: state.posts.map(p => p.id === 2 ? { ...p, title: 'TypeScript' } : p) };
console.log(state.posts[1].title, updatedPost.posts[1].title);
// Structural sharing: old and new share unchanged parts
console.log(state.posts[0] === updatedPost.posts[0]); // true - shared
console.log(state.user === updatedAge.user); // false - new object
Spread creates shallow copies - only the changed path is new, unchanged branches are shared (same reference).
Try it
- JSON Diff
Immutable updates produce diffable state - see what changed between versions.
Common mistakes
The mistake
Deep-cloning when shallow copy suffices.
The fix
Deep clone copies everything, defeating structural sharing. Use spread at each level you change, or Immer.
The mistake
Mutating state in React/Redux and expecting re-render.
The fix
React compares references. If you mutate and return the same object, React sees no change. Always return a new reference.
Look up unfamiliar terms
A beginner-friendly glossary explains jargon in plain English — variables, functions, DOM, Promise, and more.
Build real projects
Apply what you learned by building guided projects with starter code and solutions.
Decode error messages
Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.