When people first tackle an LRU (Least Recently Used) cache, they usually try to cheat. They think, "I'll just use a HashMap and store a timestamp or a global counter alongside the value. When the cache is full, I'll just iterate through the map and find the one with the oldest timestamp."

The Fallacy of the Timestamp Scan

On the surface, that sounds clean. It's a few lines of code and no complex data structures. But here is why that approach fails in a production environment: it turns your $O(1)$ cache into an $O(n)$ bottleneck.

// The "naive" way that kills performance
fn evict(&mut self) {
    let oldest_key = self.map.iter()
        .min_by_key(|(_, (value, timestamp))| timestamp)
        .map(|(k, _)| k.clone());
    
    if let Some(k) = oldest_key {
        self.map.remove(&k);
    }
}

If your cache holds 10,000 items, every single put operation that triggers an eviction has to scan all 10,000 entries just to find one to kill. That's a disaster. A true LRU cache must provide get and put operations in constant time. To do that, you can't search; you have to know exactly where the oldest item is at all times.

The Marriage of a HashMap and a Doubly Linked List

To get $O(1)$, we need two different views of the same data. We need a HashMap for the fast lookups, and a Doubly Linked List to maintain the temporal order. The list acts as a queue of "recency": the head is the most recently used, and the tail is the one we evict.

The trick is that the HashMap doesn't just store the value; it stores a pointer (or a reference) to the node in the linked list. When you access a key, you use the map to jump straight to the node in the list, pluck it out of its current position, and move it to the head. No scanning, no loops, just pointer updates.

Wrestling with Rust's Ownership in a DLL

Now, here is where you'll feel the friction. Implementing a Doubly Linked List in Rust is famously a "rite of passage" because the borrow checker hates them. In a DLL, a node is pointed to by both its predecessor and its successor. That's shared ownership with mutation—the exact thing Box<T> cannot do.

You have two real choices here. You can use Rc<RefCell<Node>>, which is the "safe" way. It handles the reference counting and provides interior mutability. It's a bit wordy and has a small runtime overhead, but it keeps you out of the unsafe realm. Alternatively, you can use raw pointers (*mut Node) and unsafe blocks. Most high-performance crates do the latter, but for our purposes, Rc<RefCell> is the better way to learn the architecture without risking a segfault every five minutes.

The general flow for a get operation looks like this:

• Look up the key in the HashMap.
• If it exists, use the stored pointer to find the node in the list.
• Detach the node from its current neighbors.
• Move the node to the front of the list.
• Return the value.

I've found that the hardest part isn't the logic, but managing the "edge cases"—like when the cache only has one item, or when you're updating a value that's already at the head. Don't let the RefCell boilerplate distract you; focus on the pointer reshuffling.

---

📋 Practical Task

Implementing the Eviction Policy for a User Session Cache

You are building a cache to store active user sessions. The cache has a fixed capacity. When the capacity is reached, the least recently used session must be removed to make room for the new one.

Below is a skeletal implementation using Rc and RefCell. Your task is to complete the put method. You must ensure that:

1. If the key already exists, its value is updated and it is moved to the front (most recent).
2. If the key is new, it is added to the front.
3. If adding a new key exceeds the capacity, the node at the tail of the list must be removed from both the linked list and the HashMap.

use std::rc::Rc;
use std::cell::RefCell;
use std::collections::HashMap;

type Link = Option<Rc<RefCell<Node>>>;

struct Node {
    key: String,
    value: String,
    prev: Link,
    next: Link,
}

pub struct LRUCache {
    capacity: usize,
    map: HashMap<String, Rc<RefCell<Node>>>,
    head: Link,
    tail: Link,
}

impl LRUCache {
    pub fn new(capacity: usize) -> Self {
        Self {
            capacity,
            map: HashMap::with_capacity(capacity),
            head: None,
            tail: None,
        }
    }

    fn detach(&mut self, node: Rc<RefCell<Node>>) {
        let mut node_borrow = node.borrow_mut();
        let prev = node_borrow.prev.take();
        let next = node_borrow.next.take();

        if let Some(ref p) = prev {
            p.borrow_mut().next = next.clone();
        } else {
            self.head = next.clone();
        }

        if let Some(ref n) = next {
            n.borrow_mut().prev = prev;
        } else {
            self.tail = prev;
        }
    }

    fn push_front(&mut self, node: Rc<RefCell<Node>>) {
        node.borrow_mut().next = self.head.clone();
        node.borrow_mut().prev = None;

        if let Some(ref old_head) = self.head {
            old_head.borrow_mut().prev = Some(node.clone());
        } else {
            self.tail = Some(node.clone());
        }
        self.head = Some(node);
    }

    pub fn put(&mut self, key: String, value: String) {
        // TODO: Implement the LRU put logic
        // 1. Check if key exists -> update value, detach, push_front
        // 2. If new key -> check capacity, evict tail if needed, create node, push_front, insert map
    }
}