Linked Lists

A linked list stores elements in separately allocated nodes linked together by pointers (next and prev). In Rust, implementing a linked list is a classic study in ownership and aliasing rules, while in practical performance engineering, Vec<T> and VecDeque<T> almost always outperform std::collections::LinkedList<T> due to CPU cache locality.

1. Singly Linked List (`Option<Box<Node<T>>>` — Strict Tree Ownership):
   head ---> [ val: 10 | next ] ---> [ val: 20 | next ] ---> None
   (Each node has 1 unique owner; 100% safe Rust without `unsafe` or `RefCell`!)

2. Doubly Linked List (`prev` and `next` pointers point to each other):
   None <--- [ prev | val: 10 | next ] <===> [ prev | val: 20 | next ] ---> None
   (Cyclic aliasing: requires raw pointers `NonNull<Node<T>>` or Arena indices!)

Why Singly Linked Lists Are Trivial in Safe Rust (Option<Box<Node<T>>>)

In a singly linked stack or list, each node is owned by exactly one predecessor (head owns node 0, node 0 owns node 1, etc.). Because ownership forms a strict DAG/tree with no cycles, Option<Box<Node<T>>> expresses a singly linked list in 100% safe Rust.

However, one subtle detail in recursive structs is Drop stack overflow: if a list has 1,000,000 nodes, the compiler's default recursive Drop implementation would recurse 1,000,000 stack frames deep! Implementing an iterative Drop loop pops Box nodes one by one in $O(1)$ stack space:

pub struct SinglyLinkedList<T> {
    head: Link<T>,
    len: usize,
}

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

struct Node<T> {
    elem: T,
    next: Link<T>,
}

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

    pub fn push_front(&mut self, elem: T) {
        let new_node = Box::new(Node {
            elem,
            // `take()` replaces `self.head` with `None` and returns the old head in O(1)!
            next: self.head.take(),
        });
        self.head = Some(new_node);
        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_front(&self) -> Option<&T> {
        self.head.as_ref().map(|node| &node.elem)
    }

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

/// Iterative `Drop` prevents stack overflow even if the list contains millions of nodes!
impl<T> Drop for SinglyLinkedList<T> {
    fn drop(&mut self) {
        let mut cur_link = self.head.take();
        while let Some(mut boxed_node) = cur_link {
            cur_link = boxed_node.next.take();
            // `boxed_node` drops here with `next == None`, so no recursive drop occurs!
        }
    }
}

fn main() {
    let mut list = SinglyLinkedList::new();
    list.push_front(10);
    list.push_front(20);
    list.push_front(30);

    assert_eq!(list.len(), 3);
    assert_eq!(list.peek_front(), Some(&30));
    assert_eq!(list.pop_front(), Some(30));
    assert_eq!(list.pop_front(), Some(20));

    println!("Remaining front element: {:?}", list.peek_front());
}

Remaining front element: Some(10)

Why Doubly Linked Lists Are Hard in Safe Rust (and Alternatives)

In a doubly linked list, Node A's next points to Node B, and Node B's prev points back to Node A. Because two nodes point to each other simultaneously while supporting mutation, Rust's single-owner Box<T> cannot represent both edges directly.