Member-only story
I Tried to Build a Graph in Rust. The Borrow Checker Made Me Redesign It
How Rust’s ownership model pushes you toward index-based graph design
Part of the Data Structures in Rust series.
A dependency manager is a graph. Package A depends on B, B depends on C, and a circular dependency creates a cycle the package manager has to detect and reject. A routing table is also a graph: each location stores connections to neighbouring locations, and finding the shortest path means traversing those connections efficiently. The data structure underlying both is the same, and implementing it in Rust exposes something worth understanding about how ownership shapes design decisions.
Pointer-based linked lists are one of the worst fits for Rust’s ownership model because they require nodes to hold mutable links in both directions. Graphs have the same problem, amplified. A graph node can have any number of edges pointing to any other node, including back to itself. There is no hierarchy, no single direction of ownership, no clean parent-child relationship the compiler can reason about statically. Node A might point to Node B, which points to Node C, which points back to Node A.
Expressing this in Rust forces a choice: reach for Rc<RefCell<T>> and accept runtime borrow checking, or change the representation entirely and use integer…
