LFU Cache with O(1) get, put (and delete)

Published 24 September 2026

LRU is the cache everyone knows how to build: a hash map plus one doubly linked list, move-to-front on access, evict from the tail. LFU (least frequently used) sounds like a small twist on it: evict the key with the lowest access count. The obvious way to build it is a min-heap keyed on frequency, and that gets you O(log n) per operation.

The interesting part is that you can get O(1) for both get and put without a heap. The idea fits in one sentence:

Keep a separate linked list of keys for every frequency, and track the minimum frequency currently in the cache.

This post builds that up, explains why min_freq is so cheap to maintain, and closes with what changes once you also want delete.

The data structures

Three pieces of state:

key_to_node:   key  -> Node
freq_to_list:  freq -> DoublyLinkedList of Nodes with that frequency
min_freq:      smallest frequency among all cached keys

Each node carries its own frequency and its own list pointers:

class Node:
    key, value, freq, prev, next

So the cache looks like a set of horizontal lists, one per frequency:

freq = 1:   head <-> A <-> C <-> D <-> tail
freq = 2:   head <-> B <-> F <-> tail
freq = 5:   head <-> E <-> tail

min_freq = 1

Order inside a list matters. Ties are common: lots of keys have been read exactly once. The usual tie-breaker is LRU, so each frequency list is kept in recency order: most recently used at the front, least recently used at the back. The eviction victim is then always

freq_to_list[min_freq].tail.prev

Why the node stores prev, next and freq

On get("foo"), foo's frequency goes from, say, 3 to 4. That means removing it from the frequency-3 list and adding it to the frequency-4 list.

If you had to find foo inside the frequency-3 list, you'd be back to O(n). Instead, key_to_node hands you the node directly, and the node knows:

• its freq, which tells you which list it is in, and
• its prev / next, which let you unlink it without walking the list.

key ──► Node(foo)
          freq = 3        ← which list am I in?
          prev / next     ← unlink me in O(1)

Unlinking is O(1), adding to the front of the next list is O(1), and the hash map lookups are O(1). You never search a list.

The operations

get(key)

Say B is in the frequency-2 list:

freq 2:  head <-> A <-> B <-> C <-> tail
                        ^

Accessing B bumps it to frequency 3:

freq 2:  head <-> A <-> C <-> tail
freq 3:  head <-> B <-> tail

The steps:

1. Look up the node. Missing, return -1.
2. Unlink it from freq_to_list[node.freq].
3. If that list is now empty and it was the min_freq list, do min_freq += 1.
4. node.freq += 1, then push the node to the front of the new frequency's list.

Step 3 is the whole trick, and it's worth asking why += 1 is enough. It could look like we need to search for the next non-empty frequency. We don't: the node we just removed is about to land at exactly old_freq + 1. So that list is guaranteed to be non-empty, and nothing can sit below it because old_freq was the minimum.

put(key, value)

Two cases.

Existing key. Update the value and treat it as an access (same frequency bump as get).

New key. If the cache is full, evict the tail of the min_freq list, which is the least recently used key among the least frequently used ones:

min_freq = 2
freq 2:  head <-> X <-> Y <-> Z <-> tail
                              ^ evict

Then insert the new key at frequency 1 and set min_freq = 1.

That last assignment is the second half of the trick. Every new key starts at frequency 1, so after any insert, min_freq is 1. You don't compute it, you just know it.

Frequency gaps are fine

This confused me at first. Suppose a few keys get hammered and then a new key shows up:

freq 1:   A
freq 10:  B <-> C
freq 20:  D

min_freq = 1

There's nothing at frequencies 2 through 9. Does that break anything?

No. If the cache is full and X arrives, we evict from freq_to_list[1] (A), insert X at frequency 1, and min_freq stays 1:

freq 1:   X
freq 10:  B <-> C
freq 20:  D

The gap only matters if min_freq ever has to jump across it, and with just get and put it never does:

• put of a new key resets min_freq to 1, which is the right answer.
• get / update only increases min_freq by exactly 1, and only when the node being bumped emptied the minimum list. That node lands at min_freq + 1, so the new minimum is always right next door.

So with get and put, min_freq moves up one step at a time or drops straight to 1, and both cases are O(1). That's why it keeps working even though the frequencies are sparse.

Complete Python implementation

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.freq = 1
        self.prev = None
        self.next = None


