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

> Learn how to implement LRU Cache in JavaScript with O(1) operations. Discover efficient eviction using a hash map and doubly-linked list for optimal performance.

- Repository: [Oleksii Trekhleb/javascript-algorithms](https://github.com/trekhleb/javascript-algorithms)
- Tags: deep-dive
- Published: 2026-02-24

---

**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`](https://github.com/trekhleb/javascript-algorithms/blob/main/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`](https://github.com/trekhleb/javascript-algorithms/blob/main/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`](https://github.com/trekhleb/javascript-algorithms/blob/main/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:

```javascript
// 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:

```javascript
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`](https://github.com/trekhleb/javascript-algorithms/blob/main/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`](https://github.com/trekhleb/javascript-algorithms/blob/main/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`](https://github.com/trekhleb/javascript-algorithms/blob/main/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`](https://github.com/trekhleb/javascript-algorithms/blob/main/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.