The chain that never ends
You are building a task scheduler. New jobs arrive constantly. Finished jobs drop off. Sometimes you need to splice a batch of high-priority tasks right into the middle of the queue. Your instinct says linked list. Every computer science textbook draws a diagram of nodes pointing to each other and promises constant-time insertion anywhere. You reach for std::collections::LinkedList, write a few lines, and the compiler accepts it. The code works. The benchmarks run. And then you notice the scheduler is slower than a Vec that just shifts elements around.
This is the classic Rust surprise. The data structure you learned in school exists in the standard library, but the standard library itself quietly recommends against it. Understanding why requires looking past the algorithmic complexity charts and into how modern CPUs actually fetch data.
How linked lists actually work
A LinkedList stores data in separate chunks called nodes. Each node holds two pieces of information: the actual value you care about, and a pointer to the next node in the chain. The list itself only keeps track of the first and last nodes. Everything else is found by following pointers.
Think of a Vec as a row of lockers in a school hallway. The lockers sit side by side. If you know the number of the first locker, you can walk straight down the hall and grab any locker instantly. The hardware loves this layout because it fetches a whole chunk of lockers into its fast memory in one trip.
A LinkedList is more like a scavenger hunt. Each clue is hidden in a different room, a different building, or a different city. The clue tells you exactly where to go next. You never skip steps. You never jump ahead. The path is explicit, but the locations are scattered.
This scattering is the root of the performance difference. When you allocate a node, the memory allocator finds whatever free space is available on the heap. Those spaces are rarely adjacent. When your program iterates through the list, the CPU has to jump around memory, waiting for each new cache line to load. That waiting time dwarfs the theoretical savings of skipping a few element shifts.
The basic API
The public interface looks familiar if you have used other languages. You create an empty list, push values to either end, and pop them off when you are done.
use std::collections::LinkedList;
/// Demonstrates basic LinkedList operations and heap allocation behavior.
fn main() {
// Creates an empty list with no heap allocations yet.
let mut tasks = LinkedList::new();
// Allocates a new node on the heap and links it to the front.
tasks.push_front("compile");
tasks.push_front("fetch_deps");
// Allocates another node and attaches it to the back.
tasks.push_back("run_tests");
// Removes the front node, returns the value, and updates the head pointer.
let first_task = tasks.pop_front();
println!("Starting: {:?}", first_task);
}
Every push triggers a heap allocation. Every pop triggers a deallocation. The list tracks the head and tail pointers so it can add or remove from either end without touching the middle nodes. The API is symmetric and predictable.
What happens under the hood
When you call push_front, Rust calls the system allocator to reserve memory for a Node struct. That struct contains your value, a next pointer, and a prev pointer. Rust's LinkedList is doubly linked, which means traversal works efficiently in both directions. The allocator returns a raw pointer. The list updates its internal head pointer to point at this new node. The old head becomes the next target.
Iteration follows the next pointers. The compiler generates a simple loop that dereferences the pointer, yields the value, and moves to the next address. There is no bounds checking. There is no index calculation. The pointer either points to valid memory or it does not.
This simplicity is why linked lists are taught first. The logic is linear. The insertion algorithm is just pointer surgery. But pointer surgery requires the CPU to chase addresses. Modern processors predict sequential memory access with incredible accuracy. They pre-fetch data before your code even asks for it. A linked list breaks that prediction entirely. The CPU stalls on every single hop.
Memory fragmentation is another hidden cost. Each node requires its own allocation header. On a 64-bit system, a node holding a single i32 consumes at least 24 bytes of payload plus allocator metadata. A Vec<i32> stores those same integers back to back with zero per-element overhead. The linked list wastes memory and forces the allocator to manage thousands of tiny blocks instead of one large contiguous region.
Splicing and the cost of convenience
The one operation where a linked list shines on paper is splitting and merging. You can cut a chain in half and glue it to another chain without moving any values. The standard library exposes this through split_off and append.
use std::collections::LinkedList;
/// Shows O(1) pointer surgery for merging two lists.
fn main() {
let mut queue = LinkedList::new();
for i in 0..5 {
queue.push_back(i);
}
// Cuts the list at index 2. Returns a new LinkedList with the rest.
// Only updates pointers. No values are copied or moved.
let high_priority = queue.split_off(2);
// Appends the second list to the first.
// Updates the tail of the first and the head of the second.
queue.append(&mut high_priority);
println!("Merged: {:?}", queue);
}
The code looks elegant. You are rearranging pointers instead of shifting arrays. In a language with manual memory management, this is a legitimate optimization. In Rust, the allocator overhead and cache misses usually cancel out the benefit. You save a few CPU cycles on pointer updates but spend dozens waiting for memory to arrive.
The community convention is clear. Do not optimize for algorithmic complexity before measuring. Profile first. If the profiler actually shows allocation churn as the bottleneck, consider a custom pool allocator instead of swapping in a linked list. Pool allocators give you the contiguous memory benefits of arrays while keeping the O(1) insertion guarantees.
Borrowing friction and compiler errors
Linked lists expose a sharp edge in Rust's borrow checker. Because the list owns every node, you cannot hold a reference to a node while mutating the list structure. The compiler enforces this strictly.
Try to iterate and remove an element at the same time, and you will hit E0502 (cannot borrow as mutable because it is also borrowed as immutable). The iterator holds an immutable borrow of the list to read the current node. The remove method requires a mutable borrow to rewire the surrounding pointers. Rust refuses to let you do both simultaneously because a dangling reference could easily occur if the node gets dropped.
use std::collections::LinkedList;
fn main() {
let mut list = LinkedList::new();
list.push_back(1);
list.push_back(2);
list.push_back(3);
// This pattern triggers E0502.
// The iterator borrows `list` immutably.
// `list.remove()` requires a mutable borrow.
// for item in &list {
// if *item == 2 {
// list.remove(); // Error here
// }
// }
}
The workaround is to collect the indices or values you want to remove, then perform the mutations in a second pass. Or use split_off to isolate the section you want to modify. The borrow checker is not being difficult. It is preventing you from accidentally using a pointer to freed memory. Trust the borrow checker here. It usually has a point.
Another friction point is indexing. LinkedList does not implement Index. You cannot write list[2]. The compiler forces you to call .get(2) or iterate. This is intentional. Random access on a linked list is O(n) and destroys cache locality. The API design pushes you toward sequential access patterns.
When to actually reach for it
You need to pick the right container for the job. The choice depends on your access patterns, your mutation frequency, and your memory constraints.
Use Vec when you need fast iteration, random access by index, or predictable memory layout. Use Vec when you are building a stack, a buffer, or a simple list that grows at the end. Use Vec when cache performance matters more than insertion speed.
Use VecDeque when you frequently push and pop from both ends. Use VecDeque when you need a queue or a double-ended stack. Use VecDeque when you want the contiguous memory benefits of a vector without the penalty of shifting elements on front insertions.
Use LinkedList when you must split and merge large collections repeatedly and have profiled the allocation overhead as acceptable. Use LinkedList when you are implementing a specific algorithm that requires O(1) middle insertion and cannot tolerate the O(n) shift cost of a vector. Use LinkedList when you are interfacing with legacy C code that expects a doubly-linked list structure.
Reach for plain vectors in ninety percent of cases. The standard library documentation explicitly states that array-based containers are generally faster and more memory-efficient. The community follows that advice.