Standard Collections

LinkedList<T>

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

Memory Layout

Stack (`LinkedList<T>`)
+-----------+-----------+-------+
| head      | tail      | len=3 |
+-----+-----+-----+-----+-------+
      |           |
      v           +-----------------------------------+
+---------------+      +---------------+      +-------v-------+
| prev: None    | ---> | prev: Some    | ---> | prev: Some    |
| next: Some    | <--- | next: Some    | <--- | next: None    |
| elem: 10      |      | elem: 20      |      | elem: 30      |
+---------------+      +---------------+      +---------------+

Every insertion into a LinkedList<T> performs a separate heap allocation for the node and stores two extra machine words (prev and next pointers, 16 bytes on 64-bit) alongside T.

Operations and Complexity

Operation Method Time Complexity
Push / pop at front list.push_front(x) / list.pop_front() $O(1)$
Push / pop at back list.push_back(x) / list.pop_back() $O(1)$
Move all nodes from other onto the end of self list.append(&mut other) $O(1)$ (relinks tail/head pointers)
Split list at index at list.split_off(at) $O(\min(\text{at}, n - \text{at}))$ traversal, $O(1)$ relink
Random access by index Not supported (list.iter().nth(i)) $O(n)$ pointer chase

O(1) List Concatenation with append() and Splitting with split_off()

The primary operation where LinkedList<T> has an asymptotic advantage over Vec<T> and VecDeque<T> is list.append(&mut other), which concatenates two lists of arbitrary length in $O(1)$ time by updating four pointers without copying or reallocating any elements:

use std::collections::LinkedList;

fn main() {
    let mut first = LinkedList::from(["a", "b"]);
    let mut second = LinkedList::from(["c", "d", "e"]);

    // Relinks `second` onto the tail of `first` in O(1) time; `second` becomes empty:
    first.append(&mut second);
    println!("After append:    first={first:?}, second={second:?}");

    // Splits `first` at index 3, returning elements from index 3 onward:
    let tail = first.split_off(3);
    println!("After split_off: first={first:?}, tail={tail:?}");
}

After append:    first=["a", "b", "c", "d", "e"], second=[]
After split_off: first=["a", "b", "c"], tail=["d", "e"]

Why Vec<T> and VecDeque<T> Are Almost Always Preferred

Even when inserting or removing elements in the middle of a sequence of a few thousand items, Vec<T> and VecDeque<T> typically outperform LinkedList<T> on modern CPUs because:

  1. Reaching the middle of a LinkedList<T> requires $O(n)$ sequential pointer chasing across non-contiguous heap addresses (causing CPU cache misses on each node), whereas Vec<T> shifts contiguous cache lines with hardware-prefetched SIMD memmove.
  2. LinkedList<T> allocates and frees a heap node on every single push and pop, whereas Vec<T> and VecDeque<T> amortize allocations across geometric growth.