Linked Lists

Linked lists are linear data structures where elements are stored in nodes, with each node containing data and a reference to the next node. Unlike arrays, linked lists don't require contiguous memory allocation.

The Rust perspective:

• Linked lists are notoriously difficult in Rust due to ownership rules
• Single ownership makes doubly-linked lists challenging
• Several approaches exist, each with trade-offs
• std::collections::LinkedList exists but is rarely the best choice

// The classic challenge: This won't compile!
struct BadNode<T> {
    data: T,
    next: Option<Box<BadNode<T>>>,
    prev: Option<Box<BadNode<T>>>,  // Can't have two owners!
}

// Solutions exist, but require careful design

Rare in Rust! Prefer Vec for most cases. Appropriate use cases:

1. Frequent insertions/deletions at arbitrary positions
2. Implementing queues, stacks, or deques
3. Memory-constrained environments (no reallocation)
4. When you need stable pointers to elements
5. Building more complex data structures

When to use Vec instead:

1. Random access needed
2. Cache-friendly iteration required
3. Append-only or mostly-read workloads
4. Simple, idiomatic code preferred

A safe, ownership-based singly linked list.

/// A singly linked list with Box-based ownership
#[derive(Debug)]
pub struct SinglyLinkedList<T> {
    head: Link<T>,
    len: usize,
}

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

#[derive(Debug)]
struct Node<T> {
    data: T,
    next: Link<T>,
}

impl<T> SinglyLinkedList<T> {
    /// Create an empty list
    pub fn new() -> Self {
        Self { head: None, len: 0 }
    }

    /// Check if the list is empty
    pub fn is_empty(&self) -> bool {
        self.head.is_none()
    }

    /// Get the length of the list
    pub fn len(&self) -> usize {
        self.len
    }

    /// Push an element to the front (O(1))
    pub fn push_front(&mut self, data: T) {
        let new_node = Box::new(Node {
            data,
            next: self.head.take(),
        });
        self.head = Some(new_node);
        self.len += 1;
    }

    /// Pop an element from the front (O(1))
    pub fn pop_front(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            self.head = node.next;
            self.len -= 1;
            node.data
        })
    }

    /// Peek at the front element (O(1))
    pub fn peek_front(&self) -> Option<&T> {
        self.head.as_ref().map(|node| &node.data)
    }

    /// Peek at the front element mutably (O(1))
    pub fn peek_front_mut(&mut self) -> Option<&mut T> {
        self.head.as_mut().map(|node| &mut node.data)
    }

    /// Push an element to the back (O(n))
    pub fn push_back(&mut self, data: T) {
        let new_node = Box::new(Node { data, next: None });

        // Find the last node
        let mut current = &mut self.head;
        while let Some(ref mut node) = current {
            current = &mut node.next;
        }

        *current = Some(new_node);
        self.len += 1;
    }

    /// Pop an element from the back (O(n))
    pub fn pop_back(&mut self) -> Option<T> {
        if self.head.is_none() {
            return None;
        }

        // Special case: only one element
        if self.head.as_ref().unwrap().next.is_none() {
            self.len -= 1;
            return self.head.take().map(|node| node.data);
        }

        // Find the second-to-last node
        let mut current = &mut self.head;
        while current.as_ref().unwrap().next.as_ref().unwrap().next.is_some() {
            current = &mut current.as_mut().unwrap().next;
        }

        self.len -= 1;
        current
            .as_mut()
            .unwrap()
            .next
            .take()
            .map(|node| node.data)
    }

    /// Get element at index (O(n))
    pub fn get(&self, index: usize) -> Option<&T> {
        if index >= self.len {
            return None;
        }

        let mut current = &self.head;
        for _ in 0..index {
            current = &current.as_ref()?.next;
        }

        current.as_ref().map(|node| &node.data)
    }

    /// Insert at index (O(n))
    pub fn insert(&mut self, index: usize, data: T) -> Result<(), &'static str> {
        if index > self.len {
            return Err("Index out of bounds");
        }

        if index == 0 {
            self.push_front(data);
            return Ok(());
        }

        let mut current = &mut self.head;
        for _ in 0..index - 1 {
            current = &mut current.as_mut().ok_or("Index out of bounds")?.next;
        }

        let new_node = Box::new(Node {
            data,
            next: current.as_mut().unwrap().next.take(),
        });

        current.as_mut().unwrap().next = Some(new_node);
        self.len += 1;
        Ok(())
    }

    /// Remove at index (O(n))
    pub fn remove(&mut self, index: usize) -> Option<T> {
        if index >= self.len {
            return None;
        }

        if index == 0 {
            return self.pop_front();
        }

        let mut current = &mut self.head;
        for _ in 0..index - 1 {
            current = &mut current.as_mut()?.next;
        }

        let removed = current.as_mut()?.next.take()?;
        current.as_mut()?.next = removed.next;
        self.len -= 1;
        Some(removed.data)
    }

    /// Reverse the list in place (O(n))
    pub fn reverse(&mut self) {
        let mut prev = None;
        let mut current = self.head.take();

        while let Some(mut node) = current {
            let next = node.next.take();
            node.next = prev;
            prev = Some(node);
            current = next;
        }

        self.head = prev;
    }

    /// Create an iterator
    pub fn iter(&self) -> Iter<'_, T> {
        Iter {
            current: self.head.as_deref(),
        }
    }

    /// Create a mutable iterator
    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
        IterMut {
            current: self.head.as_deref_mut(),
        }
    }
}

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

