Rust data structures with circular references - Eli Bendersky's website

Circular references in Rust: three workable designs

Rust's ownership model makes certain data structures awkward to express. A binary tree with parent links is a classic example: a parent owns its children, but each child also needs to point back at its parent. That's a cycle, and Rust's compile-time borrow checker won't let you express it with plain references.

struct Node {
    data: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

The obvious fix—adding a parent: Option<&Node> field—forces you to introduce explicit lifetimes, and then the borrow checker fights every mutation. You can't hold a mutable reference to a node while another reference to it is alive, which makes insertion and deletion nearly impossible to write.

Rust programmers have settled on three practical alternatives. Using a binary search tree (BST) with parent links as a case study, we can compare each approach: runtime borrow checking via Rc and RefCell, handle-based references into a central vector, and raw pointers with unsafe. Full implementations for all three are available in the companion repository.

Approach 1: runtime borrow checking with Rc and RefCell

This approach leans on two standard library types. std::rc::Rc provides shared ownership of heap data; multiple Rc instances can point to the same allocation, which is freed only when the last one drops. Its weak counterpart, std::rc::Weak, holds a non-owning reference, so the data survives only as long as at least one Rc remains.

std::cell::RefCell moves borrow checking to runtime. You can create and pass references freely, but borrow() and borrow_mut() enforce the same single-writer-or-multiple-readers rule dynamically. Violations cause a runtime panic rather than a compile error.

The BST structure combines these:

Owning links to children are Rc; the non-owning parent link is Weak. Insertion into a node uses borrow_mut() to get a RefMut, which allows mutation without a visible &mut reference:

Lookups follow a similar pattern with .borrow(). Returning a found node means cloning the Rc, which guarantees the node won't be dropped while the caller still holds it.

This design works, but it's fussy. Every node is wrapped in Option, Rc, and RefCell, and you must track which layer you're operating on. It's also awkward to return a plain reference to stored data: a RefCell must track borrows at runtime, so callers receive a std::cell::Ref rather than a regular &, leaking implementation details into the API.

Approach 2: vector handles as node references

The second design sidesteps cycles entirely. The Tree owns a Vec<Node>, and "references" are indices into that vector. A handle of 0 means "none".

Insertion is straightforward. A new node is pushed onto the vector, and its handle is returned:

This version is markedly simpler than the Rc/RefCell approach. There are no layers of indirection, fewer heap allocations, and the vector's memory layout is cache-friendly. It's also likely faster, since RefCell's dynamic borrow checks disappear entirely.

The costs are real, though. Handles are raw indices: a bug can index past the vector's end, point at the wrong node, or mutate a slot that other handles still reference. And deletion is a lie. "Removing" a node just unlinks it from the tree; the memory stays allocated forever:

For production use, you'd want a free list of reusable indices—or a full garbage collector. Neither is implemented in the sample code.

Approach 3: raw pointers and unsafe

The third option feels most familiar to C programmers. Node links become raw pointers:

Allocation uses Box::into_raw, which hands over ownership of the heap memory to the raw pointer. From that point on, deallocation is your responsibility:

Insertion requires an unsafe block for every pointer dereference—something Rust normally forbids:

Deallocation goes through Box::from_raw, which reconstructs a Box that owns the memory and frees it when dropped. This is also how you must clean up the entire tree: the default Drop implementation has no idea how to release a *mut Node root, so without a custom Drop you'll leak memory.

Writing raw-pointer code requires less mental overhead than juggling Option<Rc<RefCell<Node>>>; the line counts are similar but the logic reads like ordinary C. It's also likely faster, since there are no runtime borrow checks. The trade-off is the complete loss of compile-time safety—all the classic C memory bugs are back on the table. The right choice depends on whether you prefer fighting the borrow checker or fighting memory unsafety.

Three ways to model cyclic graphs in Rust

Rust’s ownership model makes circular references inconvenient, but not impossible. There are three practical strategies, each with a different trade-off between ergonomics and safety. All are worth knowing, and the choice often comes down to how much risk you’re willing to manage manually versus how cleanly you want your API to read.

1. Rc + RefCell: safe but verbose

The most straightforward approach uses Rc for shared ownership and RefCell for interior mutability. For instance, a doubly-linked list node would hold Rc> pointers. This is fully safe — the borrow checker is satisfied at runtime via RefCell, and reference counts handle deallocation. The downside is that cycles will leak memory unless you manually break them (e.g., with take()), and the API can get noisy with repeated borrow_mut() calls.

Typical code for creating a simple circular list looks like this:

struct Tree {
    root: Option<Node>,
}

struct Node {
    data: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

Note that both forward and backward links use Rc, which means the list is inherently leaky. A common workaround is to use Weak in one direction (e.g., the prev field) so that dropping the head breaks the cycle. This is still fully safe, but the bookkeeping is done by you, the developer.

2. Index-based handles in a Vec: memory-safe but alias-prone

Instead of pointers, you can store all nodes in a single Vec and refer to each other by integer indices. This pattern is common in games and ECS-like designs, and it avoids unsafe entirely. Memory safety is guaranteed by the allocator, and deallocation is trivial: just drop the Vec.

The trade-offs are less obvious but real. The API becomes more error-prone because a typo or a logic bug can send you to the wrong node — and unlike with Rc, there’s no runtime guard against aliasing borrows. For example, you might easily write a method that mutates a node while holding an immutable borrow of another one from the same Vec, which will panic. Style-wise, you need to be disciplined about when you take indices versus nodes.

Here’s a minimal sketch of a doubly-linked list using this pattern:

struct Node {
    data: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
    parent: Option<&Node>,
}

The main advantage over Rc/RefCell is that there are no reference-count cycles to worry about, and moving or traversing is cheap — just plain integers. The main disadvantage is that your code may compile fine while having subtle borrow or logic bugs that show up only at runtime.

3. Raw pointers and unsafe: full control, great care needed

For the highest level of control, you can use raw pointers and wrap each operation in an unsafe block. This is effectively what Rust’s own standard library does for collections like Vec or LinkedList, and it’s also the pattern behind many popular crates built around arenas or intrusive structures.

The benefits: no ref-counting overhead, no cycle leaks, and the struct layout is exactly what you want. The costs: every dereference is unchecked, so one wrong move can cause undefined behavior. You’re responsible for invariants, aliasing rules, and remembering to drop nodes properly via Box::from_raw. For small, well-isolated graph utilities, this can be a good fit; for large application-wide data structures, the risk may not be worth it.

Code gets more verbose, but it’s quite performant. For example:

struct Tree<'a> {
    root: Option<Node<'a>>,
}

struct Node<'a> {
    data: i32,
    left: Option<Box<Node<'a>>>,
    right: Option<Box<Node<'a>>>,
    parent: Option<&'a Node<'a>>,
}

Notice that insert must manually fix the previous node’s next pointer and the new node’s prev. In a safe or index-based design those are just two fields on separate objects; in a raw-pointer design they’re two distinct memory writes that the compiler won’t reorder without care.

How to choose

There’s no universal winner. Even though unsafe with raw pointers is popular for the standard library and foundational crates, you wouldn’t use it in a high-level business or application domain where safety bugs are costly and hard to debug. The index-based Vec approach gives you a surprisingly ergonomic middle ground when you want to keep everything safe and avoid cycles. Rc/RefCell is best when you want to model shared ownership directly and are okay with explicit cycle-breaking.

use std::cell::RefCell;
use std::rc::{Rc, Weak};

pub struct Tree {
    count: usize,
    root: Option<NodeLink>,
}

type NodeLink = Rc<RefCell<Node>>;

#[derive(Debug)]
struct Node {
    data: i32,
    left: Option<NodeLink>,
    right: Option<NodeLink>,
    parent: Option<Weak<RefCell<Node>>>,
}

Getting these three approaches right requires knowing Rust’s ownership model deeply. That comfort comes with practice — but having the options in your toolkit is a much better place than being stuck with a single, rigid pattern.