🔁 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

1LRUCache.prototype._remove = function (node) {
2    node.prev.next = node.next;
3    node.next.prev = node.prev;
4};

✅ 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

1LRUCache.prototype._insert = function (node) {
2    const prev = this.right.prev;
3    const next = this.right;
4    prev.next = node;
5    node.prev = prev;
6    node.next = next;
7    next.prev = node;
8};

✅ 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 👇

1// Node class for the doubly linked list
2class Node {
3    constructor(key, value) {
4        this.key = key;
5        this.value = value;
6        this.prev = null;
7        this.next = null;
8    }
9}
10
11
12
13var LRUCache = function (capacity) {
14    this.capacity = capacity;
15    this.cache = new Map(); // key → node
16
17    // Dummy nodes: left = LRU end, right = MRU end
18    this.left = new Node(0, 0);
19    this.right = new Node(0, 0);
20    this.left.next = this.right;
21    this.right.prev = this.left;
22};
23
24// Removes a node from the doubly linked list
25LRUCache.prototype._remove = function (node) {
26    node.prev.next = node.next;
27    node.next.prev = node.prev;
28};
29
30// Inserts a node at the MRU (right) end
31LRUCache.prototype._insert = function (node) {
32    const prev = this.right.prev;
33    const next = this.right;
34    prev.next = node;
35    node.prev = prev;
36    node.next = next;
37    next.prev = node;
38};
39
40// Get a value by key and update it to be most recent
41LRUCache.prototype.get = function (key) {
42    if (this.cache.has(key)) {
43        const node = this.cache.get(key);
44        this._remove(node);  // remove from current position
45        this._insert(node);  // re-insert as most recent
46        return node.value;
47    }
48    return -1;
49};
50
51// Insert or update a key-value pair
52LRUCache.prototype.put = function (key, value) {
53    if (this.cache.has(key)) {
54        this._remove(this.cache.get(key));
55    }
56
57    const node = new Node(key, value);
58    this.cache.set(key, node);
59    this._insert(node);
60
61    // Evict LRU if capacity exceeded
62    if (this.cache.size > this.capacity) {
63        const lru = this.left.next;  // least recently used node
64        this._remove(lru);
65        this.cache.delete(lru.key);
66    }
67};

🧠 Time and Space Complexity

✅ 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.