How to use LinkedList in Rust
You remember the linked list from your first algorithms class. The professor drew nodes and pointers on the whiteboard, explaining how you can splice elements into the middle of a list without shifting everything else. You build a data structure in Rust and reach for std::collections::LinkedList. The compiler accepts it. Your code runs. Then you run a benchmark and stare at the results. The linked list is slower than the vector. Much slower.
Rust has LinkedList, but using it is a decision that almost always hurts performance. The collection exists for specific workloads where pointer manipulation beats memory movement. Here is how to use it correctly, and how to recognize the tiny slice of problems where it actually wins.
The structure under the hood
A linked list stores data in separate nodes scattered across the heap. Each node holds a value and pointers to the previous and next nodes. Rust's implementation is a doubly-linked list, meaning every node knows its neighbor in both directions. You can walk forward or backward. You can insert or remove a node in the middle by rewiring the pointers of its neighbors. The data itself doesn't move. Only the pointers change.
This design gives you O(1) insertion and removal at any position, provided you already have a reference to that position. The cost is memory fragmentation and cache behavior. Every node is a separate heap allocation. The nodes are not contiguous. The CPU cannot predict where the next node lives.
Minimal usage
Creating and manipulating a linked list follows a standard pattern. You create an empty list, push elements to the front or back, and iterate through them.
use std::collections::LinkedList;
fn main() {
// LinkedList allocates a new node for each element.
let mut tasks = LinkedList::new();
// Push to the back appends to the tail.
tasks.push_back("Write tests");
tasks.push_back("Refactor parser");
// Push to the front adds to the head.
tasks.push_front("Fix login bug");
// Iteration follows pointers from head to tail.
for task in &tasks {
println!("Task: {}", task);
}
}
The push_back and push_front methods allocate a fresh node and update the list's internal pointers. Iteration starts at the head and follows the next pointers until it hits null. The syntax looks like any other collection, but the runtime behavior is distinct.
The cache miss tax
The reason LinkedList feels slow in practice comes down to how modern CPUs work. Processors are fast, but memory is slow. To bridge the gap, CPUs use a cache hierarchy. When the CPU reads a value from memory, it loads a block of surrounding data into the cache, assuming you'll need it next. This is called prefetching.
A Vec stores its elements in a contiguous block of memory. When you iterate over a vector, the CPU loads one cache line and can process multiple elements before fetching the next line. The hardware prefetcher predicts the next address and loads it in the background. Iteration becomes nearly free.
A LinkedList node can live anywhere on the heap. Node A might be at address 0x1000, and Node B might be at 0x8F420. When you follow a pointer from A to B, the CPU has to check the cache. If B is not there, it triggers a cache miss. The CPU stalls while memory fetches the data. This stall costs hundreds of cycles. Even if the algorithmic complexity is the same, the constant factor of cache misses destroys performance.
Don't reach for the linked list to fix a performance problem. You'll likely make it worse.
Cursor-based manipulation
The one place LinkedList shines is cursor-based manipulation. If you have a reference to a specific position and need to insert or remove elements around it repeatedly, the cursor API avoids scanning the list. A cursor holds a position and can move around, insert, or remove in O(1) time.
use std::collections::LinkedList;
fn main() {
let mut playlist = LinkedList::new();
playlist.push_back("Song A");
playlist.push_back("Song B");
playlist.push_back("Song C");
// Create a cursor at the front of the list.
// The cursor borrows the list and tracks a position.
let mut cursor = playlist.cursor_front();
// Move the cursor to the second element.
cursor.move_next();
// Insert a song before the current position.
// This is O(1) because the cursor already has the pointers.
cursor.insert_before("Song B-Prime");
// Remove the current element and get the value back.
// The neighbors are rewired automatically.
if let Some(removed) = cursor.remove_current() {
println!("Removed: {}", removed);
}
// The cursor remains valid and points to the element after the removed one.
println!("Current: {:?}", cursor.current());
}
The cursor API is the killer feature of LinkedList. It lets you maintain a position and mutate the list around it without searching. If you drop the cursor, you lose your O(1) position. Keep the cursor alive as long as you are doing localized edits.
Splicing and appending
LinkedList supports O(1) concatenation and splitting of sub-lists. You can move all elements from one list to another by rewiring the endpoints. This is useful when you are building a data structure that frequently merges or splits large blocks of data.
use std::collections::LinkedList;
fn main() {
let mut list_a = LinkedList::new();
list_a.push_back(1);
list_a.push_back(2);
let mut list_b = LinkedList::new();
list_b.push_back(3);
list_b.push_back(4);
// Move all elements from list_b to the end of list_a.
// This is O(1). No elements are copied or moved.
list_a.append(&mut list_b);
// list_b is now empty.
println!("List A: {:?}", list_a);
println!("List B: {:?}", list_b);
// Split the list into two at a cursor position.
let mut cursor = list_a.cursor_front();
cursor.move_next();
cursor.move_next();
// Split off everything after the cursor.
let mut list_c = cursor.split_off();
println!("List A after split: {:?}", list_a);
println!("List C: {:?}", list_c);
}
The append method transfers ownership of the nodes. The nodes themselves are not allocated or deallocated. Only the pointers at the boundaries change. This makes LinkedList efficient for queue implementations that merge batches, or for graph algorithms that move nodes between adjacency lists.
Pitfalls and compiler errors
The biggest pitfall is assuming LinkedList behaves like a vector. You cannot index into a linked list. If you try to use bracket syntax, the compiler rejects it because LinkedList does not implement the Index trait.
let list = LinkedList::new();
list.push_back(10);
// This will not compile.
// The compiler reports that LinkedList does not support indexing.
let first = list[0];
You must use .get(index) instead, which scans the list from the head or tail, whichever is closer. This is O(n). Random access is slow.
Another pitfall is the cursor borrow rules. A cursor borrows the list. If you hold a cursor and try to mutate the list directly, you get a borrow checker error. The cursor owns the modification state. You must perform all mutations through the cursor while it is alive.
If you try to mutate the list while a cursor is active, the compiler rejects you with a borrow conflict. The error message will indicate that the list is borrowed as mutable by the cursor. Drop the cursor or complete your mutations before accessing the list directly.
When to use LinkedList
Use Vec when you need fast access by index, fast iteration, or appending to the end. The contiguous memory layout wins for almost every workload. The cache behavior and allocation efficiency of vectors make them the default choice.
Use VecDeque when you need to push and pop from both ends efficiently. It provides O(1) amortized operations at both ends without the memory fragmentation of a linked list. A deque is the right tool for queues, sliding windows, and double-ended stacks.
Use LinkedList when you have a cursor pointing to a specific position and need to perform many insertions or removals around that position. The cursor API gives you O(1) splicing that Vec cannot match. If your algorithm maintains a position and edits locally, the linked list pays off.
Use LinkedList when you are implementing a data structure that requires frequent splicing of large blocks of elements between lists. LinkedList supports O(1) concatenation and splitting of sub-lists via append and split_off. If you are merging or partitioning lists repeatedly, the pointer rewiring beats memory movement.
Reach for Vec even if you need to remove elements from the middle. Swapping with the last element and popping is O(1). If order matters, the O(n) shift of a vector is usually faster than the allocation and pointer overhead of a linked list due to CPU cache behavior. Profile before you switch.
Trust the benchmark. If the profiler says Vec is faster, the profiler is right.