Linked List Limitations

Even the official std::collections::LinkedList documentation begins with the note: "It is almost always better to use Vec or VecDeque because array-based containers are generally faster, more memory efficient, and make better use of CPU cache." Understanding why linked lists struggle on modern hardware—and how Rust's ownership rules interact with node-based lists—explains when to avoid LinkedList<T>.

1. CPU Cache Misses vs. Hardware Prefetching

Modern CPUs fetch memory into L1/L2 cache in 64-byte cache lines and automatically prefetch sequential memory addresses when scanning a contiguous array (Vec<T> or VecDeque<T>).

In a LinkedList<T>, each node is allocated separately on the heap and may reside at an arbitrary memory address:

Vec<i64> (1 Cache Line = 8 elements fetched in a single memory read!):
+----+----+----+----+----+----+----+----+
| 10 | 20 | 30 | 40 | 50 | 60 | 70 | 80 |   <-- Hardware prefetcher streams at ~50+ GB/s
+----+----+----+----+----+----+----+----+

LinkedList<i64> (Pointer chasing across scattered heap addresses):
[Node @ 0x6000_0140] ──(cache miss!)──> [Node @ 0x6000_89a0] ──(cache miss!)──> [Node @ 0x6000_0020]

Because the CPU cannot know the address of node $i + 1$ until it finishes loading node $i$, traversing a LinkedList<T> stalls on serial pointer-chasing latency (~50–100 ns per RAM miss) on every step.

2. Per-Element Memory and Allocator Overhead

3. Lack of Stable $O(1)$ Mid-List Insertion/Removal APIs

In textbook data structures, a doubly linked list supports $O(1)$ insertion and removal in the middle if you already hold a direct pointer to the target node. In safe Rust:

1. Holding raw mutable pointers to individual nodes from outside the list would violate the borrow checker's aliasing guarantees.
2. Stable std::collections::LinkedList does not expose raw node pointers (a safe CursorMut API remains nightly-only under #![feature(linked_list_cursors)]).
3. Consequently, on stable Rust, reaching index i in a LinkedList<T> requires an $O(n)$ sequential walk from the front or back—wiping out the theoretical $O(1)$ mid-list mutation advantage!

use std::collections::{LinkedList, VecDeque};

fn main() {
    // Both VecDeque and LinkedList support O(1) front/back operations,
    // but VecDeque also supports O(1) indexing and contiguous cache locality:
    let deque = VecDeque::from([10, 20, 30, 40]);
    let list = LinkedList::from([10, 20, 30, 40]);

    // O(1) on VecDeque vs O(n) iterator walk on LinkedList:
    println!("VecDeque[2] (O(1)):        {}", deque[2]);
    println!("LinkedList nth(2) (O(n)):  {:?}", list.iter().nth(2));
}

VecDeque[2] (O(1)):        30
LinkedList nth(2) (O(n)):  Some(&30)

When to Use an Index-Based Intrusive or Arena List Instead

If your problem genuinely requires $O(1)$ splicing, removal, and reordering of interior nodes by handle (such as an LRU cache's recency list or a DOM/UI tree), store the nodes inside a contiguous Vec<Node> where each prev and next link is a u32 or usize index into that Vec. This gives you both true $O(1)$ interior removal by node ID and contiguous cache-friendly storage.