Boring Combinatorics

Now the mechanical accessors. front, front_mut, back, back_mut. Then three iterators: by-value (IntoIter), by-shared-ref (Iter), by-mutable-ref (IterMut). The pattern is identical to Chapter 2; the only difference is dereferencing NonNull<Node<T>> instead of pattern-matching on a safe enum.

front/back return Option<&T>. We turn Option<NonNull<Node<T>>> into Option<&T> via map(|node| unsafe { &(*node.as_ptr()).elem }). The _mut versions use &mut instead. The lifetime of the returned reference is tied to &self (or &mut self) by elision — the compiler will not let it escape past the next mutation.

impl<T> LinkedList<T> {
    pub fn front(&self) -> Option<&T> {
        unsafe { self.front.map(|n| &(*n.as_ptr()).elem) }
    }

    pub fn front_mut(&mut self) -> Option<&mut T> {
        unsafe { self.front.map(|n| &mut (*n.as_ptr()).elem) }
    }

    pub fn back(&self) -> Option<&T> {
        unsafe { self.back.map(|n| &(*n.as_ptr()).elem) }
    }

    pub fn back_mut(&mut self) -> Option<&mut T> {
        unsafe { self.back.map(|n| &mut (*n.as_ptr()).elem) }
    }
}

Iter<'a, T> walks shared references. Hold a current pointer and a remaining-count; each call to next reads elem, advances along back, decrements the count. The shared-borrow lifetime 'a ties the iterator's references to the original list. PhantomData<&'a Node<T>> carries it.

pub struct Iter<'a, T> {
    front: Option<NonNull<Node<T>>>,
    back: Option<NonNull<Node<T>>>,
    len: usize,
    _marker: PhantomData<&'a Node<T>>,
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<&'a T> {
        if self.len == 0 { return None; }
        unsafe {
            self.front.map(|n| {
                self.len -= 1;
                self.front = (*n.as_ptr()).back;
                &(*n.as_ptr()).elem
            })
        }
    }
}

impl<T> LinkedList<T> {
    pub fn iter(&self) -> Iter<'_, T> {
        Iter { front: self.front, back: self.back, len: self.len, _marker: PhantomData }
    }
}

IterMut is the same shape with &'a mut T and PhantomData<&'a mut Node<T>>. The reason this is sound — and not aliasing-violating — is that the iterator holds an exclusive borrow of the whole list, never hands out two references to the same node, and walks linearly. Miri verifies this; we'll run it in the testing section.

pub struct IterMut<'a, T> {
    front: Option<NonNull<Node<T>>>,
    back: Option<NonNull<Node<T>>>,
    len: usize,
    _marker: PhantomData<&'a mut Node<T>>,
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<&'a mut T> {
        if self.len == 0 { return None; }
        unsafe {
            self.front.map(|n| {
                self.len -= 1;
                self.front = (*n.as_ptr()).back;
                &mut (*n.as_ptr()).elem
            })
        }
    }
}

IntoIter is a LinkedList<T> with a shim. It holds the original list by value and delegates next to pop_front, next_back to pop_back. That gets us DoubleEndedIterator for free and ensures the destructor runs on whatever's left if iteration stops early.

pub struct IntoIter<T> { list: LinkedList<T> }

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<T> { self.list.pop_front() }
    fn size_hint(&self) -> (usize, Option<usize>) { (self.list.len, Some(self.list.len)) }
}

impl<T> DoubleEndedIterator for IntoIter<T> {
    fn next_back(&mut self) -> Option<T> { self.list.pop_back() }
}

impl<T> IntoIterator for LinkedList<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;
    fn into_iter(self) -> IntoIter<T> { IntoIter { list: self } }
}