The Shape of Data in RAM
You're building a game loop. You need to store active entities. You reach for a linked list because that's what you learned in a data structures class. You add ten thousand entities. The frame rate tanks. The profiler shows the CPU spending more time jumping around memory than doing actual work. The problem isn't your logic. It's the shape of your data in RAM.
Rust gives you three main choices for dynamic sequences: Vec, VecDeque, and LinkedList. They all let you add and remove items. They all look similar in code. Under the hood, they behave completely differently. The difference comes down to how the data sits in memory and how the CPU fetches it.
Vec: The Contiguous King
A Vec stores its elements in a single, contiguous block of memory. Think of it like a row of lockers in a school hallway. Locker 0 is next to locker 1, which is next to locker 2. If you want to visit every locker, you just walk down the hall. You never have to turn around or run to a different building.
/// Stores a sequence of integers in contiguous memory.
/// Ideal for iteration and random access by index.
fn vec_example() {
// Allocates a block of memory on the heap.
// Starts with capacity 0, grows as needed.
let mut scores = Vec::new();
// Pushing adds to the end.
// If the block is full, Vec allocates a bigger block,
// copies everything over, and frees the old one.
scores.push(100);
scores.push(250);
// Random access is instant.
// The CPU calculates the address by adding the index
// times the size of the element to the base pointer.
let second = scores[1];
}
This layout gives Vec two superpowers. First, random access is O(1). You can jump to index 5000 instantly. Second, iteration is blazing fast. The CPU doesn't just fetch the data you asked for. It fetches a chunk of memory called a cache line, usually 64 bytes. If your data is contiguous, one cache line fetch might give you eight integers at once. The CPU also has a hardware prefetcher that sees you're walking through memory linearly and grabs the next cache line before you even ask.
Vec is the default. If you're not sure what to use, use Vec. It wins on speed, memory efficiency, and ergonomics for the vast majority of use cases.
Trust the contiguous block. The CPU rewards locality.
The Cost of Growth
Vec has a catch. Since it's a fixed-size block, it eventually fills up. When you push and there's no room, Vec must grow. It allocates a new, larger block of memory, copies all the existing elements to the new block, and frees the old one.
This sounds expensive. It is. But Vec uses a growth strategy that makes the average cost negligible. When Vec needs to grow, it typically doubles its capacity. This means reallocations happen less and less frequently as the vector grows. The cost of the copy is spread out over many pushes. In algorithmic terms, push is O(1) amortized.
You can control this yourself. If you know roughly how many items you'll store, use Vec::with_capacity. This avoids reallocations entirely.
/// Pre-allocates memory to avoid reallocations during a known loop.
/// This is a common convention when reading from a file or parsing.
fn parse_records() -> Vec<String> {
// We know there are 1000 records.
// Allocating once is faster than growing 10 times.
let mut records = Vec::with_capacity(1000);
for i in 0..1000 {
records.push(format!("Record {}", i));
}
records
}
Convention aside: always use Vec::with_capacity when the size is known or bounded. It's a free performance win.
VecDeque: The Circular Buffer
Sometimes you need a queue. You add items to the back and remove them from the front. A Vec can do this, but removing from the front is slow. Vec::remove(0) shifts every remaining element down by one index to fill the gap. That's O(N). If you do this in a loop, your code degrades to O(NĀ²).
VecDeque solves this. It's a deque, short for double-ended queue. It supports O(1) push and pop on both ends. Internally, it uses a circular buffer. Imagine a conveyor belt that wraps around. You can add to the back or the front without moving any existing items. The head and tail pointers just move. When the tail hits the end of the buffer, it wraps around to the beginning.
use std::collections::VecDeque;
/// Manages a fixed-size history buffer.
/// Keeps the most recent N commands.
struct CommandHistory {
commands: VecDeque<String>,
max_size: usize,
}
impl CommandHistory {
fn new(max: usize) -> Self {
Self {
// Pre-allocate to avoid growth during normal operation.
commands: VecDeque::with_capacity(max),
max_size: max,
}
}
fn add(&mut self, cmd: String) {
// If full, remove the oldest command.
// pop_front is O(1) for VecDeque.
if self.commands.len() >= self.max_size {
self.commands.pop_front();
}
// Add new command to the end. O(1).
self.commands.push_back(cmd);
}
}
VecDeque keeps data contiguous in chunks, so iteration is still fast. You get the cache benefits of Vec with the flexibility of a queue. The trade-off is that VecDeque does not support indexing. You cannot write deque[i]. The compiler will reject this with an error like "the type VecDeque<T> cannot be indexed". You must iterate or use pop methods. This restriction exists because the circular layout makes index calculation complex and error-prone.
If you need a queue, reach for VecDeque. Don't hack a Vec with remove(0).
LinkedList: The Pointer Chase
A LinkedList stores each element in a separate node allocated on the heap. Each node holds the value and pointers to the previous and next nodes. To find the next item, you follow the pointer.
This sounds flexible. You can insert in the middle without shifting. You can split lists. But the memory layout is scattered. Nodes can be anywhere in RAM. Iterating a linked list is a scavenger hunt. The CPU fetches a node, finds the pointer, jumps to a random address, fetches the next node, and repeats.
This causes cache misses. The CPU prefetcher can't help because the addresses are random. Each node might be in a different cache line. For a list of integers, a Vec might fit 16 items in a single cache line. A LinkedList might fetch a new cache line for every single item. The performance difference is massive. Iterating a LinkedList can be 10x to 50x slower than a Vec depending on the data size and CPU architecture.
use std::collections::LinkedList;
/// Demonstrates LinkedList usage.
/// Note: Iteration is slow due to cache misses.
fn linked_list_example() {
let mut tasks = LinkedList::new();
// push_back is O(1).
tasks.push_back("Compile");
tasks.push_back("Test");
// Iteration requires following pointers.
// No random access. No indexing.
for task in &tasks {
println!("{}", task);
}
}
Memory overhead is another killer. Each node needs storage for the value plus two pointers (next and prev). On a 64-bit system, pointers are 8 bytes each. Plus the heap allocator adds overhead per allocation. For a u32 value, a Vec uses 4 bytes per item. A LinkedList might use 32 bytes or more per item. That's 8x the memory for the same data.
LinkedList also has a complex API for modification. To insert in the middle, you need a Cursor. The cursor holds a position in the list. You move the cursor, then call cursor.insert_before(). This is ergonomic pain compared to vec.insert(index, value).
If you're reaching for a LinkedList, ask yourself if you're solving a problem or just satisfying a nostalgia for pointers.
When LinkedList Actually Wins
LinkedList isn't useless. It has specific strengths. It shines when you need to split and merge lists in O(1) time. You can take two lists and splice them together without copying any data. You can also insert or remove in the middle in O(1) time, provided you already have a cursor at the exact position.
This is useful in niche scenarios. An editor implementing undo/redo with complex history branching might benefit. A graph algorithm that frequently merges disjoint sets might use it. But these cases are rare. Even then, you should measure. The cache penalty often outweighs the algorithmic benefit unless the list is huge and the operations are extremely frequent.
For 99% of Rust code, LinkedList is the wrong tool. The standard library includes it for completeness, not because it's recommended.
Pitfalls and Compiler Errors
VecDeque indexing: As mentioned, VecDeque does not implement Index. If you try deque[i], you get a compiler error. The error message will say something like "the type std::collections::VecDeque<T> cannot be indexed". You must iterate or use pop_front/pop_back.
LinkedList indexing: Same issue. LinkedList does not support indexing. list[i] fails. You must iterate. If you find yourself writing a loop to find an index just to access an element, you should probably be using a Vec.
Vec capacity shock: If you push a massive number of items into a Vec without reserving, you'll trigger many reallocations. Each reallocation copies data. This can cause latency spikes in real-time applications. Use reserve or with_capacity to smooth this out.
LinkedList cursor lifetime: The Cursor API borrows the list. You can't hold a cursor and mutate the list in ways that invalidate the cursor. The borrow checker enforces this, but it can lead to complex lifetimes if you're not careful.
E0599: If you try to call a method that doesn't exist, you get E0599. This often happens when you mix up Vec and VecDeque APIs. Vec has remove(index). VecDeque does not. VecDeque has pop_front. Vec does not. Check the docs.
Treat the API differences as signals. If you need indexing, you need a Vec. If you need queue behavior, you need a VecDeque. The compiler will guide you.
Decision Matrix
Use Vec when you need random access by index, fast iteration, or you're building a list that grows at the end. It's the default. It's the workhorse. It uses the least memory and runs the fastest for sequential access.
Use VecDeque when you need a queue or stack where you push and pop from both ends. It gives you O(1) operations on both sides without the cache penalty of a linked list. It's the right choice for buffers, history logs, and BFS algorithms.
Reach for LinkedList only when you need to split and merge lists in O(1) time, or when you have a cursor and need to insert/remove in the middle without shifting. Even then, measure first. The cache penalty usually kills the benefit. If you're implementing a data structure that requires frequent splicing, LinkedList might be justified. For application code, it almost never is.
The compiler won't stop you from using a LinkedList, but your profiler will judge you.