Search⌘ K
AI Features
Home
Courses
Rust Brain Teasers

Puzzle 15: Explanation

Explore how linked lists work in Rust, focusing on dynamic memory management using Rc and RefCell. Understand reference counting and cyclic reference challenges, and learn why Rust's standard LinkedList is preferred for safe and efficient list operations.

We'll cover the following...

Test it out

Hit “Run” to see the code’s output.

C++
use std::cell::RefCell;
use std::rc::Rc;
type Link = Option<Rc<RefCell<Node>>>;
#[derive(Debug)]
struct Node {
    elem: i32,
    next: Link,
}
fn main() {
    let mut head = Some(Rc::new(
        RefCell::new(Node{ elem: 1, next: None })
    ));
    head
        .as_mut()
        .unwrap()
        .borrow_mut()
        .next = Some(Rc::new(RefCell::new(
            Node{ elem: 2, next: head.clone() })
        ));
    println!("{:?}", head);
}

Output

The program will display node 1, node 2, and then node 1 again. The output repeats itself until the program exits and displays the following message: thread 'main' has overflowed its stack.

Explanation

The conceptually simple linked lists are one of the first dynamic data structures people encounter in computer science classes. In linked lists, each entry contains a pointer to the next entry. This allows us to easily insert items into the middle of the list. We do that by finding the insertion point and copying its next pointer to the new element. If we change the previous entry’s next to our new entry, we insert it into the middle of our list without rearranging existing nodes. We can iterate a linked list by following each node’s pointer to the next item. We can visualize a linked list like this:

The Next ...