LRU Cache - Hash Map + Doubly Linked List

📚 Table of Contents

Problem Statement
Real-World Analogy
Key Insights
Solution Approach
Step-by-Step Walkthrough
Complexity Analysis
Edge Cases
Test Cases
Interview Tips
Key Takeaways

📋 Problem Statement

Implement:

get(key): return value if key exists, else -1
put(key, value): insert/update value and mark key as most recently used

If cache size exceeds capacity, evict the least recently used key.

🎯 Real-World Analogy

Desk With Active Files

You keep a small stack of active files. Touching a file moves it to top. Adding a new file when desk is full removes the oldest untouched file.

💡 Key Insights

Hash map gives O(1) lookup by key.
Doubly linked list gives O(1) move-to-front and O(1) tail eviction.
Head = most recent, tail = least recent.
Use dummy head/tail nodes to simplify pointer operations.

💻 Solution Approach

Time: O(1) per get/put | Space: O(capacity)

Python Implementation

class Node:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None


class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.map = {}

        self.head = Node()  # MRU sentinel
        self.tail = Node()  # LRU sentinel
        self.head.next = self.tail
        self.tail.prev = self.head

    def _add_front(self, node: Node) -> None:
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def _remove(self, node: Node) -> None:
        p, n = node.prev, node.next
        p.next = n
        n.prev = p

    def _move_to_front(self, node: Node) -> None:
        self._remove(node)
        self._add_front(node)

    def get(self, key: int) -> int:
        node = self.map.get(key)
        if not node:
            return -1
        self._move_to_front(node)
        return node.val

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            node = self.map[key]
            node.val = value
            self._move_to_front(node)
            return

        node = Node(key, value)
        self.map[key] = node
        self._add_front(node)

        if len(self.map) > self.capacity:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.key]

JavaScript Implementation

class Node {
  constructor(key = 0, val = 0) {
    this.key = key;
    this.val = val;
    this.prev = null;
    this.next = null;
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();

    this.head = new Node();
    this.tail = new Node();
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  addFront(node) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
  }

  remove(node) {
    const p = node.prev;
    const n = node.next;
    p.next = n;
    n.prev = p;
  }

  moveToFront(node) {
    this.remove(node);
    this.addFront(node);
  }

  get(key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    this.moveToFront(node);
    return node.val;
  }

  put(key, value) {
    if (this.map.has(key)) {
      const node = this.map.get(key);
      node.val = value;
      this.moveToFront(node);
      return;
    }

    const node = new Node(key, value);
    this.map.set(key, node);
    this.addFront(node);

    if (this.map.size > this.capacity) {
      const lru = this.tail.prev;
      this.remove(lru);
      this.map.delete(lru.key);
    }
  }
}

🔍 Step-by-Step Walkthrough

capacity=2, put(1,1), put(2,2), get(1), put(3,3):

After get(1): order is [1,2] (1 most recent).
put(3,3) exceeds capacity, evict key 2.
Cache now contains keys 1 and 3.

⚡ Complexity Analysis

get: O(1) map lookup + O(1) list move.

put: O(1) update/insert + optional O(1) tail eviction.

Space: O(capacity).

🔧 Edge Cases

Updating existing key should not change size.
Repeated gets should preserve cache size and reorder nodes.
Capacity=1 should evict on each new distinct insert.
Missing key should return -1.

🧪 Test Cases

Expected outputs

LRUCache(2); put(1,1); put(2,2); get(1) => 1
put(3,3); get(2) => -1
put(4,4); get(1), get(3), get(4) => -1, 3, 4

💼 Interview Tips

State invariant: list order represents recency.
Explain why singly linked list is insufficient for O(1) arbitrary delete.
Use sentinel nodes to avoid null-branch bugs.

🎓 Key Takeaways

Map + doubly linked list is the canonical O(1) cache design.
Recency updates are just linked-list pointer operations.

← Back to All Algorithms