impl<T> Drop for SinglyLinkedList<T> {
    fn drop(&mut self) {
        // Iteratively drop to avoid stack overflow on large lists
        let mut current = self.head.take();
        while let Some(mut node) = current {
            current = node.next.take();
        }
    }
}

/// Immutable iterator
pub struct Iter<'a, T> {
    current: Option<&'a Node<T>>,
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.current.map(|node| {
            self.current = node.next.as_deref();
            &node.data
        })
    }
}

/// Mutable iterator
pub struct IterMut<'a, T> {
    current: 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> {
        self.current.take().map(|node| {
            self.current = node.next.as_deref_mut();
            &mut node.data
        })
    }
}

/// Consuming iterator
pub struct IntoIter<T> {
    list: SinglyLinkedList<T>,
}

impl<T> Iterator for IntoIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.list.pop_front()
    }
}

impl<T> IntoIterator for SinglyLinkedList<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;

    fn into_iter(self) -> Self::IntoIter {
        IntoIter { list: self }
    }
}

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

fn main() {
    let mut list = SinglyLinkedList::new();

    // Push elements
    list.push_front(3);
    list.push_front(2);
    list.push_front(1);
    list.push_back(4);
    list.push_back(5);

    println!("List: {:?}", list.iter().collect::<Vec<_>>());
    println!("Length: {}", list.len());

    // Access elements
    println!("Front: {:?}", list.peek_front());
    println!("Index 2: {:?}", list.get(2));

    // Remove elements
    println!("Pop front: {:?}", list.pop_front());
    println!("Pop back: {:?}", list.pop_back());
    println!("After pops: {:?}", list.iter().collect::<Vec<_>>());

    // Insert and remove
    list.insert(1, 10).unwrap();
    println!("After insert at 1: {:?}", list.iter().collect::<Vec<_>>());

    list.remove(1);
    println!("After remove at 1: {:?}", list.iter().collect::<Vec<_>>());

    // Reverse
    list.reverse();
    println!("Reversed: {:?}", list.iter().collect::<Vec<_>>());

    // Iterate
    println!("\nIteration:");
    for item in &list.iter().collect::<Vec<_>>() {
        println!("  {}", item);
    }
}

A doubly linked list using reference counting for shared ownership.

use std::cell::RefCell;
use std::rc::{Rc, Weak};
use std::fmt;

/// Doubly linked list with interior mutability
pub struct DoublyLinkedList<T> {
    head: Link<T>,
    tail: Link<T>,
    len: usize,
}

type Link<T> = Option<Rc<RefCell<Node<T>>>>;
type WeakLink<T> = Option<Weak<RefCell<Node<T>>>>;

struct Node<T> {
    data: T,
    next: Link<T>,
    prev: WeakLink<T>,
}

