Hashmap + Doubly Linked List (LRU and LFU)

Some designs need two things at once: find any item by key in $O(1)$ , and keep the items in an order you can change in $O(1)$ (move to front, drop the oldest). A dict alone has no cheap reordering, and a list alone has no cheap lookup. Put them together, with the dict pointing straight at linked-list nodes, and both operations become constant time. LRU and LFU caches are the classic cases.

The idea#

The doubly linked list holds the order. Removing a node you already have a pointer to is $O(1)$ , because it knows both neighbors. Appending at one end is $O(1)$ too. The dict maps key -> node, so you never walk the list to find something.

In an LRU cache the list runs from least recent (head side) to most recent (tail side):

get(key): look up the node, unlink it, append it at the tail.
put(key, value): if the key exists, update and move it to the tail. If the cache is full, evict head.next and delete its key from the dict.

Two details make the code short and correct:

Sentinel head and tail. Dummy nodes at both ends mean every real node always has a prev and a next. Unlink and append never need a None check, even for the first or last item.
The node stores its own key. On eviction you start from the node (head.next), and you need its key to delete it from the dict.

This works because each structure covers the other's weak spot. The dict jumps straight to a node, and a node that knows both neighbors can leave the list without a walk. The diagram shows both pointers at work.

An LRU cache: a dict maps keys 7, 2 and 9 to nodes in a doubly linked list between a head and a tail sentinel; the node next to head is evicted, and a touched node moves next to tail

How to spot it#

The wording usually names the order you have to maintain.

Cue in the problem	What it points to
"O(1) `get` and `put`" plus "evict least recently used"	dict + DLL (LRU)
"evict least frequently used, ties by least recent"	dict + one ordered bucket per frequency (LFU)
"move to front", "most recent first", "bounded history"	a list you reorder by node, found by key
"go back / forward k steps"	check first whether an array plus an index is simpler

Template#

Here are the LRU operations from above, written with sentinels. Each one is $O(1)$ .

init(capacity):
    map = empty dict                 # key -> node
    head, tail = two sentinel nodes, linked to each other
remove(node):                        # unlink: neighbors point past it
    node.prev.next = node.next; node.next.prev = node.prev
append(node):                        # tail side = most recent
    link node between tail.prev and tail
get(key):
    if key not in map: return -1
    remove(map[key]); append(map[key])   # a read is a use
    return the node's value
put(key, value):
    if key in map: remove(map[key])      # refresh recency on update too
    else if map is full:
        lru = head.next                  # head side = least recent
        remove(lru); delete lru.key from map
    map[key] = new node(key, value); append it

You don't always have to build this by hand. In Python, collections.OrderedDict is exactly a dict plus a doubly linked list. move_to_end(key) refreshes recency and popitem(last=False) evicts the oldest, so an LRU cache fits in a dozen lines. Interviewers often ask for the manual version anyway, to see that you know what the library is doing.

When an array beats a linked list#

Not every reordering problem needs a linked list, though. A linked list reorders in $O(1)$ , but it can only move one node at a time. If the access pattern is "jump k steps", an array plus an index is often better.

Operation	Doubly linked list	Array + index
append a new item	$O(1)$	$O(1)$ amortized
move k steps back or forward	$O(k)$ , walks nodes	$O(1)$ , direct jump
Memory	a node object per item	compact slots

Pitfalls#

Most bugs here come from the dict and the list falling out of sync. The LFU items refer to the min_freq counter covered in the hints.

Not deleting the evicted key from the dict. The node leaves the list but stays reachable from the map. Storing the key in the node is what makes the delete possible.
Not refreshing recency on put of an existing key. An update is a use, so the key must move to the most-recent end.
Checking capacity before handling an existing key. Updating a key in a full cache must not evict anything.
LFU: forgetting min_freq = 1 on insert, or bumping min_freq when the old bucket still has keys.
Capacity 0. put must be a no-op, otherwise LFU pops from an empty bucket.
Using list.pop(0) for eviction. It is $O(n)$ , which defeats the point of the design.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with LRU Cache.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: LRU Cache

