Rust Brain Teasers/

...

/

Puzzle 15: Explanation

Puzzle 15: Explanation

Let’s learn how references and linked lists work in Rust.

We'll cover the following...

Test it out

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

Press + to interact
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 field in each node is an ...