impl<T> Node<T> {
    fn new(data: T) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Self {
            data,
            next: None,
            prev: None,
        }))
    }
}

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

    pub fn is_empty(&self) -> bool {
        self.head.is_none()
    }

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

    /// Push to front (O(1))
    pub fn push_front(&mut self, data: T) {
        let new_node = Node::new(data);

        match self.head.take() {
            Some(old_head) => {
                old_head.borrow_mut().prev = Some(Rc::downgrade(&new_node));
                new_node.borrow_mut().next = Some(old_head);
            }
            None => {
                self.tail = Some(Rc::clone(&new_node));
            }
        }

        self.head = Some(new_node);
        self.len += 1;
    }

    /// Push to back (O(1))
    pub fn push_back(&mut self, data: T) {
        let new_node = Node::new(data);

        match self.tail.take() {
            Some(old_tail) => {
                new_node.borrow_mut().prev = Some(Rc::downgrade(&old_tail));
                old_tail.borrow_mut().next = Some(Rc::clone(&new_node));
            }
            None => {
                self.head = Some(Rc::clone(&new_node));
            }
        }

        self.tail = Some(new_node);
        self.len += 1;
    }

    /// Pop from front (O(1))
    pub fn pop_front(&mut self) -> Option<T> {
        self.head.take().map(|old_head| {
            match old_head.borrow_mut().next.take() {
                Some(new_head) => {
                    new_head.borrow_mut().prev = None;
                    self.head = Some(new_head);
                }
                None => {
                    self.tail = None;
                }
            }
            self.len -= 1;

            Rc::try_unwrap(old_head)
                .ok()
                .expect("Node still has references")
                .into_inner()
                .data
        })
    }

    /// Pop from back (O(1))
    pub fn pop_back(&mut self) -> Option<T> {
        self.tail.take().map(|old_tail| {
            match old_tail.borrow_mut().prev.take() {
                Some(weak_prev) => {
                    if let Some(new_tail) = weak_prev.upgrade() {
                        new_tail.borrow_mut().next = None;
                        self.tail = Some(new_tail);
                    }
                }
                None => {
                    self.head = None;
                }
            }
            self.len -= 1;

            Rc::try_unwrap(old_tail)
                .ok()
                .expect("Node still has references")
                .into_inner()
                .data
        })
    }

    /// Peek front
    pub fn peek_front(&self) -> Option<std::cell::Ref<'_, T>> {
        self.head
            .as_ref()
            .map(|node| std::cell::Ref::map(node.borrow(), |n| &n.data))
    }

    /// Peek back
    pub fn peek_back(&self) -> Option<std::cell::Ref<'_, T>> {
        self.tail
            .as_ref()
            .map(|node| std::cell::Ref::map(node.borrow(), |n| &n.data))
    }

    /// Iterate from front to back
    pub fn iter(&self) -> impl Iterator<Item = std::cell::Ref<'_, T>> {
        DoublyLinkedListIter {
            current: self.head.clone(),
        }
    }

    /// Iterate from back to front
    pub fn iter_back(&self) -> impl Iterator<Item = std::cell::Ref<'_, T>> {
        DoublyLinkedListIterBack {
            current: self.tail.clone(),
        }
    }

    /// Clear the list
    pub fn clear(&mut self) {
        while self.pop_front().is_some() {}
    }
}

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

impl<T> Drop for DoublyLinkedList<T> {
    fn drop(&mut self) {
        self.clear();
    }
}

struct DoublyLinkedListIter<T> {
    current: Link<T>,
}

impl<T> Iterator for DoublyLinkedListIter<T> {
    type Item = std::cell::Ref<'static, T>;

    fn next(&mut self) -> Option<Self::Item> {
        // Note: This is a simplified version. Real implementation
        // would need to handle lifetimes differently.
        self.current.take().map(|node| {
            let next = node.borrow().next.clone();
            self.current = next;
            // This is unsafe in general; shown for educational purposes
            unsafe {
                std::mem::transmute::<std::cell::Ref<'_, T>, std::cell::Ref<'static, T>>(
                    std::cell::Ref::map(node.borrow(), |n| &n.data)
                )
            }
        })
    }
}

struct DoublyLinkedListIterBack<T> {
    current: Link<T>,
}

impl<T> Iterator for DoublyLinkedListIterBack<T> {
    type Item = std::cell::Ref<'static, T>;

    fn next(&mut self) -> Option<Self::Item> {
        self.current.take().map(|node| {
            let prev = node.borrow().prev.clone().and_then(|w| w.upgrade());
            self.current = prev;
            unsafe {
                std::mem::transmute::<std::cell::Ref<'_, T>, std::cell::Ref<'static, T>>(
                    std::cell::Ref::map(node.borrow(), |n| &n.data)
                )
            }
        })
    }
}

impl<T: fmt::Debug> fmt::Debug for DoublyLinkedList<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut list = f.debug_list();
        let mut current = self.head.clone();
        while let Some(node) = current {
            list.entry(&node.borrow().data);
            current = node.borrow().next.clone();
        }
        list.finish()
    }
}

fn main() {
    let mut list = DoublyLinkedList::new();

    // Test push operations
    list.push_back(1);
    list.push_back(2);
    list.push_back(3);
    list.push_front(0);

    println!("List: {:?}", list);
    println!("Length: {}", list.len());

    // Test peek
    println!("Front: {:?}", list.peek_front().map(|r| *r));
    println!("Back: {:?}", list.peek_back().map(|r| *r));

    // Test pop operations
    println!("Pop front: {:?}", list.pop_front());
    println!("Pop back: {:?}", list.pop_back());
    println!("After pops: {:?}", list);

    // Clear
    list.clear();
    println!("After clear: {:?}", list);
    println!("Is empty: {}", list.is_empty());
}

