How do I keep a mutable reference to the last node while building a linked list?

Question

I'm trying to implement building a singly-linked list from an Iterator, keeping the order of elements.

The structure is defined as:

#[derive(Debug)]
struct List<T> {
    list: Node<T>,
}

type Node<T> = Option<Box<Link<T>>>;

#[derive(Debug)]
struct Link<T> {
    head: T,
    tail: Node<T>,
}

I was thinking of keeping a mutable reference to the end of the list and expanding it while iterating. However, I couldn't figure out how this could be done. The (non-working) idea was:

impl<T> List<T> {
    pub fn from_iterator(i: &mut Iterator<Item = T>) -> Self {
        let mut list = List { list: None };
        {
            let mut last: &mut Node<T> = &mut list.list;
            for x in i {
                let singleton = Box::new(Link {
                    head: x,
                    tail: None,
                });
                *last = Some(singleton);
                // --> I aim for something like the line below. Of course
                // 'singleton' can't be accessed at this point, but even if I
                // match on *last to retrieve it, still I couldn't figure out how
                // to properly reference the new tail.
                // last = &mut singleton.tail;
            }
        }
        list
    }
}

It'd be possible to just build the list in reverse and then reverse it afterwards with the same time complexity, but I was curious if the above approach is ever possible in Rust.

Answer 1

As described in Cannot obtain a mutable reference when iterating a recursive structure: cannot borrow as mutable more than once at a time, you can explicitly transfer ownership of the mutable reference using {}:

impl<T> List<T> {
    pub fn from_iterator<I>(i: I) -> Self
    where
        I: IntoIterator<Item = T>,
    {
        let mut list = List { list: None };
        {
            let mut last: &mut Node<T> = &mut list.list;

            for x in i {
                let singleton = Box::new(Link {
                    head: x,
                    tail: None,
                });
                *last = Some(singleton);

                last = &mut {last}.as_mut().unwrap().tail;
            }
        }
        list
    }
}

I also removed the trait object (&mut Iterator) in favor of a generic. This allows for more optimized code (although with a linked list it's probably not worth it).

It's unfortunate that the unwrap is needed. Even though the Link is placed on the heap, making the address stable, the compiler does not perform that level of lifetime tracking. One could use unsafe code based on this external knowledge, but I don't know that it's worth it here.

Answer 2

I'm not sure you can do it in a loop. The borrow checker might not be smart enough. You can do it with recursion though.

impl<T> List<T> {
    pub fn from_iterator(i: &mut Iterator<Item = T>) -> Self {
        let mut list = List { list: None };
        Self::append_from_iterator(&mut list.list, i);
        list
    }
    pub fn append_from_iterator(list: &mut Node<T>, i: &mut Iterator<Item = T>) {
        match i.next() {
            Some(x) => {
                let mut singleton = Box::new(Link {
                    head: x,
                    tail: None,
                });
                Self::append_from_iterator(&mut singleton.tail, i);
                *list = Some(singleton);
            }, 
            None => (),
        }

    }
}

playground