LRU Cache Implementation in JavaScript: O(1) Operations and Efficient Eviction

The LRU Cache in trekhleb/javascript-algorithms achieves average O(1) time complexity for both retrieval and insertion by combining a hash map for instant key lookup with a doubly-linked list that maintains access order through constant-time pointer manipulation.

The Least Recently Used (LRU) Cache is a fundamental data structure that optimizes memory usage by evicting the oldest accessed items when capacity is reached. In the trekhleb/javascript-algorithms repository, the implementation demonstrates how to build a high-performance LRU Cache in JavaScript using complementary data structures that ensure deterministic eviction behavior without sacrificing speed.

The Data Structures Behind O(1) LRU Cache Performance

The implementation in src/data-structures/lru-cache/LRUCache.js relies on two core components working in tandem to guarantee constant-time operations.

Hash Map for Instant Lookup

The nodesMap property stores direct references from cache keys to their corresponding doubly-linked list nodes. This hash map enables O(1) lookup time when retrieving or updating values, as the implementation never needs to traverse the list to locate a specific key.

Doubly-Linked List for Access Ordering

The cache maintains a doubly-linked list using dummy head and tail nodes. The list orders items from least-recently used (immediately after head) to most-recently used (immediately before tail). Because each node contains prev and next pointers, the implementation can reposition or remove any node in constant time by adjusting only local pointers.

Core LRU Cache Operations

The efficiency of the LRU Cache stems from how it handles four primary operations: insertion, retrieval, promotion, and eviction.

Inserting and Updating Values with set()

When set(key, value) is called, the implementation first checks nodesMap for the key. If present, it updates the node's value and calls promote(node) to move it to the most-recent position. If the key is new, it creates a LinkedListNode, appends it to the list via append(node), and adds it to nodesMap. If the size exceeds capacity after insertion, the implementation evicts the LRU entry.

Retrieving Values with get()

The get(key) method performs a constant-time lookup in nodesMap. If the key exists, the implementation calls promote(node) to mark the entry as recently used before returning its value. If the key is not found, it returns undefined.

Promoting Nodes to Most-Recent

The promote(node) method ensures that accessed items move to the tail of the list. It accomplishes this by first calling evict(node) to unlink the node from its current position, then append(node) to insert it before the dummy tail. Both operations modify only the immediate neighboring nodes' pointers, preserving O(1) complexity.

Evicting the Least-Recently-Used Entry

When the cache exceeds its capacity, the evict method removes the node immediately following the dummy head—the least-recently used item. It unlinks the node by connecting head.next to node.next, removes the key from nodesMap, and decrements the size. Because the LRU item is always at the front of the list, no traversal is required, ensuring O(1) eviction.

Implementation Details in trekhleb/javascript-algorithms

The repository provides two implementations of the LRU Cache in src/data-structures/lru-cache/.

The primary implementation in LRUCache.js manually manages the doubly-linked list and hash map as described above. It defines a LinkedListNode class with key, value, next, and prev properties, and the LRUCache class encapsulates the nodesMap, dummy head/tail nodes, and the capacity limit.

For environments where code simplicity is preferred over explicit pointer management, the repository also includes LRUCacheOnMap.js. This alternative leverages JavaScript's native Map object, which maintains insertion order. It achieves similar O(1) performance by using Map.prototype.delete() followed by Map.prototype.set() to simulate promotion, and evicts by removing the first entry via Map.prototype.keys().next().

Practical Example: Using the LRU Cache

The following example demonstrates the manual linked-list implementation:

// Import the LRU cache implementation
import LRUCache from './src/data-structures/lru-cache/LRUCache.js';

// Create a cache that can hold up to 3 items
const cache = new LRUCache(3);

// Populate the cache
cache.set('a', 1);
cache.set('b', 2);
cache.set('c', 3);

// Access 'a' – this promotes 'a' to most-recent
console.log(cache.get('a')); // 1

// Insert a new entry, triggering eviction of the LRU item ('b')
cache.set('d', 4);

// 'b' has been evicted; trying to get it returns undefined
console.log(cache.get('b')); // undefined

// The cache now holds: a (most-recent), c, d (least-recent)

The same usage pattern works with the Map-based version:

import LRUCacheOnMap from './src/data-structures/lru-cache/LRUCacheOnMap.js';

const cache = new LRUCacheOnMap(2);
cache.set(1, 'one');
cache.set(2, 'two');
cache.get(1);        // promotes 1
cache.set(3, 'three'); // evicts key 2

Summary

• The LRU Cache combines a hash map (nodesMap) for O(1) key lookup with a doubly-linked list for O(1) reordering and eviction.
• Promotion (moving accessed items to most-recent) and eviction (removing least-recent) both execute in constant time via pointer manipulation.
• The implementation in src/data-structures/lru-cache/LRUCache.js uses dummy head and tail nodes to simplify boundary conditions and avoid null checks.
• An alternative LRUCacheOnMap.js leverages native JavaScript Map insertion ordering for a more concise implementation with identical asymptotic complexity.

Frequently Asked Questions

Why does the LRU Cache use a doubly-linked list instead of an array or a singly-linked list?

A doubly-linked list allows O(1) removal of arbitrary nodes when they are accessed or evicted. Arrays require O(n) shifting to remove elements from the middle or front, while singly-linked lists cannot efficiently move a node to the tail without traversing from the head to find its predecessor.

What is the time complexity of the LRU Cache operations?

Both get and set operations run in average O(1) time. The hash map provides constant-time lookup, while the doubly-linked list enables constant-time promotion of accessed nodes and eviction of the least-recently used entry via pointer updates.

How does the alternative LRUCacheOnMap.js implementation work without a manual linked list?

This version exploits the fact that JavaScript's native Map preserves insertion order. When a key is accessed, it is deleted and re-inserted to move it to the "most recent" end. Eviction simply removes the first entry returned by map.keys().next(), achieving O(1) operations with less code.

When should I use the manual linked list implementation versus the Map-based version?

Use the manual implementation in LRUCache.js when you need explicit control over memory layout, are working in environments where Map iteration order behavior might vary, or are learning the fundamental mechanics of pointer manipulation. Use LRUCacheOnMap.js for production code where brevity and maintainability are priorities, as it reduces the risk of pointer-related bugs while maintaining identical performance characteristics.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}