An intrusive list where nodes embed the link pointers, used in kernel/embedded programming.

use std::ptr::NonNull;
use std::marker::PhantomData;

/// Intrusive list link - embed this in your struct
#[derive(Debug)]
pub struct IntrusiveLink<T> {
    next: Option<NonNull<T>>,
    prev: Option<NonNull<T>>,
}

impl<T> IntrusiveLink<T> {
    pub const fn new() -> Self {
        Self {
            next: None,
            prev: None,
        }
    }
}

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

/// Trait for types that can be stored in intrusive list
///
/// # Safety
/// The link field must be at a consistent offset within the struct
pub unsafe trait Linked {
    fn link(&self) -> &IntrusiveLink<Self>;
    fn link_mut(&mut self) -> &mut IntrusiveLink<Self>;
}

/// Intrusive doubly linked list
pub struct IntrusiveList<T: Linked> {
    head: Option<NonNull<T>>,
    tail: Option<NonNull<T>>,
    len: usize,
    _marker: PhantomData<T>,
}

impl<T: Linked> IntrusiveList<T> {
    pub const fn new() -> Self {
        Self {
            head: None,
            tail: None,
            len: 0,
            _marker: PhantomData,
        }
    }

    pub fn is_empty(&self) -> bool {
        self.head.is_none()
    }

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

    /// Push a node to the front
    ///
    /// # Safety
    /// - The node must not already be in a list
    /// - The node must remain valid while in the list
    pub unsafe fn push_front(&mut self, node: NonNull<T>) {
        let node_ref = node.as_ref();
        let link = node_ref.link() as *const _ as *mut IntrusiveLink<T>;

        (*link).next = self.head;
        (*link).prev = None;

        if let Some(old_head) = self.head {
            let old_head_link = old_head.as_ref().link() as *const _ as *mut IntrusiveLink<T>;
            (*old_head_link).prev = Some(node);
        } else {
            self.tail = Some(node);
        }

        self.head = Some(node);
        self.len += 1;
    }

    /// Push a node to the back
    ///
    /// # Safety
    /// Same as push_front
    pub unsafe fn push_back(&mut self, node: NonNull<T>) {
        let node_ref = node.as_ref();
        let link = node_ref.link() as *const _ as *mut IntrusiveLink<T>;

        (*link).next = None;
        (*link).prev = self.tail;

        if let Some(old_tail) = self.tail {
            let old_tail_link = old_tail.as_ref().link() as *const _ as *mut IntrusiveLink<T>;
            (*old_tail_link).next = Some(node);
        } else {
            self.head = Some(node);
        }

        self.tail = Some(node);
        self.len += 1;
    }

    /// Pop from front
    ///
    /// # Safety
    /// Caller must ensure proper handling of returned node
    pub unsafe fn pop_front(&mut self) -> Option<NonNull<T>> {
        self.head.map(|node| {
            let link = node.as_ref().link();

            self.head = link.next;

            if let Some(new_head) = self.head {
                let new_head_link = new_head.as_ref().link() as *const _ as *mut IntrusiveLink<T>;
                (*new_head_link).prev = None;
            } else {
                self.tail = None;
            }

            // Clear the node's links
            let link_mut = node.as_ref().link() as *const _ as *mut IntrusiveLink<T>;
            (*link_mut).next = None;
            (*link_mut).prev = None;

            self.len -= 1;
            node
        })
    }

    /// Remove a specific node
    ///
    /// # Safety
    /// - Node must be in this list
    pub unsafe fn remove(&mut self, node: NonNull<T>) {
        let link = node.as_ref().link();

        match (link.prev, link.next) {
            (Some(prev), Some(next)) => {
                // Middle node
                let prev_link = prev.as_ref().link() as *const _ as *mut IntrusiveLink<T>;
                let next_link = next.as_ref().link() as *const _ as *mut IntrusiveLink<T>;
                (*prev_link).next = Some(next);
                (*next_link).prev = Some(prev);
            }
            (Some(prev), None) => {
                // Tail node
                let prev_link = prev.as_ref().link() as *const _ as *mut IntrusiveLink<T>;
                (*prev_link).next = None;
                self.tail = Some(prev);
            }
            (None, Some(next)) => {
                // Head node
                let next_link = next.as_ref().link() as *const _ as *mut IntrusiveLink<T>;
                (*next_link).prev = None;
                self.head = Some(next);
            }
            (None, None) => {
                // Only node
                self.head = None;
                self.tail = None;
            }
        }

        // Clear the node's links
        let link_mut = node.as_ref().link() as *const _ as *mut IntrusiveLink<T>;
        (*link_mut).next = None;
        (*link_mut).prev = None;

        self.len -= 1;
    }

