Looking for an idiomatic way to build a singly-linked list in Rust iteratively, with a step-by-step debug print?

Question

I'd like to iteratively debug print a singly-linked list as it builds, but I can't find a legal way to borrow.

Am I coming at the problem in a way that's too object oriented? Do I need to abandon safe rust or use RefCell for something so simple?

fn main() {
    let mut list = Some(Box::new(List { val: 0, next: None }));
    let mut current = &mut list;
    for i in 1..10 {
        let next = Box::new(List { val: i, next: None });
        current.as_mut().unwrap().next = Some(next);
        current = &mut current.as_mut().unwrap().next;
        // dbg!(list); Illegal!
    }
}

#[derive(Debug, Clone)]
struct List {
    val: i32,
    next: Option<Box<List>>,
}

Answer 1

This is certainly not possible without using smart pointers.

To accomplish this we must have:

1. A reference to the head of the list
2. A reference to the tail of the list
3. The ability to mutate the value referred to by #2

Simple pointers don't work for #1 and #2 because the problem requires multiple references & mutation access to our list. The borrow checker is meant to prevent this.

Rc can be used to allow multiple references, & Cell can be used to allow mutation of the pointee.

With this in mind, my List struct needs to look like this.

#[derive(Clone, Default)]
struct List {
    val: i32,
    next: Option<Rc<Cell<List>>>,
}

// Cell does't implement `Debug` so a manual implementation is necessary
// Make sure you don't accidentally mutate the value in the `Cell`...
impl fmt::Debug for List {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut dbg = &mut f.debug_struct("List");
        dbg = dbg.field("val", &self.val);
        if let Some(next) = self.next.clone() {
            let taken = next.take();
            dbg = dbg.field("next", &taken);
            next.set(taken);
        } else {
            dbg = dbg.field("next", &Option::<()>::None)
        }
        return dbg.finish();
    }
}

& the code to iteratively build and print now looks like this.

use std::{
    cell::Cell,
    fmt::{self},
    rc::Rc,
};

fn main() {
    let list = List { val: 0, next: None };
    let head = Rc::new(Cell::new(list));
    let mut tail = head.clone();
    for i in 1..10 {
        // Create the new node
        let next = Rc::new(Cell::new(List { val: i, next: None }));
        // Add the new node to the node `tail` currently references
        tail.set((|| {
            let mut taken = tail.take();
            taken.next = Some(next.clone());
            return taken;
        })());
        // Update `tail` to reference the node we just added
        tail = next.clone();
        // Print the whole list
        head.set((|| {
            let taken = head.take();
            dbg!(&taken);
            return taken;
        })());
    }
}

We now get the desired output as the list is built.

[main.rs:25:13] &taken = List {
    val: 0,
    next: List {
        val: 1,
        next: None,
    },
}
[main.rs:25:13] &taken = List {
    val: 0,
    next: List {
        val: 1,
        next: List {
            val: 2,
            next: None,
        },
    },
}