Why LRU Is a Rust Rite of Passage

Ask a programmer to build an LRU cache and they will reach for the textbook design without thinking: a hash map for O(1) key lookup, and a doubly linked list for O(1) recency updates. Each map entry points at a list node; each list node points at its neighbors; touching a key splices its node to the front. In C it is a fiddly afternoon. In Go it is container/list and a map. In Rust it is the moment a lot of people first really meet the borrow checker.

Where it breaks

The textbook design needs a node that is owned by the list but also reachable from the map, with prev and next pointers that let you mutate a node through one path while it is aliased by another. That is precisely the pattern Rust is built to forbid: shared mutable aliasing. Write next: &mut Node and the borrow checker asks who owns this node, and how can the map and the list and the neighbor all hold a mutable path to it at once. They cannot, not with plain references. The compiler is not being fussy. It is refusing to let you build a structure where a &mut could exist to something another pointer can also change.

You have four honest ways out, and choosing among them is the lesson:

1. Rc<RefCell<Node>> everywhere. Reference counting for shared ownership, RefCell to move the borrow check to runtime. It works, it compiles, and it is verbose and easy to deadlock-borrow at runtime. The pointer soup just got reference counts bolted on.
2. unsafe with raw pointers. What the real lru crate does internally, carefully, behind a safe API. Fast, but now you are the borrow checker, and you had better be right.
3. An index arena. Store the nodes in a Vec and make the links plain usize indices instead of references. No aliasing, because an index is just a number. More on this below.
4. A simpler structure entirely. For a teaching-sized cache, drop the linked list:

pub struct LruCache {
    capacity: usize,
    map: HashMap<i32, i32>,
    order: Vec<i32>, // front = least recent, back = most recent
}

impl LruCache {
    pub fn get(&mut self, key: i32) -> Option<i32> {
        if let Some(&v) = self.map.get(&key) {
            self.touch(key);
            Some(v)
        } else { None }
    }
    pub fn put(&mut self, key: i32, value: i32) {
        if self.capacity == 0 { return; }
        if self.map.contains_key(&key) {
            self.map.insert(key, value);
            self.touch(key);
            return;
        }
        if self.map.len() == self.capacity {
            let lru = self.order.remove(0); // evict front
            self.map.remove(&lru);
        }
        self.map.insert(key, value);
        self.order.push(key);
    }
    fn touch(&mut self, key: i32) {
        if let Some(pos) = self.order.iter().position(|&k| k == key) {
            self.order.remove(pos);
            self.order.push(key);
        }
    }
}

touch is O(n) because it scans the Vec, so this is not the asymptotically optimal cache. But it is obviously correct, it has zero unsafe, and the borrow checker is happy because there is no aliasing: keys are values, the order is a list of values, nothing points at anything.

The point the compiler was making

Here is the reframe that turns the frustration into a lesson. The reason this design fought you is that the textbook LRU relies on a node being mutated through one alias while another alias still holds it. In C that "works," right up until the day a stale pointer or a double-unlink corrupts your heap and you spend a weekend in a debugger. Rust made you confront, at compile time, the exact aliasing that causes those bugs.

And the way out it nudges you toward, the index arena, is genuinely a better default for linked and graph-shaped data in Rust:

struct Node { key: i32, val: i32, prev: usize, next: usize }
struct Lru { nodes: Vec<Node>, /* head/tail/free indices, map of key -> index */ }

Links are usize into one Vec. There is no aliasing to reason about, the whole structure is one owned allocation, it serializes trivially, and it is cache-friendly because the nodes are contiguous. The same trick powers high-performance graphs, ECS game engines, and arena-based compilers. You reach for it because the borrow checker taught you to.

The takeaway

LRU is a rite of passage not because it is hard, but because it is the first time many people feel Rust disagree with a design they considered settled, and then discover the disagreement was a good point. The lesson is not "Rust makes data structures painful." It is "the pointer-mutating-through-aliases pattern was always dangerous, and here is a cleaner way to express the same idea." You leave the fight reaching for indices and arenas, and your non-Rust code quietly gets better too.

Build it yourself. Solve the LRU Cache challenge on barehands and get graded on correctness and speed. No crates, just the standard library.