Building an LRU Cache with O(1) Operations

Implement the classic eviction cache using a doubly-linked list encoded in a key-value store

By SysAdmin · Published 2026-05-27

Building an LRU Cache with O(1) Operations

Every database, CDN, and browser uses an LRU cache. It's the most-asked system design data structure — and building one from scratch teaches you why.

1. The Problem

An LRU (Least Recently Used) cache holds a fixed number of key-value pairs. When full, it evicts the entry that hasn't been accessed for the longest time. Both get and put must run in O(1) amortized time.

Our challenge:

• get(key) returns the value and marks it as most-recently-used
• put(key, value) inserts or updates, evicting the LRU entry if at capacity
• containsKey(key) checks existence without affecting recency
• All backed by an external KV store — not just a Java LinkedHashMap

2. The Naïve Approach (and Why It Fails)

Map<String, String> cache = new HashMap<>();
List<String> accessOrder = new ArrayList<>();

public String get(String key) {
    accessOrder.remove(key);   // O(n)!
    accessOrder.add(key);
    return cache.get(key);
}

ArrayList.remove(Object) is O(n) — it scans and shifts elements. With a cache of 100K entries, every get becomes a 100K scan. This defeats the entire purpose of a cache.

3. The Right Model

The classic solution is a HashMap + Doubly Linked List. But since we must use an external KV store, we encode the linked-list pointers directly in the stored values:

KV entry for key "k":  value + '\\u001F' + prevKey + '\\u001F' + nextKey

Using the Unit Separator character (U+001F) as a delimiter, each KV entry contains:

• The actual cached value
• A pointer to the previous key (toward LRU/tail)
• A pointer to the next key (toward MRU/head)

We maintain head (most recently used) and tail (least recently used) as in-memory pointers.

4. The Implementation, Walked Through

The Interface

public interface LRUCacheContract {
    void init(int capacity);
    String get(String key);
    void put(String key, String value);
    boolean remove(String key);
    int size();
    boolean containsKey(String key);
}

Core Operations

Every get and put does three things:

1. Detach the node from its current position in the list
2. Add it to the head (most recently used)
3. If at capacity, evict the tail (least recently used)

private void detach(String key, String raw) {
    String p = prev(raw), n = next(raw);
    // Stitch prev and next together
    if (p != null) {
        String pr = kv.get(p);
        kv.put(p, encode(val(pr), prev(pr), n));
    } else {
        head = n;  // was the head
    }
    if (n != null) {
        String nr = kv.get(n);
        kv.put(n, encode(val(nr), p, next(nr)));
    } else {
        tail = p;  // was the tail
    }
}

private void addHead(String key, String v) {
    kv.put(key, encode(v, null, head));
    if (head != null) {
        String hr = kv.get(head);
        kv.put(head, encode(val(hr), key, next(hr)));
    }
    head = key;
    if (tail == null) tail = key;
}

⚠️ Trap: containsKey must NOT update recency. The grader checks this — if containsKey moves a key to the head, the wrong entry gets evicted.

Eviction

private void evictTail() {
    if (tail == null) return;
    String victim = tail;
    String raw = kv.get(victim);
    if (raw != null) detach(victim, raw);
    kv.delete(victim);
    size--;
}

5. Performance

Every operation does a constant number of KV store calls:

• get: 1 read + at most 4 writes (detach old position + add head)
• put: 1 read + at most 5 writes (detach + add head + maybe evict tail)
• containsKey: 1 read, zero writes

All O(1) in terms of cache size — the number of KV operations doesn't grow with N.

6. What the Grader Checks

7. Takeaways

1. Encode pointers in values. When your storage layer is a flat KV store, you can build any data structure by encoding pointers (prev/next keys) in the values themselves.

1. containsKey ≠ get semantically. In a real cache (Redis, Memcached), checking existence doesn't bump the TTL. Your LRU must make the same distinction.

1. Synchronized is fine for correctness. The grader tests concurrent access — coarse locking via synchronized is the simplest correct approach for an in-process cache wrapper.

👉 Try it yourself: LRU Cache on Cruscible