Persistent Data Structure Concepts

In this lesson, you will learn how to implement "persistence" in data structures, allowing you to access previous versions of your data without duplicating the entire structure.

The Core Concept: Structural Sharing

In Rust, when we think of a "persistent" data structure, we don't mean writing to a disk. Instead, we refer to structures that are effectively immutable: once a version is created, it never changes. When you want to "modify" the structure, you create a new version that reuses the parts of the previous version that didn't change. This technique is called structural sharing.

Imagine a simple linked list. If you want to add an element to the front, you create a new node that points to the existing head of the list. Both the old version and the new version are valid and share the entire tail of the list in memory.

Implementation in Rust

To achieve this, we rely on std::rc::Rc for shared ownership. Since the data is immutable, multiple versions can safely point to the same memory addresses.

use std::rc::Rc;

struct Node<T> {
    value: T,
    next: Option<Rc<Node<T>>>,
}

// Creating a new version based on an old one
fn push<T>(val: T, head: Option<Rc<Node<T>>>) -> Rc<Node<T>> {
    Rc::new(Node {
        value: val,
        next: head, // Structural sharing: the old list is now the tail
    })
}

In this code, the push function doesn't modify the existing list. It returns a new Rc wrapper that represents the new head. If you have an old_list variable, it remains untouched and perfectly valid, even as you build a new_list that points into the same underlying memory for its tail.

Because we are using Rc, we don't have to copy the data. We only allocate a single new node. This allows us to keep a "history" of our collections with minimal memory overhead, which is much more efficient than cloning a Vec every time an update occurs. This pattern is essential when building undo systems, functional state management, or concurrent algorithms where you need consistent snapshots of data without expensive synchronization.

Key Takeaway: Persistent data structures achieve versioning through structural sharing, where new versions reuse the nodes of previous versions rather than copying the entire collection.