class DoublyLinkedList:
    def __init__(self):
        # sentinels, so add/remove never special-case the ends
        self.head = Node(None, None)
        self.tail = Node(None, None)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def add_front(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
        self.size += 1

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = node.next = None
        self.size -= 1

    def remove_last(self):
        if self.size == 0:
            return None
        node = self.tail.prev
        self.remove(node)
        return node

    def empty(self):
        return self.size == 0


class LFUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.key_to_node = {}   # key  -> Node
        self.freq_to_list = {}  # freq -> DoublyLinkedList (MRU at front)
        self.min_freq = 0

    def _touch(self, node):
        old_freq = node.freq
        old_list = self.freq_to_list[old_freq]
        old_list.remove(node)

        if old_list.empty():
            del self.freq_to_list[old_freq]
            # node is about to land at old_freq + 1, so that is the new minimum
            if self.min_freq == old_freq:
                self.min_freq += 1

        node.freq += 1
        self.freq_to_list.setdefault(node.freq, DoublyLinkedList()).add_front(node)

    def get(self, key):
        node = self.key_to_node.get(key)
        if node is None:
            return -1
        self._touch(node)
        return node.value

    def put(self, key, value):
        if self.capacity == 0:
            return

        node = self.key_to_node.get(key)
        if node is not None:
            node.value = value
            self._touch(node)
            return

        if len(self.key_to_node) == self.capacity:
            lfu_list = self.freq_to_list[self.min_freq]
            victim = lfu_list.remove_last()  # LRU among the least frequent
            if lfu_list.empty():
                del self.freq_to_list[self.min_freq]
            del self.key_to_node[victim.key]

        node = Node(key, value)
        self.key_to_node[key] = node
        self.freq_to_list.setdefault(1, DoublyLinkedList()).add_front(node)
        self.min_freq = 1

A couple of details that are easy to get wrong:

• Delete empty frequency lists. Otherwise freq_to_list slowly fills with dead lists for every frequency a key has ever passed through.
• capacity == 0. Without the early return, the eviction branch reads freq_to_list[0] on the very first put and crashes.
• Update counts as a use. put on an existing key bumps its frequency. LeetCode 460 expects this, and it's the natural reading of "use".

I checked this against a brute-force reference (a plain dict of (value, freq, last_used) that scans for the victim) over a few thousand random sequences of operations, and the two agree.

Why it's actually O(1)

Trace a get:

hash lookup (key_to_node)         O(1)
unlink from old freq list         O(1)   ← node has prev/next
maybe min_freq += 1               O(1)   ← no search, see above
hash lookup (freq_to_list)        O(1)
push to front of new freq list    O(1)

put is the same, plus an eviction that's just remove_last() on a list we already have a handle to. At no point do we walk a list or scan frequencies.

The mental model:

                 key_to_node
                     │
                     ▼
             ┌───────────────┐
             │ Node          │
             │ key, value    │
             │ freq          │
             │ prev / next   │
             └───────┬───────┘
                     │ lives in the list for its freq
          ┌──────────┴──────────┐
          ▼                     ▼
      freq = 2               freq = 5
   A <-> B <-> C             X <-> Y

   min_freq = 2

Access B, and it moves to a fresh frequency-3 list (min_freq stays 2, since A and C are still there). Access A and C too, and the frequency-2 list empties, so min_freq becomes 3. Each step is local.

What about delete(key)?

Here's where it gets tricky. Everything above relied on one fact: min_freq either resets to 1 (on insert) or steps up by exactly 1 (on access). Arbitrary deletion breaks that.

freq 1:    A
freq 10:   B
freq 20:   C

min_freq = 1

Now delete(A). The frequency-1 list is empty, and the correct new min_freq is 10. Nothing local tells you that. The naive fix scans 2, 3, …, 10, which is O(gap) and can be arbitrarily large. A sorted set of active frequencies works but costs O(log n).

The fix is to add a vertical linked list over the frequencies: turn each frequency list into a bucket and chain the buckets together in increasing order. Only frequencies that currently hold at least one key get a bucket, so the chain stays sparse:

min_bucket
    │
    ▼
Bucket(1) <-> Bucket(10) <-> Bucket(20)
    │             │              │
    A             B              C

With that in place:

• Deleting the last key in a bucket unlinks the bucket from the chain in O(1), and if it was the minimum, the new minimum is just bucket.next. No searching, because the chain is the set of non-empty frequencies.
• Bumping a node from frequency f to f+1 inserts a new bucket right after f's bucket if one doesn't already exist. That's O(1) too, since f+1 can only go immediately after f.
• Inserting a new key goes into the bucket at the head of the chain (creating it if the head isn't frequency 1).

In fact, once you have the bucket chain you don't need min_freq at all. The head of the chain is the minimum. This is the design from the well-known O(1) LFU paper (Shah, Mitra & Matani, 2010), and it's what you'd reach for if deletes are part of the API.

Should the cache support delete at all? For a pure eviction cache you can often get away without it. But real caches need invalidation ("this user's profile changed, drop it"), so in practice you want it, and the bucket chain is how you keep it O(1).

Critique

The implementation above is correct (it matches a brute-force reference), and it's the answer an interviewer expects. Here's where it falls short of something I'd ship.

Interface problems

• -1 means "miss", and -1 is also a value. After put("a", -1), get("a") and get("missing") both return -1, and the caller can't tell them apart. That's a LeetCode convention leaking into the API. Return None or a caller-supplied default, or raise KeyError like a dict does.
• Negative capacity is silently unbounded. capacity == 0 is handled, but with capacity = -1 the check len(...) == self.capacity never fires, so the cache grows forever (100 puts leave 100 keys). Reject capacity < 0 in __init__.
• The title promises delete; the code doesn't have it. The bucket chain is only described in prose. Without delete there's no invalidation path, and a cache with no invalidation path will serve stale data.
• No thread safety. _touch is several separate mutations across two dicts and two lists. The GIL makes each bytecode atomic, not the sequence, so two threads calling get can corrupt the lists. A real cache needs a lock around every public method, or a design that buffers reads and applies them in batches (which is what Caffeine does).

The hand-rolled linked list is the slow part

DoublyLinkedList exists because the textbook version is written for C++ or Java. In Python, collections.OrderedDict already is a hash map over a doubly linked list, implemented in C. del od[key], od[key] = None (append at the end) and od.popitem(last=False) (pop the oldest) are all O(1). Swapping it in removes Node, DoublyLinkedList and every pointer update:

from collections import OrderedDict, defaultdict


class LFUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.vals = {}                         # key  -> (value, freq)
        self.lists = defaultdict(OrderedDict)  # freq -> keys, LRU first
        self.min_freq = 0

    def _touch(self, key):
        value, freq = self.vals[key]
        del self.lists[freq][key]
        if not self.lists[freq]:
            del self.lists[freq]
            if self.min_freq == freq:
                self.min_freq += 1
        self.vals[key] = (value, freq + 1)
        self.lists[freq + 1][key] = None

    def get(self, key):
        if key not in self.vals:
            return -1
        self._touch(key)
        return self.vals[key][0]

    def put(self, key, value):
        if self.capacity <= 0:
            return
        if key in self.vals:
            self.vals[key] = (value, self.vals[key][1])
            self._touch(key)
            return
        if len(self.vals) == self.capacity:
            lfu = self.lists[self.min_freq]
            victim, _ = lfu.popitem(last=False)
            if not lfu:
                del self.lists[self.min_freq]
            del self.vals[victim]
        self.vals[key] = (value, 1)
        self.lists[1][key] = None
        self.min_freq = 1

It agrees with the original on 3,000 random operation sequences, and on 200,000 mixed operations against a 500-entry cache it runs about 2x faster (0.04 s against 0.08 s on my machine). It also allocates less. The original creates a Node with a full instance __dict__ per key (no __slots__), plus a new list with two sentinel nodes every time a key reaches a frequency nobody else is at.

The recency order is flipped (oldest first, since OrderedDict appends at the end), but the rule is the same. The -1 is kept here only so the two versions can be compared.

LFU itself is the bigger problem

Even a perfect implementation inherits LFU's weaknesses as a policy:

• Old popularity never expires. Counts only go up. A key that was hammered yesterday and is never read again keeps its high count and outlives everything new. In a test with capacity 3, two keys read 1,000 times each and then never again stayed cached, while a new working set of five keys cycling through the last slot got 0 hits in 1,000 reads.
• New keys can't get established. Every new key enters at frequency 1, which is the eviction end. If the cache is full of established keys, each newcomer is evicted by the next newcomer before it has a chance to earn a second hit.

Production caches fix the policy, not the data structure. Redis's allkeys-lfu keeps a small logarithmic counter per key that decays over time, so old popularity fades. Caffeine's W-TinyLFU estimates frequency in a compact count-min sketch that is periodically halved, and puts a small LRU window in front so new keys get a trial period before they compete on frequency. If you need LFU behaviour in practice, start there rather than with an exact per-key count.

Summary

	get / put only	get / put / delete
Per-key lookup	key -> Node	key -> Node
Per-frequency lists	freq -> DLL	buckets, each holding a DLL
Finding the minimum	min_freq int	head of the bucket chain
Why it's O(1)	min only resets to 1 or steps +1	empty bucket unlinks, next is the new min

The broader lesson: an O(1) structure usually depends on an invariant that makes the "hard" query (here, what's the minimum?) answerable from local information. Adding an operation that breaks the invariant means adding structure to restore it.