Generic Linked List

Implementing a full-featured generic singly linked list (LinkedList<T>) with $O(1)$ push_front, pop_front, peek, peek_mut, all three standard iterator modes (IntoIter<T>, Iter<'a, T>, IterMut<'a, T>), FromIterator<T>, and an iterative Drop implementation brings together ownership, lifetime elision, and Option::as_deref / Option::take idioms in 100% safe Rust.

Generic `LinkedList<T>` Ownership & Iterator Modes:

  `LinkedList<T>`
    head ---> Box<Node<T>> { elem: T, next: Option<Box<Node<T>>> }
      |
      +-- `into_iter(self)` ---> `IntoIter<T>`       (Pops owned `T` via `pop_front`)
      +-- `iter(&self)`     ---> `Iter<'a, T>`       (Advances `next: Option<&'a Node<T>>`)
      +-- `iter_mut(&mut)`  ---> `IterMut<'a, T>`    (Advances `next: Option<&'a mut Node<T>>`)

Key Idioms Used in Safe `LinkedList<T>`

Operation	Idiom	Why It Works Without `unsafe`
`push_front` / `pop_front`	`self.head.take()`	Replaces `self.head` with `None` and yields the owned `Option<Box<Node<T>>>` in $O(1)$.
`Iter<'a, T>::next`	`self.next.map(\|node\| { self.next = node.next.as_deref(); &node.elem })`	`Option::as_deref()` converts `&Option<Box<Node<T>>>` directly into `Option<&Node<T>>`!
`IterMut<'a, T>::next`	`self.next.take().map(\|node\| { self.next = node.next.as_deref_mut(); &mut node.elem })`	Because `&mut T` is not `Copy`, `self.next.take()` extracts the current `Option<&'a mut Node<T>>` before advancing to `node.next.as_deref_mut()`!
Iterative `Drop`	`while let Some(mut node) = cur { cur = node.next.take(); }`	Unlinks each `Box<Node<T>>` iteratively in $O(1)$ stack space so dropping 1,000,000 nodes never overflows the call stack.

Complete Runnable Implementation

use std::iter::FromIterator;

pub struct LinkedList<T> {
    head: Option<Box<Node<T>>>,
    len: usize,
}

struct Node<T> {
    elem: T,
    next: Option<Box<Node<T>>>,
}

impl<T> Default for LinkedList<T> {
    fn default() -> Self {
        Self::new()
    }
}

impl<T> LinkedList<T> {
    pub const fn new() -> Self {
        Self { head: None, len: 0 }
    }

    pub const fn len(&self) -> usize {
        self.len
    }

    pub const fn is_empty(&self) -> bool {
        self.len == 0
    }

    pub fn push_front(&mut self, elem: T) {
        self.head = Some(Box::new(Node {
            elem,
            next: self.head.take(),
        }));
        self.len += 1;
    }

    pub fn pop_front(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            self.head = node.next;
            self.len -= 1;
            node.elem
        })
    }

    pub fn peek(&self) -> Option<&T> {
        self.head.as_ref().map(|node| &node.elem)
    }

    pub fn peek_mut(&mut self) -> Option<&mut T> {
        self.head.as_mut().map(|node| &mut node.elem)
    }

    /// Reverses the linked list in-place in O(n) time and O(1) auxiliary memory!
    pub fn reverse(&mut self) {
        let mut prev = None;
        let mut current = self.head.take();
        while let Some(mut boxed_node) = current {
            let next = boxed_node.next.take();
            boxed_node.next = prev;
            prev = Some(boxed_node);
            current = next;
        }
        self.head = prev;
    }

    pub fn iter(&self) -> Iter<'_, T> {
        Iter {
            next: self.head.as_deref(),
        }
    }

    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
        IterMut {
            next: self.head.as_deref_mut(),
        }
    }
}

impl<T> Drop for LinkedList<T> {
    fn drop(&mut self) {
        let mut cur = self.head.take();
        while let Some(mut boxed) = cur {
            cur = boxed.next.take();
        }
    }
}

pub struct IntoIter<T>(LinkedList<T>);

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.pop_front()
    }
}

pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        let node = self.next?;
        self.next = node.next.as_deref();
        Some(&node.elem)
    }
}

pub struct IterMut<'a, T> {
    next: Option<&'a mut Node<T>>,
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        let node = self.next.take()?;
        self.next = node.next.as_deref_mut();
        Some(&mut node.elem)
    }
}

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

impl<'a, T> IntoIterator for &'a LinkedList<T> {
    type Item = &'a T;
    type IntoIter = Iter<'a, T>;
    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

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

impl<T> FromIterator<T> for LinkedList<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let mut list = Self::new();
        for item in iter {
            list.push_front(item);
        }
        list.reverse();
        list
    }
}

fn main() {
    let mut list: LinkedList<i32> = [10, 20, 30].into_iter().collect();
    assert_eq!(list.len(), 3);

    // Mutate all elements in-place via `IterMut`:
    for val in &mut list {
        *val += 5;
    }

    // Reverse in-place in O(1) memory:
    list.reverse();

    let collected: Vec<i32> = list.into_iter().collect();
    assert_eq!(collected, vec![35, 25, 15]);
    println!("Generic LinkedList after +5 and in-place reverse: {collected:?}");
}

Generic LinkedList after +5 and in-place reverse: [35, 25, 15]

Key Idioms Used in Safe LinkedList<T>

Complete Runnable Implementation

Key Idioms Used in Safe `LinkedList<T>`