Learn how to implement an O(1) LRU (Least Recently Used) Cache using a Hash Map and Doubly Linked List: head/tail dummy nodes, eviction policy, and JavaScript class implementation.
An LRU (Least Recently Used) Cache organizes items in order of use, allowing you to quickly identify which item hasn't been used for the longest time when capacity is reached.
To achieve O(1) lookup and O(1) eviction/insertion, an LRU Cache combines a Hash Map (for fast node lookup) with a Doubly Linked List (for fast node relocation and deletion).
Create dummy head and tail nodes linked together. Map stores key -> DLLNode pointers.
If key exists in map, move its node to the front of DLL (right after head) to mark it Most Recently Used, then return value. If missing, return -1.
If key exists, update value and move node to head. If key is new, create node and insert right after head. If capacity is exceeded, evict node right before tail (Least Recently Used) and delete from map.
1class Node {2 constructor(key, value) {3 this.key = key;4 this.value = value;5 this.prev = null;6 this.next = null;7 }8}9 10class LRUCache {11 constructor(capacity) {12 this.capacity = capacity;13 this.map = new Map();14 15 // Dummy sentinel nodes16 this.head = new Node(0, 0);17 this.tail = new Node(0, 0);18 this.head.next = this.tail;19 this.tail.prev = this.head;20 }21 22 _remove(node) {23 node.prev.next = node.next;24 node.next.prev = node.prev;25 }26 27 _insertAtHead(node) {28 node.next = this.head.next;29 node.next.prev = node;30 this.head.next = node;31 node.prev = this.head;32 }33 34 get(key) {35 if (!this.map.has(key)) return -1;36 37 const node = this.map.get(key);38 this._remove(node);39 this._insertAtHead(node);40 return node.value;41 }42 43 put(key, value) {44 if (this.map.has(key)) {45 this._remove(this.map.get(key));46 }47 48 const newNode = new Node(key, value);49 this.map.set(key, newNode);50 this._insertAtHead(newNode);51 52 if (this.map.size > this.capacity) {53 // Evict LRU node right before tail54 const lru = this.tail.prev;55 this._remove(lru);56 this.map.delete(lru.key);57 }58 }59}60 61// Example usage:62// const cache = new LRUCache(2);63// cache.put(1, 1); cache.put(2, 2);64// cache.get(1); // returns 165// cache.put(3, 3); // evicts key 2!The full interactive roadmap is unlocking — these specialized modules land in upcoming releases.
This feature will be implemented in the next update.
This feature will be implemented in the next update.
This feature will be implemented in the next update.
Explore the full catalog — 30+ algorithms with more unlocking every release.
Test your understanding of LRU Cache Design Algorithm complexity and step mechanics.
Q1.Why is a Doubly Linked List necessary in an LRU Cache alongside a Hash Map?
Q2.What is the purpose of using dummy head and tail sentinel nodes in the Doubly Linked List?
Apply LRU Cache Design Algorithm to real coding interview questions.
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache with O(1) time complexity.
Design and implement a data structure for a Least Frequently Used (LFU) cache.