Iterator for a Linked List in Rust

Question

I am new to Rust and am trying to learn it. I've read a bunch of different material and believe I have the gist of important concepts like the borrow checker, references, lifetimes, smart pointers, etc. But I am having a difficult time trying to understand more abstruse concepts like RefCell, Mutexes, Pin, etc., to be able to actually code with these data structures. It's all very abstract to me.

1. Where can I learn more about items like these to actually code with them?
2. I have a particular question about implementing the Iterator trait to iterate references inside a RefCell for a LinkedList data structure I have coded and can't seem to get to work because it causes issues with temporary borrows and the like, and I haven't got the slightest clue how to approach these problems to work around said issues.

Nonetheless, here is my code:

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

type LinkNodePtr<T> = Rc<RefCell<LinkNode<T>>>;

pub struct LinkNode<T> {
    data: T,
    next: Option<LinkNodePtr<T>>,
    prev: Option<LinkNodePtr<T>>,
}

#[derive(Debug)]
pub struct LinkedList<T> {
    head: Option<LinkNodePtr<T>>,
    tail: Option<LinkNodePtr<T>>,
    len: usize,
}

impl<'a, T> LinkedList<T> {
    pub fn new(data: T) -> Self {
        let link_node_ptr = Rc::new(RefCell::new(LinkNode {
            data,
            next: None,
            prev: None,
        }));

        LinkedList {
            head: Some(Rc::clone(&link_node_ptr)),
            tail: Some(Rc::clone(&link_node_ptr)),
            len: 1,
        }
    }

    pub fn add_to_head(&mut self, data: T) {
        let link_node_ptr = Rc::new(RefCell::new(LinkNode {
            data,
            next: self.head.take(),
            prev: None,
        }));

        self.head = Some(Rc::clone(&link_node_ptr));

        let link_node = link_node_ptr.borrow_mut();
        if let Some(ref link_node_ptr_next) = link_node.next {
            let mut link_node_next = (*link_node_ptr_next).borrow_mut();
            link_node_next.prev = Some(Rc::clone(&link_node_ptr));
        }

        self.len += 1;
    }

    pub fn add_to_tail(&mut self, data: T) {
        let link_node_ptr = Rc::new(RefCell::new(LinkNode {
            data,
            next: None,
            prev: self.tail.take(),
        }));

        self.tail = Some(Rc::clone(&link_node_ptr));

        let link_node = link_node_ptr.borrow();
        if let Some(ref link_node_ptr_prev) = link_node.prev {
            let mut link_node_prev = (*link_node_ptr_prev).borrow_mut();
            link_node_prev.next = Some(Rc::clone(&link_node_ptr));
        }

        self.len += 1;
    }

    pub fn iter(&'a self) -> LinkedListIter<'a, T> {
        let current = if let Some(ref head) = self.head {
            Some(head.borrow())
        } else {
            None
        };
        LinkedListIter { current }
    }
}

pub struct LinkedListIter<'a, T> {
    current: Option<Ref<'a, LinkNode<T>>>,
}

impl<'a, T> Iterator for LinkedListIter<'a, T> {
    type Item = Ref<'a, T>;

    fn next(&mut self) -> Option<Self::Item> {
        if let Some(link_node) = self.current.take() {
            self.current = if let Some(ref link_node_ptr_next) = link_node.next {
                let link_node_next = (*link_node_ptr_next).borrow();
                Some(link_node_next)
            } else {
                None
            };
            Some(Ref::map(link_node, |x| &x.data))
        } else {
            None
        }
    }
}

impl<'a, T> std::fmt::Debug for LinkNode<T>
where
    T: std::fmt::Debug,
{
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("LinkNode")
            .field("data", &self.data)
            .field("next", &self.next)
            .finish()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn it_works() {
        let mut ll = LinkedList::new(1);
        ll.add_to_tail(2);
        ll.add_to_tail(3);
        ll.add_to_tail(4);
        ll.add_to_head(5);
        ll.add_to_head(6);

        for x in ll.iter() {
            println!("{}", x);
        }

        println!("{:?}", ll);
    }
}

error[E0505]: cannot move out of `link_node` because it is borrowed
  --> src\linked_list.rs:97:27
   |
86 | impl<'a, T> Iterator for LinkedListIter<'a, T> {
   |      -- lifetime `'a` defined here
...
91 |             self.current = if let Some(ref link_node_ptr_next) = link_node.next {
   |                                                                  --------- borrow of `link_node` occurs here
92 |                 let link_node_next = (*link_node_ptr_next).borrow();
   |                                      ------------------------------ argument requires that `link_node` is borrowed for `'a`
...
97 |             Some(Ref::map(link_node, |x| &x.data))
   |                           ^^^^^^^^^ move out of `link_node` occurs here

Answer 1

I'm afraid it won't work with lifetime annotations, because the lifetime of every node is different. That's exactly why linked lists in Rust are so hard, and much of that is layed out in "Learn Rust With Entirely Too Many Linked Lists", which is an excellent read and almost mandatory if you want to deal with recursive data structures like linked lists.

To fix your problem, instead of holding Ref values to the next item, hold the Rc itself. That's what Rc is for.

That said, it's currently impossible to return a value from an iterator that borrows the iterator itself. That makes it impossible to return a Ref from an iterator, as a Ref must always be connected to a RefCell via a lifetime, and the RefCell would have to be stored inside the iterator.

So right now, I'm afraid I have to tell you that your approach isn't possible without unsafe (to my knowledge).

The 'Entirely too many linked lists' article seems to agree, it has an entire chapter about Rc<RefCell<T>> based doubly-linked lists and how they are incompatible with iterators.

TLDR: Don't try to write linked lists in Rust. It's a concept that simply isn't compatible with Rusts ownership rules. If you want to do it anyway, read "Learn Rust With Entirely Too Many Linked Lists" first.