If you're coming from a Java or C++ background, your instinct when you need a dynamic sequence of elements is often to reach for a linked list. It's the classic computer science answer to "how do I handle a list that grows?" But in Rust, trying to implement a linked list the "traditional" way is a rite of passage that usually ends in a headache. I've seen many developers spend an entire afternoon fighting the borrow checker just to get a basic Node structure working, only to find that their code is slower than if they'd just used a vector.

The fight with the borrow checker

The naive way to build a linked list in Rust is to try and mirror the C-style approach: a struct with a value and a pointer to the next node. You'll likely start with Box<Node>. This works for a simple singly linked list, but the moment you want a doubly linked list—where nodes point both forward and backward—you hit a wall. Rust's ownership rules dictate that a value can have only one owner. A node in a doubly linked list, by definition, is pointed to by both its predecessor and its successor.

// This is the "naive" path that leads to pain
struct Node {
    value: i32,
    next: Option<Box<Node>>,
    prev: Option<Box<Node>>, // Error! This creates a circular ownership loop
}

To fix this, you'll find yourself reaching for Rc<RefCell<T>> to allow multiple ownership and interior mutability. While this technically works, you've now introduced runtime overhead for reference counting and borrow checking. You're no longer writing high-performance Rust; you're essentially simulating a garbage-collected language inside Rust. It's verbose, it's clunky, and it's usually the wrong tool for the job.

Pointer chasing and the cache miss

Beyond the syntax struggle, there's a hardware reality we have to face. Modern CPUs are incredibly fast, but getting data from main memory is slow. CPUs rely on "cache lines"—they grab a chunk of memory and assume that the data you need next is physically located right next to the data you just used. This is why Vec is so dominant. A vector stores its elements contiguously in memory, meaning the CPU can pre-fetch the next few elements with near-perfect accuracy.

A linked list, however, scatters its nodes across the heap. Each time you follow a next pointer, you're potentially jumping to a completely different page of memory. This is "pointer chasing," and it's a performance killer. Even if a linked list theoretically offers $O(1)$ insertion at the head, the constant factor overhead of cache misses often makes a Vec (which might need to occasionally reallocate) faster in practice for everything except the most extreme data sizes.

When a linked list actually makes sense

So, is std::collections::LinkedList useless? Not entirely, but its use case is tiny. You should consider it only if you are doing heavy splitting and merging of lists—operations where you can move a large chunk of data by just swapping a few pointers without iterating through the elements. If you need to push and pop from both ends, VecDeque is almost always the better choice because it uses a growable ring buffer, giving you the best of both worlds: contiguous-ish memory and $O(1)$ operations at both ends.

My rule of thumb is this: start with Vec. If you realize you're doing too many expensive shifts at the front of the list, move to VecDeque. Only if you're implementing a very specific algorithm that requires constant-time splitting or merging should you even look at a linked list. Trust me, your future self—and the borrow checker—will thank you.

📋 Practical Task

Refactoring a Node-Based Undo Stack to a Vector

You have been handed a legacy piece of code for a text editor's "Undo" feature. The previous developer implemented it as a custom singly linked list of Action structs to avoid "expensive" array shifts. However, the current implementation is causing memory fragmentation and is difficult to maintain.

Your Task:

• Rewrite the UndoStack implementation. Replace the Node and Box logic with a Vec<Action>.
• Implement the push_action method (to add a new action to the stack) and the pop_action method (to retrieve the last action for undoing).
• Ensure that the UndoStack has a maximum capacity (e.g., 100 actions). If the vector exceeds this size, remove the oldest action (the one at the bottom of the stack) to make room for the new one.
• Compare the mental overhead: notice how the ownership logic simplifies once the Box pointers are gone.