Course contentsShow
← Computer Science
Lesson 2145 of 2,87248. Programming ParadigmsFree lesson

Persistent Data Structures

Efficiently implement immutable collections using structural sharing techniques.

Persistent Data Structures

What you'll learn: How to efficiently implement immutable collections that preserve previous versions without copying everything.

The Challenge of Immutability

In functional programming, immutability is core: once you create a data structure, you never modify it. Instead, operations return new versions. The naïve approach? Copy the entire structure on every change. A list with a million elements? Copy all million to add one item. That's wasteful.

Structural Sharing to the Rescue

Persistent data structures solve this by sharing unchanged parts between versions. Think of it like a tree where branches represent different versions of your data. When you "modify" the structure, you only create new nodes along the path that changed—everything else is reused.

Analogy: The Family Photo Album

Imagine a family photo album. Instead of duplicating the entire album every time you add a photo, you keep the old pages and just add a new cover that points to mostly the same pages, plus one new page. Both versions exist simultaneously, sharing most content.

How It Works

When you insert into a persistent list or tree:

  1. Create new nodes only for the path affected by the change
  2. Point new nodes to unchanged subtrees from the old version
  3. Both old and new versions remain accessible

For a balanced tree of n elements, most operations touch only O(log n) nodes, not all n nodes. You get immutability with logarithmic overhead instead of linear copying.

Common Examples

  • Persistent vectors (like Clojure's PersistentVector)
  • Persistent hash maps with tree structures
  • Persistent linked lists (sharing tails)

Key Takeaway: Persistent data structures enable efficient immutability by sharing unchanged portions between versions, giving you history and thread-safety without massive memory or time costs.