Leetcode - 146. LRU Cache

🔁 Building an LRU Cache in JavaScript (The Right Way)

Imagine you're building a browser, an in-memory database, or any service where you want to store recently accessed items and automatically discard the least-used ones. You need an LRU Cache – a smart data structure that gives you:

• O(1) access to items
• Automatic eviction of the least recently used item when capacity is exceeded

In this post, we’ll build an efficient LRU Cache using JavaScript, a Map, and a Doubly Linked List. Let's dive in! 👇

---

🚀 What is an LRU Cache?

LRU stands for Least Recently Used. The idea is simple:

• Store a fixed number of key-value pairs
• When you get or put, the item becomes the most recently used
• If the cache exceeds capacity, evict the least recently used item

This keeps your cache optimized, fast, and memory-efficient.

---

🧠 What We’ll Use

We’ll combine two data structures:

1. Map – stores key → node (for O(1) lookups)
2. Doubly Linked List – tracks the order of usage from least recent (left) to most recent (right)

We also use two dummy nodes (left and right) to make insertions/removals cleaner without edge-case checks.

---

🔧 Our Custom Helper Methods

To keep our logic clean, we write two internal utility methods.

---

1. _remove(node) – Remove Node from List

LRUCache.prototype._remove = function (node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
};

✅ Purpose: Detach a node from the doubly linked list.

📍 When it's used:

• When an existing key is accessed (to reinsert it as most recent)
• When evicting the least recently used node

---

2. _insert(node) – Insert Node at MRU End

LRUCache.prototype._insert = function (node) {
    const prev = this.right.prev;
    const next = this.right;
    prev.next = node;
    node.prev = prev;
    node.next = next;
    next.prev = node;
};

✅ Purpose: Always insert a node just before the right dummy (i.e., mark it as most recently used)

📍 When it's used:

• After inserting a new node
• After accessing an existing node (to update its position)

---

🤫 Why the _ prefix in _remove and _insert?

It’s just a naming convention. It signals that these methods are internal helpers and shouldn’t be used outside the class. JavaScript doesn't enforce private methods in traditional ES5 syntax, so _ helps you communicate intent.

---

🧱 Full LRU Cache Implementation

Here’s the complete working code 👇

// Node class for the doubly linked list
class Node {
    constructor(key, value) {
        this.key = key;
        this.value = value;
        this.prev = null;
        this.next = null;
    }
}



var LRUCache = function (capacity) {
    this.capacity = capacity;
    this.cache = new Map(); // key → node

    // Dummy nodes: left = LRU end, right = MRU end
    this.left = new Node(0, 0);
    this.right = new Node(0, 0);
    this.left.next = this.right;
    this.right.prev = this.left;
};

// Removes a node from the doubly linked list
LRUCache.prototype._remove = function (node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
};

// Inserts a node at the MRU (right) end
LRUCache.prototype._insert = function (node) {
    const prev = this.right.prev;
    const next = this.right;
    prev.next = node;
    node.prev = prev;
    node.next = next;
    next.prev = node;
};

// Get a value by key and update it to be most recent
LRUCache.prototype.get = function (key) {
    if (this.cache.has(key)) {
        const node = this.cache.get(key);
        this._remove(node);  // remove from current position
        this._insert(node);  // re-insert as most recent
        return node.value;
    }
    return -1;
};

// Insert or update a key-value pair
LRUCache.prototype.put = function (key, value) {
    if (this.cache.has(key)) {
        this._remove(this.cache.get(key));
    }

    const node = new Node(key, value);
    this.cache.set(key, node);
    this._insert(node);

    // Evict LRU if capacity exceeded
    if (this.cache.size > this.capacity) {
        const lru = this.left.next;  // least recently used node
        this._remove(lru);
        this.cache.delete(lru.key);
    }
};

---

🧠 Time and Space Complexity

Operation	Time Complexity	Why
get	O(1)	Map lookup + pointer updates
put	O(1)	Map insert + pointer operations
Space	O(N)	Stores up to capacity nodes

---

✅ Summary

By combining a Map and a Doubly Linked List, we achieve:

• O(1) performance for both get and put
• Clean and predictable memory eviction
• Modular, readable code with private helper functions

This structure is battle-tested and used across real-world systems — from operating system memory managers to Redis and beyond.

---