This is the template. Build the manual version with sentinels first, then try the OrderedDict version with move_to_end and popitem(last=False).

Hint: LFU Cache

LFU evicts the key with the lowest use count, and breaks ties by least recent use. Keep three maps: key -> value, key -> count, and count -> OrderedDict of keys. Each bucket is a tiny LRU (used as an ordered set), so popitem(last=False) on the lowest bucket evicts the right key.

Hint: LFU Cache: finding the lowest bucket

Keep a min_freq and never search for it. On access, a key moves from count f to f + 1; if f was the minimum and its bucket is now empty, the new minimum is exactly f + 1. On insert, a new key has count 1, so min_freq resets to 1. With capacity 0, put must do nothing.

Hint: Design Browser History

A doubly linked list works: visit links a new node after the current one, which drops the forward history in $O(1)$ . But back and forward then walk steps nodes. A dynamic array with a current index and a last high-water mark jumps in $O(1)$ : visit writes at current + 1 and sets last = current, back goes to max(0, current - steps) and forward to min(last, current + steps).

Hint: Design Browser History: follow-ups

To cap the history (for example at 10,000 entries), drop the oldest, or use a fixed-size circular buffer. Guard current with a lock if back and visit can race.

Hint: Design Circular Queue

With linked nodes, preallocate k nodes, link the last back to the first, and move front and rear pointers around the ring. A size counter tells full from empty when the two pointers meet. The array version, which is more common, is in Sliding Time Window.

Hint: Logger Rate Limiter

The base answer is a dict of message to last printed time. That dict grows forever. One way to bound it is an OrderedDict capped at a maximum size, which trades the exact time rule for a hard memory bound. Other ways are in Sliding Time Window.

Key takeaways#

The dict gives $O(1)$ lookup and the doubly linked list gives $O(1)$ reordering. You need both pointers: key to node, and node to neighbors.
Sentinel head and tail nodes remove every edge case in unlink and append.
Store the key inside the node so eviction can clean up the dict.
LFU is an ordered bucket per count plus a min_freq that only moves up by one on access or resets to 1 on insert.
If the access pattern is "jump k steps", an array plus an index can beat a linked list.
For thread safety, one lock around each public method is the simple answer, since every operation touches both the dict and the list.

Core idea#

A dict gives $O(1)$ lookup and a doubly linked list gives $O(1)$ reordering. The dict maps key -> node, so both operations stay constant time. LRU and LFU caches are the classic cases.

Key points#

LRU list order: least recent at the head side, most recent at the tail side.
get: unlink the node and append it at the tail. put when full: evict head.next.
Sentinel head and tail nodes remove every None check in unlink and append.
The node stores its own key, so eviction can delete it from the dict.
collections.OrderedDict is a dict plus a doubly linked list. Interviewers often still ask for the manual version.
LFU keeps key -> value, key -> count and count -> OrderedDict. Each bucket is a tiny LRU for ties.
LFU min_freq: on access, it moves to f + 1 only if bucket f was the minimum and is now empty. On insert, it resets to 1.
Thread safety: one lock around each public method.

List or array#

Operation	Doubly linked list	Array + index
`visit`	$O(1)$	$O(1)$ amortized
`back(k)`, `forward(k)`	$O(k)$	$O(1)$ jump

Design Browser History jumps k steps, so it is better as an array with current and a last high-water mark.

Template#

get(key):
    if key not in map: return -1
    unlink map[key]; append it at the tail     # most recent
    return its value
put(key, value):
    if key in map: unlink map[key]             # refresh recency
    else if map is full:
        lru = head.next                        # least recent
        unlink lru; delete lru.key from map
    map[key] = new node(key, value); append it at the tail

Pitfalls#

Not deleting the evicted key from the dict.
Not refreshing recency when put updates an existing key.
Checking capacity before handling an existing key. An update must not evict.
LFU: forgetting min_freq = 1 on insert. Capacity 0 must make put a no-op.
Using list.pop(0) for eviction. It is $O(n)$ .

Say it in an interview#

"The dict finds the node, and the linked list moves it in O(1)."
"LFU is an LRU bucket per count, plus a min_freq that never needs a search."