TLDR: An LRU (Least Recently Used) Cache evicts the item that hasn't been accessed the longest when it's full. The classic implementation combines a HashMap (O(1) lookup) with a Doubly Linked List (O(1) move-to-front) for overall O(1) get and put.

---

📖 The Browser History Analogy

Your browser "Back" button stores the pages you visited most recently. If you visit 100 pages and your browser only keeps 10 in memory, it drops the oldest one.

LRU says: the item you haven't needed in the longest time is the least valuable — evict it first.

The classic challenge is implementing this in O(1) for both get and put. A hash map gives O(1) lookup but can't maintain order. A linked list maintains order but gives O(n) lookup. The insight: use both together.

---

🔢 The HashMap + Doubly Linked List Architecture

flowchart LR
    HashMap["HashMap\n(key → node pointer)"] --> DLL["Doubly Linked List\nHead (MRU) ←→ ... ←→ Tail (LRU)"]

• HashMap: Maps each key to its Node in the list — O(1) access.
• Doubly Linked List: Maintains access order. Head = Most Recently Used, Tail = Least Recently Used.
• On get(key): find the node (O(1) via map), move it to head (O(1) via pointer manipulation).
• On put(key, val) when full: remove tail node (O(1)), delete its key from map, insert new node at head.

---

⚙️ Step-by-Step Trace: Capacity = 3

Key: get(1) bumped 1 to head, so 3 became the new tail. When 4 arrives, 2 gets evicted — not 3.

---

🧠 Java Implementation

import java.util.HashMap;

public class LRUCache {
    private static class Node {
        int key, val;
        Node prev, next;
        Node(int k, int v) { key = k; val = v; }
    }

    private final int capacity;
    private final HashMap<Integer, Node> map = new HashMap<>();
    // Sentinel nodes simplify boundary conditions
    private final Node head = new Node(0, 0);  // Most Recent side
    private final Node tail = new Node(0, 0);  // Least Recent side

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node n = map.get(key);
        moveToHead(n);
        return n.val;
    }

    public void put(int key, int val) {
        if (map.containsKey(key)) {
            Node n = map.get(key);
            n.val = val;
            moveToHead(n);
        } else {
            Node n = new Node(key, val);
            map.put(key, n);
            insertAtHead(n);
            if (map.size() > capacity) {
                Node lru = removeTail();
                map.remove(lru.key);
            }
        }
    }

    private void moveToHead(Node n) {
        removeNode(n);
        insertAtHead(n);
    }
    private void removeNode(Node n) {
        n.prev.next = n.next;
        n.next.prev = n.prev;
    }
    private void insertAtHead(Node n) {
        n.next = head.next;
        n.prev = head;
        head.next.prev = n;
        head.next = n;
    }
    private Node removeTail() {
        Node lru = tail.prev;
        removeNode(lru);
        return lru;
    }
}

Sentinel nodes (head and tail) eliminate null checks at list boundaries — every real node always has a prev and next.

---

⚖️ Thread Safety: From Single-Threaded to Concurrent

The basic implementation above is not thread-safe. For multi-threaded cache (e.g., shared across API threads):

For production caches, most teams use a battle-tested library like Caffeine (Java) or functools.lru_cache (Python) rather than rolling their own.

---

📌 Summary

• LRU evicts the item not accessed the longest — ideal when recency correlates with future access probability.
• HashMap + Doubly Linked List gives O(1) get and put.
• Sentinel head/tail nodes simplify insertion and removal at boundaries.
• For thread safety, synchronized methods are a good starting point; Caffeine or Guava Cache for production.

---

📝 Practice Quiz

1. What two data structures combine to give LRU Cache O(1) get and O(1) put?

   • A) Array + Binary Heap
   • B) HashMap + Doubly Linked List
   • C) TreeMap + Queue
     Answer: B

2. When get(key) is called on a key that exists, what must happen besides returning the value?

   • A) Increment a hit counter.
   • B) Move the accessed node to the head of the list (mark as Most Recently Used).
   • C) Check if the cache is full and possibly evict.
     Answer: B

3. Why are sentinel head and tail nodes used?

   • A) They store the MRU and LRU values as a shortcut.
   • B) They eliminate null-pointer checks at list boundaries — every real node always has a non-null prev and next.
   • C) They act as locks for thread safety.
     Answer: B

---