LRU Cache

A Least Recently Used (LRU) cache bounds memory usage to a fixed capacity of entries, supporting both get(&K) and put(K, V) in $O(1)$ time and evicting the entry that has gone the longest without being accessed whenever capacity is exceeded.

In Rust, instead of scattering nodes across the heap with Rc<RefCell<Node>> or raw unsafe pointers, an arena-backed doubly linked list (Vec<Entry<K, V>>) combined with a HashMap<K, usize> achieves $O(1)$ lookups and $O(1)$ recency promotions in 100% safe Rust with contiguous cache locality!

100% Safe O(1) LRU Cache Architecture (`HashMap<K, usize>` + Arena Doubly Linked List):

  `map: HashMap<K, usize>`  ---> Maps key `K` to slot index `idx` in `entries: Vec<Node>`

  `entries: Vec<Node<K, V>>` (Doubly linked via `prev: Option<usize>`, `next: Option<usize>`):
    `head` (Most Recently Used / MRU)
      |
      v
    [ Slot 2: prev=None, next=Some(0) ] <===> [ Slot 0: prev=Some(2), next=None ]
                                                                          ^
                                                                        `tail` (LRU -> Evicted first!)

How $O(1)$ Promotion and Eviction Work

Complete Runnable Implementation

use std::collections::HashMap;
use std::hash::Hash;

struct Node<K, V> {
    key: K,
    val: V,
    prev: Option<usize>,
    next: Option<usize>,
}

pub struct LruCache<K, V> {
    capacity: usize,
    map: HashMap<K, usize>,
    entries: Vec<Node<K, V>>,
    head: Option<usize>, // Most Recently Used (MRU) index
    tail: Option<usize>, // Least Recently Used (LRU) index
}

impl<K: Eq + Hash + Clone, V> LruCache<K, V> {
    pub fn new(capacity: usize) -> Self {
        assert!(capacity > 0, "LRU cache capacity must be > 0");
        Self {
            capacity,
            map: HashMap::with_capacity(capacity),
            entries: Vec::with_capacity(capacity),
            head: None,
            tail: None,
        }
    }

    pub fn len(&self) -> usize {
        self.map.len()
    }

    pub fn is_empty(&self) -> bool {
        self.map.is_empty()
    }

    /// Retrieves a reference to the value for `key` and marks it as Most Recently Used in O(1) time.
    pub fn get(&mut self, key: &K) -> Option<&V> {
        let &idx = self.map.get(key)?;
        self.detach(idx);
        self.attach_front(idx);
        Some(&self.entries[idx].val)
    }

    /// Inserts or updates `(key, val)` in O(1) time, evicting the LRU entry if at capacity.
    pub fn put(&mut self, key: K, val: V) -> Option<(K, V)> {
        // Case 1: Key already exists -> update in place and promote to MRU head:
        if let Some(&idx) = self.map.get(&key) {
            self.entries[idx].val = val;
            self.detach(idx);
            self.attach_front(idx);
            return None;
        }

        // Case 2: Cache is at capacity -> evict `self.tail` (LRU) and reuse its slot in-place!
        if self.entries.len() == self.capacity {
            let lru_idx = self.tail.expect("non-empty cache has a tail");
            self.detach(lru_idx);

            let old_node = &mut self.entries[lru_idx];
            self.map.remove(&old_node.key);

            let evicted_key = std::mem::replace(&mut old_node.key, key.clone());
            let evicted_val = std::mem::replace(&mut old_node.val, val);

            self.map.insert(key, lru_idx);
            self.attach_front(lru_idx);
            return Some((evicted_key, evicted_val));
        }

        // Case 3: Cache still has spare capacity -> push a new slot:
        let idx = self.entries.len();
        self.entries.push(Node {
            key: key.clone(),
            val,
            prev: None,
            next: None,
        });
        self.map.insert(key, idx);
        self.attach_front(idx);
        None
    }

    fn detach(&mut self, idx: usize) {
        let prev = self.entries[idx].prev.take();
        let next = self.entries[idx].next.take();

        match prev {
            Some(p) => self.entries[p].next = next,
            None => self.head = next,
        }
        match next {
            Some(n) => self.entries[n].prev = prev,
            None => self.tail = prev,
        }
    }

    fn attach_front(&mut self, idx: usize) {
        self.entries[idx].prev = None;
        self.entries[idx].next = self.head;

        if let Some(old_head) = self.head {
            self.entries[old_head].prev = Some(idx);
        } else {
            self.tail = Some(idx);
        }
        self.head = Some(idx);
    }
}

fn main() {
    let mut cache = LruCache::new(2);

    cache.put("a", 10);
    cache.put("b", 20);

    // Accessing "a" promotes "a" to MRU, making "b" the LRU entry:
    assert_eq!(cache.get(&"a"), Some(&10));

    // Inserting "c" evicts "b" (the LRU entry):
    let evicted = cache.put("c", 30);
    assert_eq!(evicted, Some(("b", 20)));
    assert_eq!(cache.get(&"b"), None);
    assert_eq!(cache.get(&"a"), Some(&10));
    assert_eq!(cache.get(&"c"), Some(&30));

    println!("Evicted LRU item: {evicted:?}, active 'a'={:?}, 'c'={:?}", cache.get(&"a"), cache.get(&"c"));
}

Evicted LRU item: Some(("b", 20)), active 'a'=Some(10), 'c'=Some(30)