Collection Adapters and Specialized Types

LinkedList<T>

LinkedList<T> (std::collections::LinkedList<T>) is a doubly linked list of heap-allocated nodes, each holding an owned element T along with next and prev pointers.

Node Structure and Stack Header

On a 64-bit platform:

  • The LinkedList<T> header on the stack is 24 bytes (head: Option<NonNull<Node<T>>>, tail: Option<NonNull<Node<T>>>, len: usize).
  • Each heap-allocated Node<T> stores 16 bytes of link pointers (next and prev) plus size_of::<T>().
Stack (`LinkedList<T>`, 24 B)
+--------+--------+---------+
| head   | tail   | len = 2 |
+---+----+---+----+---------+
    |        |
    v        +-------------------------+
+-------------------+        +---------v---------+
| next: Some       -+------> | next: None        |
| prev: None        | <-----+- prev: Some        |
| element: "alpha"  |        | element: "beta"   |
+-------------------+        +-------------------+

Core Operations on LinkedList<T>

Method Signature Time Complexity Behavior
list.push_front(x) / push_back(x) fn push_front(&mut self, elt: T) $O(1)$ (1 heap alloc) Allocates a new node and links it at head or tail
list.pop_front() / pop_back() fn pop_front(&mut self) -> Option<T> $O(1)$ (1 heap free) Unlinks the head or tail node, frees it, and returns Some(T)
list.front() / back() fn front(&self) -> Option<&T> $O(1)$ Inspects head or tail element (front_mut / back_mut for &mut T)
list.append(&mut other) fn append(&mut self, other: &mut Self) $O(1)$ (0 allocs, 0 copies) Splices other's entire node chain onto the end of self
list.split_off(at) fn split_off(&mut self, at: usize) -> Self $O(\min(\text{at}, n - \text{at}))$ Walks from the nearer end to at and unlinks the tail into a new LinkedList<T>

Splicing Two Lists in $O(1)$ Time with append()

Unlike Vec::append or VecDeque::append, which must copy elements from other into self's buffer (and reallocate if self lacks capacity), LinkedList::append(&mut other) updates only the boundary pointers (self.tail.next = other.head, other.head.prev = self.tail, self.tail = other.tail, self.len += other.len) in $O(1)$ constant time regardless of how many millions of nodes other contains:

use std::collections::LinkedList;

fn main() {
    let mut primary = LinkedList::from([10, 20]);
    let mut secondary = LinkedList::from([30, 40, 50]);

    // Constant-time pointer splice; no elements are moved or copied in memory:
    primary.append(&mut secondary);

    println!("Primary:   {primary:?}");
    println!("Secondary: {secondary:?} (len={})", secondary.len());
}

Primary:   [10, 20, 30, 40, 50]
Secondary: [] (len=0)