A few years ago, I watched a senior dev on my team—someone who could write C++ in his sleep—spend an entire Tuesday staring at a compiler error. He was trying to port a doubly linked list from an old codebase into Rust. He kept trying to use Box for the next and prev pointers, but the borrow checker was absolutely shredding his code. He eventually came to my desk, visibly frustrated, and asked, "Is it actually possible to build a graph or a list in this language without using unsafe every five lines?"

The problem is that in C++, pointers are just addresses. In Rust, a pointer carries a set of promises about ownership and lifetime. When you have two nodes that point to each other, you've created a cycle. If you use Box, you're claiming sole ownership. But a node in a doubly linked list can't be "owned" by both its predecessor and its successor simultaneously. You'll hit a wall immediately.

Navigating Shared Ownership with Rc and Weak

To get around the "single owner" rule, we have to stop thinking about Box and start thinking about Rc (Reference Counted). Rc allows multiple owners by keeping track of how many references to a value exist. When the count hits zero, the data is cleaned up. This sounds perfect for a linked list, right? Not quite. If Node A points to Node B, and Node B points back to Node A, their reference counts will never hit zero. You've just created a memory leak in safe Rust.

This is where Weak references come in. A Weak pointer is like an Rc, but it doesn't contribute to the ownership count. In a doubly linked list, the standard pattern is to have the "forward" link be a strong Rc and the "backward" link be a Weak pointer. This breaks the cycle and allows the borrow checker to let the memory be reclaimed when the list is actually dropped.

Handling Interior Mutability with RefCell

Even with Rc, you'll run into another problem: Rc only gives you shared, immutable references. You can't just reach into an Rc and change the next pointer to a new node. This is where it feels like the language is fighting you, but there's a specific tool for this: RefCell.

RefCell implements "interior mutability." It moves the borrow checking from compile-time to runtime. Instead of the compiler proving your code is safe, RefCell tracks borrows while the program is running. If you try to borrow a value mutably while someone else already has a reference to it, the program will panic. It's a trade-off: you lose some compile-time certainty in exchange for the flexibility needed to mutate data structures with complex ownership.

struct Node {
    value: i32,
    next: Option<Rc<RefCell<Node>>>,
    prev: Option<Weak<RefCell<Node>>>,
}

Looking at that type signature—Option<Rc<RefCell<Node>>>—can be daunting at first. It's a lot of wrapping. But think of it as a layer cake: the Option handles the end of the list, the Rc handles the shared ownership, and the RefCell handles the ability to actually change the pointers. Once you get comfortable with this "smart pointer sandwich," you can implement almost any complex data structure in safe Rust.

📋 Practical Task

Implementing a Basic Doubly Linked List Node Linkage

Your task is to implement the logic for linking two nodes together in a doubly linked list using Rc and RefCell. You are provided with the Node struct. You must write a function link_nodes(first: Rc<RefCell<Node>>, second: Rc<RefCell<Node>>) that sets the next pointer of the first node to the second, and the prev pointer of the second node back to the first.

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

struct Node {
    value: i32,
    next: Option<Rc<RefCell<Node>>>,
    prev: Option<Weak<RefCell<Node>>>,
}

impl Node {
    fn new(value: i32) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Node {
            value,
            next: None,
            prev: None,
        }))
    }
}

fn link_nodes(first: Rc<RefCell<Node>>, second: Rc<RefCell<Node>>) {
    // TODO: Implement the bidirectional link here.
    // Remember to use .borrow_mut() to modify the fields.
    // Use Rc::downgrade() to create the Weak pointer for the 'prev' link.
}

fn main() {
    let node1 = Node::new(1);
    let node2 = Node::new(2);

    link_nodes(node1.clone(), node2.clone());

    // Verification
    let n1_borrow = node1.borrow();
    let n2_borrow = node2.borrow();
    
    assert!(n1_borrow.next.is_some());
    assert!(n2_borrow.prev.is_some());
    println!("Nodes successfully linked!");
}