Why Standard Maps Fall Short
In modern web applications, caching expensive database queries or external API payloads is essential for maintaining snappy response times. However, primitive JavaScript Map objects grow indefinitely unless manually pruned, leading to eventual memory leaks in long-running services.
To prevent memory exhaustion without adding heavy infrastructure like Redis, a Least Recently Used (LRU) eviction strategy backed by time-to-live (TTL) expiration provides the ideal balance.
Designing the Data Structure
An efficient LRU cache requires O(1) key lookups and O(1) node updates whenever items are accessed or evicted. Combining a JavaScript Map with a Doubly Linked List achieves both requirements seamlessly.
The Complete Implementation
Here is the complete, type-safe implementation written in generic TypeScript:
type Node<K, V> = {
key: K;
value: V;
expiresAt: number | null;
prev: Node<K, V> | null;
next: Node<K, V> | null;
};
export class LRUCache<K, V> {
private capacity: number;
private ttlMs?: number;
private map = new Map<K, Node<K, V>>();
private head: Node<K, V> | null = null;
private tail: Node<K, V> | null = null;
constructor(options: { capacity: number; ttlMs?: number }) {
if (options.capacity <= 0) {
throw new Error("Capacity must be greater than 0");
}
this.capacity = options.capacity;
this.ttlMs = options.ttlMs;
}
get(key: K): V | undefined {
const node = this.map.get(key);
if (!node) return undefined;
if (node.expiresAt && Date.now() > node.expiresAt) {
this.remove(node);
this.map.delete(key);
return undefined;
}
this.moveToHead(node);
return node.value;
}
set(key: K, value: V, customTtlMs?: number): void {
const existing = this.map.get(key);
const ttl = customTtlMs ?? this.ttlMs;
const expiresAt = ttl ? Date.now() + ttl : null;
if (existing) {
existing.value = value;
existing.expiresAt = expiresAt;
this.moveToHead(existing);
return;
}
if (this.map.size >= this.capacity && this.tail) {
this.map.delete(this.tail.key);
this.remove(this.tail);
}
const newNode: Node<K, V> = {
key,
value,
expiresAt,
prev: null,
next: null,
};
this.map.set(key, newNode);
this.addToHead(newNode);
}
delete(key: K): boolean {
const node = this.map.get(key);
if (!node) return false;
this.remove(node);
this.map.delete(key);
return true;
}
clear(): void {
this.map.clear();
this.head = null;
this.tail = null;
}
private addToHead(node: Node<K, V>): void {
node.next = this.head;
node.prev = null;
if (this.head) {
this.head.prev = node;
}
this.head = node;
if (!this.tail) {
this.tail = node;
}
}
private remove(node: Node<K, V>): void {
if (node.prev) {
node.prev.next = node.next;
} else {
this.head = node.next;
}
if (node.next) {
node.next.prev = node.prev;
} else {
this.tail = node.prev;
}
}
private moveToHead(node: Node<K, V>): void {
this.remove(node);
this.addToHead(node);
}
}Usage and Practical Examples
Using the cache in your application is straightforward. You specify a maximum capacity and optionally a default TTL:
const cache = new LRUCache<string, { id: string; name: string }>({
capacity: 100,
ttlMs: 60_000, // 1 minute default TTL
});
// Cache user data
cache.set("user:101", { id: "101", name: "Alice" });
// Custom TTL for specific critical entry (e.g. 5 seconds)
cache.set("user:102", { id: "102", name: "Bob" }, 5_000);
// Retrieve cached item (moves to head as most recently used)
const user = cache.get("user:101");
console.log(user?.name); // "Alice"With this zero-dependency structure in place, all operations execute in constant O(1) time complexity with zero GC overhead.