LRU Cache: Design an O(1) Cache with a Doubly Linked List and Hash Map

An LRU (Least Recently Used) cache evicts the item that hasn't been touched in the longest time once it's full. It's a classic interview question, but it's also exactly what backs real systems: database query caches, CDN edge caches, browser tab memory management, connection pools.

The naive approach — an array you scan for the oldest entry — is O(n) per operation. The trick to O(1) is combining two structures: a hash map for O(1) lookup, and a doubly linked list for O(1) reordering.

The Structure

Every node lives in the linked list AND has a pointer stored in the hash map. head is a sentinel pointing to the most recently used node; tail is a sentinel pointing to the least recently used one, which is the eviction candidate.

The Two Operations

get(key): hash map lookup finds the node in O(1). If found, unlink it from its current position and relink it right after head (it's now the most recently used), then return its value. If not found, return null/miss.

put(key, value): if the key already exists, update its value and move it to the front, same as get. If it's new and capacity is full, remove the node just before tail (the least recently used) from both the list and the hash map, then insert the new node at the front.

Both operations only ever touch a constant number of pointers — no scanning required.

PHP Implementation

class Node
{
    public function __construct(
        public string $key,
        public mixed $value,
        public ?Node $prev = null,
        public ?Node $next = null,
    ) {}
}

class LRUCache
{
    private array $map = [];
    private Node $head;
    private Node $tail;
    private int $capacity;

    public function __construct(int $capacity)
    {
        $this->capacity = $capacity;
        $this->head = new Node('', null);
        $this->tail = new Node('', null);
        $this->head->next = $this->tail;
        $this->tail->prev = $this->head;
    }

    public function get(string $key): mixed
    {
        if (!isset($this->map[$key])) {
            return null;
        }

        $node = $this->map[$key];
        $this->detach($node);
        $this->attachToFront($node);

        return $node->value;
    }

    public function put(string $key, mixed $value): void
    {
        if (isset($this->map[$key])) {
            $node = $this->map[$key];
            $node->value = $value;
            $this->detach($node);
            $this->attachToFront($node);
            return;
        }

        if (count($this->map) >= $this->capacity) {
            $lru = $this->tail->prev;
            $this->detach($lru);
            unset($this->map[$lru->key]);
        }

        $node = new Node($key, $value);
        $this->map[$key] = $node;
        $this->attachToFront($node);
    }

    private function detach(Node $node): void
    {
        $node->prev->next = $node->next;
        $node->next->prev = $node->prev;
    }

    private function attachToFront(Node $node): void
    {
        $node->next = $this->head->next;
        $node->prev = $this->head;
        $this->head->next->prev = $node;
        $this->head->next = $node;
    }
}

The two sentinel nodes (head and tail) exist purely to avoid null checks at the boundaries — every real node always has a valid prev and next to work with.

Common Pitfalls

Forgetting to update the hash map on eviction. If you remove a node from the linked list but leave its entry in $map, the next get() for that key returns a dangling node instead of a miss.

Off-by-one on capacity checks. Check count($this->map) >= $this->capacity before inserting the new node, not after — otherwise the cache temporarily holds capacity + 1 items.

Treating get() as read-only. A cache hit still mutates state — it moves the node to the front. Skipping that step turns your LRU into a plain FIFO cache.

Using an array and array_shift() as the "queue." array_shift() is O(n) because PHP reindexes the array. This defeats the entire point of the exercise — the doubly linked list is what makes eviction O(1).

When to Reach for a Real Implementation

Don't hand-roll this for production unless you have a specific reason (embedding the cache inside a single PHP process with no external dependency, for instance). For anything shared across requests or processes, Redis's own eviction policies (allkeys-lru, volatile-lru) or a library like symfony/cache already solve this correctly and durably. The value of building it yourself is understanding why O(1) requires both structures together — neither one alone gets you there.