Building persistent data structures with practical Python code

Persistent data structures don't belong to a single language or paradigm. The idea predates Python by decades, yet the language gives you just enough immutability primitives to express them clearly. If you've ever wished you could pass a collection to a function without worrying about it being mutated under your nose, persistence is the answer. It's also the answer to questions like "what did this list look like three steps ago?" without keeping manual copies.

For developers working through interview prep at a Melbourne bootcamp or building side projects from a Brisbane home office, persistent structures offer a quiet superpower. You can hand a snapshot to another function, compare states across time, or roll back changes without writing a single rollback handler. The implementation isn't exotic either. With a handful of classes and a recursive helper, the ideas behind persistent stacks, queues and even trees become approachable for anyone comfortable with Python's object model.

What persistence actually means

In data structure theory, persistence doesn't refer to disk storage or databases. It describes a property where every operation produces a new version of the structure while keeping old versions intact and accessible. Think of it like Git commits: each commit is a snapshot, and you can check out any of them without losing the rest. In programming terms, if you call push on a persistent stack, you receive a brand-new stack with the extra element on top, and the original stack remains exactly as it was.

This behaviour is the default in functional languages such as Haskell or Clojure. In Python, however, the standard library leans heavily towards mutability, which is why persistent structures feel like something of an import. The good news is that Python's object model makes persistence straightforward. Tuples are immutable, classes can be frozen with @dataclass(frozen=True), and copying objects is cheap when they hold references rather than copies of nested data. The mental shift is small, even if the spelling of behaviour in your codebase looks a touch different from what you might have written elsewhere.

The functional foundation

Persistent structures rest on a small set of building blocks worth naming explicitly. Each plays a role in keeping versions cheap and safe to share, and understanding them upfront saves hours of confused debugging later.

Core principles to internalise

• Immutability means once an object exists, its internal state cannot change.
• Structural sharing lets the new version reuse most of the old structure, isolating changes to a node or two.
• Path copying recreates only the nodes along the path to the modified part of the tree.
• Reference identity in Python acts like a pointer, giving you structural sharing for free.

Together these principles give you what textbooks at universities in Sydney and Adelaide call a path copy tree. The terms sound intimidating, but in code they amount to creating a few new objects and pointing them at existing nodes. The trick is recognising that Python references already behave like pointers, so you don't need to drop down to C or rely on ctypes. Most second-year computer science subjects at Australian unis touch on these concepts, even if they don't always use the phrase persistent data structure.

A persistent stack in pure Python

The simplest persistent structure to build is a stack. Each frame holds a value plus a reference to the previous frame, and a special empty frame signals the bottom. Because every frame is immutable, two stacks that share a tail are actually sharing the same memory, which is exactly what structural sharing looks like in practice.

from dataclasses import dataclass
from typing import Optional, Any

@dataclass(frozen=True)
class Stack:
    value: Any
    prev: Optional["Stack"] = None

EMPTY = Stack(None)

def push(stack, value):
    return Stack(value, stack)

def pop(stack):
    return stack.prev

def peek(stack):
    return stack.value

Calling push(s, 42) returns a new stack without touching s. You can stack operations, branch off alternative paths, then discard the ones you don't need. The garbage collector eventually cleans up unused nodes, so memory grows only in proportion to the number of distinct versions you retain. From there, it's a short step to richer persistent structures like cons lists and trees, and the code shape stays remarkably similar.

Beyond stacks: queues and persistent lists

Stacks get you off the ground, but queues are where things get interesting. A persistent queue is harder because both ends of the structure need to behave well under immutability. The trick, popularised by Chris Okasaki, is to maintain two stacks under the hood. Enqueueing pushes onto the back stack, and dequeuing pops from the front, reversing onto the back when the front runs dry. Each reversal produces new frames, but the front stack stays untouched, giving you persistence on every operation.

The mental model carries over cleanly to other structures, including persistent cons lists, ropes for editable text buffers, and persistent hash maps backed by bit-partitioned tries. If you want to read more about applying data structures in real systems, the web development section walks through several examples that complement these ideas and shows how the same patterns turn up in production code, not just textbooks.

Path copying versus structural sharing

Path copying and structural sharing are two sides of the same coin, but they show up differently depending on what you're building. In a persistent binary search tree, an insertion only needs to recreate the nodes from the root down to the inserted leaf. The rest of the tree, including subtrees hanging off sibling branches, stays shared between old and new versions. The cost is proportional to the height of the tree, not the number of nodes.

In a persistent hash array mapped trie, structural sharing is even more aggressive. Each level of the trie shares most of its branching with neighbouring nodes, so updates only touch a handful of leaves. Clojure's persistent maps work this way. You can replicate the pattern in Python using nested dictionaries, though the per-node overhead is larger than a low-level implementation would use, so real benchmarks matter more than benchmarks usually do in Python.

Trade-offs you should weigh

Persistent structures aren't free. The performance characteristics differ from their mutable cousins in ways that matter when you scale up to serious workloads. A summary of the main trade-offs helps frame the choice for a project before you commit to either approach.

Key trade-offs at a glance

• Memory usage can grow with the number of versions you retain, even when most nodes are shared.
• Some operations have amortised rather than worst-case guarantees, so a single call may occasionally be slow.
• Debugging can be trickier when multiple versions of an object are floating around a call stack.
• The standard library doesn't ship persistent versions, so you either build them yourself or reach for a third-party library.
• Equality semantics need to match between versions, which sometimes forces extra bookkeeping in __eq__ overrides.

That said, the alternative is often worse. Mutable shared state is a frequent source of bugs, especially when functions mutate arguments behind your back. Persistent structures make data flow explicit, which feels like a feature rather than a limitation once you adjust your thinking. For solo developers and small teams scattered across Perth and Hobart, this explicitness can save an afternoon of print-statement debugging.

When persistence shines in practice

A few scenarios make persistence feel less like an academic exercise and more like a sensible engineering choice. Consider undo functionality: rather than tracking inverse operations, you keep a stack of snapshots and pop one when the user hits Ctrl+Z. Consider concurrent algorithms: threads can hold their own version of a structure without locking because none of them are writing to shared memory. Consider pure functions in machine learning pipelines, where each transformation ought to leave the input untouched.

If you're experimenting with neural network code, persistent pipelines pair nicely with the kind of component-based architectures described in guides on perceptron and backpropagation. Each layer can receive an immutable snapshot of weights and activations, making gradient checks easier to reason about. Australian tech meetups from Coffs Harbour to Fremantle regularly feature talks on functional patterns, and persistence is one of those quiet techniques that travels from curiosity to muscle memory once you start reaching for it in production code.