Iterator structs

A collection should not have to become its own iterator. A separate iterator struct holds traversal state while the collection keeps its role as a collection. For a linked list, this also lets callers traverse items without exposing the links between nodes. section 3.2.4

Three iterator structs distinguish how callers use the list:

• `Iter` supports `iter(&self)` for shared access. section 3.2.4
• `IterMut` supports `iter_mut(&mut self)` for mutable access. section 3.2.4
• `IntoIter` supports `into_iter(self)`, which consumes the list and yields owned items. section 3.2.4

struct Iter<T> {
    next: Option<ListItemPtr<T>>,
}
struct IterMut<T> {
    next: Option<ListItemPtr<T>>,
}
struct IntoIter<T> {
    next: Option<ListItemPtr<T>>,
}

Each struct starts with an `Option` pointing to the next list item. Its `Iterator::next` implementation advances that state and returns an item or `None`. section 3.2.4

The access modes affect what `next` can return. The first implementation clones shared item data for both `Iter` and `IterMut`; their names alone do not make the results `&T` and `&mut T`. Consuming iteration instead tries to unwrap `Rc` pointers to recover owned values. The later borrowed-reference implementation adds lifetimes and `PhantomData`, then uses unsafe pointer dereferences. That code needs a separate safety justification: an iterator struct does not, by itself, make returned references valid. section 3.2.4

impl<'a, T> IntoIterator for &'a LinkedList<T> {
    type IntoIter = Iter<'a, T>;
    type Item = &'a T;
    fn into_iter(self) -> Self::IntoIter {
        self.iter()       #1
    }
}
impl<'a, T> IntoIterator for &'a mut LinkedList<T> {
    type IntoIter = IterMut<'a, T>;
    type Item = &'a mut T;
    fn into_iter(self) -> Self::IntoIter {
        self.iter_mut()      #2
    }
}
impl<T> IntoIterator for LinkedList<T> {     #3
    type IntoIter = IntoIter<T>;
    type Item = T;
    fn into_iter(self) -> Self::IntoIter {
        self.into_iter()        #4
    }
}

Implementing `IntoIterator` for `&LinkedList<T>`, `&mut LinkedList<T>`, and `LinkedList<T>` connects the three structs to `for` loops and the usual borrowed, mutably borrowed, and consuming forms of iteration. section 3.2.4

If these methods form a public library API, their return types must be public too. An external test catches the mistake: a public `iter` method returning private `Iter` fails to compile. Keep the list's internal fields private while making the intended collection methods and iterator types visible. section 6.11.1