    /// Iterate over the list
    pub fn iter(&self) -> IntrusiveIter<'_, T> {
        IntrusiveIter {
            current: self.head,
            _marker: PhantomData,
        }
    }
}

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

pub struct IntrusiveIter<'a, T: Linked> {
    current: Option<NonNull<T>>,
    _marker: PhantomData<&'a T>,
}

impl<'a, T: Linked> Iterator for IntrusiveIter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.current.map(|node| unsafe {
            let node_ref = node.as_ref();
            self.current = node_ref.link().next;
            node_ref
        })
    }
}

// Example usage with a Task struct

#[derive(Debug)]
pub struct Task {
    pub id: u64,
    pub name: String,
    pub priority: u8,
    link: IntrusiveLink<Task>,
}

// Safety: link field is consistently placed in Task
unsafe impl Linked for Task {
    fn link(&self) -> &IntrusiveLink<Self> {
        &self.link
    }

    fn link_mut(&mut self) -> &mut IntrusiveLink<Self> {
        &mut self.link
    }
}

impl Task {
    pub fn new(id: u64, name: &str, priority: u8) -> Self {
        Self {
            id,
            name: name.to_string(),
            priority,
            link: IntrusiveLink::new(),
        }
    }
}

fn main() {
    // Create tasks on the heap
    let task1 = Box::new(Task::new(1, "Task A", 1));
    let task2 = Box::new(Task::new(2, "Task B", 2));
    let task3 = Box::new(Task::new(3, "Task C", 3));

    // Convert to NonNull pointers
    let ptr1 = NonNull::new(Box::into_raw(task1)).unwrap();
    let ptr2 = NonNull::new(Box::into_raw(task2)).unwrap();
    let ptr3 = NonNull::new(Box::into_raw(task3)).unwrap();

    let mut list = IntrusiveList::<Task>::new();

    // Add tasks to list
    unsafe {
        list.push_back(ptr1);
        list.push_back(ptr2);
        list.push_back(ptr3);
    }

    println!("Tasks in list:");
    for task in list.iter() {
        println!("  {} (priority {}): {}", task.id, task.priority, task.name);
    }

    // Remove middle task
    unsafe {
        list.remove(ptr2);
    }

    println!("\nAfter removing Task B:");
    for task in list.iter() {
        println!("  {} (priority {}): {}", task.id, task.priority, task.name);
    }

    // Clean up - take ownership back and drop
    unsafe {
        while let Some(ptr) = list.pop_front() {
            drop(Box::from_raw(ptr.as_ptr()));
        }
    }
}

| Approach | Safety | Performance | Ease of Use | Use Case |

|----------|--------|-------------|-------------|----------|

| Box singly | Safe | Good | Easy | Stacks, simple lists |

| Rc> doubly | Safe | Overhead | Medium | When doubly needed |

| Intrusive | Unsafe | Best | Hard | Kernel, embedded |

| std::LinkedList | Safe | Good | Easy | General purpose |

| Arena-based | Safe | Very good | Medium | Known lifetime |

1. Prefer Vec over LinkedList - Almost always faster in practice
2. Use Box for singly linked - Simplest ownership model
3. Use Rc for doubly linked - When you need it
4. Consider arena allocation - For complex graph structures
5. Implement Drop carefully - Avoid stack overflow on large lists
6. Use iterators - More idiomatic than index access

| Operation | Singly (Box) | Doubly (Rc) | Vec |

|-----------|--------------|-------------|-----|

| Push front | O(1) | O(1) | O(n) |

| Push back | O(n) | O(1) | O(1) amortized |

| Pop front | O(1) | O(1) | O(n) |

| Pop back | O(n) | O(1) | O(1) |

| Random access | O(n) | O(n) | O(1) |

| Insert middle | O(n) find + O(1) | O(n) find + O(1) | O(n) |

| Cache locality | Poor | Poor | Excellent |

1. Implement contains() for singly linked list
2. Add append() to merge two lists

1. Implement a sorted linked list with insert_sorted()
2. Create a circular linked list

1. Implement an LRU cache using a doubly linked list
2. Build a lock-free concurrent linked list

• Learning Rust With Entirely Too Many Linked Lists
• std::collections::LinkedList
• Intrusive Collections

• tokio: Task queues use intrusive lists
• Linux kernel: Extensively uses intrusive lists
• allocators: Free list management
• LRU caches: Fast removal and reordering
• undo/redo: Command history