Linked lists with hash maps

Problem

"Design" problems ask you to build a small data structure with a promised cost for each operation, usually O(1). No single textbook structure meets all the promises, so you combine two: one to answer where is it? and one to answer what comes next? The skill is deciding which question each structure answers, and keeping them in agreement after every operation.

Intuition

Think of a cloakroom. Coats hang on a rail in the order they were last used, with the newest at one end. To find yours, the attendant keeps a ticket stub that says exactly which hook it is on, so there is no searching. Taking a coat to use it and putting it back at the newest end is just lifting it off its hook and hanging it at the end of the rail, which touches only the neighbours of that hook. When the rail is full and a new coat arrives, the attendant takes the coat at the oldest end and tears up its stub. The rail is the linked list, the stubs are the hash map, and neither is any use without the other.

The pattern generalises. Whenever you need a lookup by key and a maintained order, let the map store the list node, not just the value. A node already knows its neighbours, so removing it needs no search.

The blue key is the most recently used. The amber key was at the oldest end when the cache was full and a new key arrived. A hit or an update moves its key back to the blue end.

Mechanics

The least recently used cache

Invariant. The map contains exactly the keys that are in the list, each mapped to its own node, and the list runs from most recently used (next to a front sentinel) to least recently used (next to a back sentinel). Every operation must preserve both facts, and it can do so with three constant-time moves: look up a node in the map, unlink a node from where it is, and link a node in at the front.

• get(key). Miss: return −1. Hit: unlink the node, link it at the front, return its value.
• put(key, value). Existing key: update the value, then move the node to the front. New key: if the cache is full, take the node next to the back sentinel, unlink it and delete its key from the map, then create the new node, add it to the map and link it at the front.

Why doubly linked. Unlinking a node means making its predecessor point at its successor. In a singly linked list you would have to walk from the front to find the predecessor, which costs O(n). The prev pointer makes that a constant-time step. Why the node stores its key. When the back node is evicted, the only thing you hold is the node, and you need its key to delete the map entry. Why sentinels. With a front and a back dummy node, "first node" and "last node" are never special cases, so link and unlink have no if for empty or single-element lists.

Copying with a map

A list whose nodes also carry a random pointer cannot be copied in one pass, because when you copy node i the copy of its random target may not exist yet. The fix is two passes. Pass one walks the list and makes one copy per node, recording copies[original] = copy. Pass two walks again and sets each copy's next and random to copies[original.next] and copies[original.random]. The map is what turns "the node this pointer targets" into "its copy". Mapping None to None removes the null checks.

There is an O(1)-space version: insert each copy directly after its original, so the copy of any node is node.next; set each copy's random from original.random.next; then split the two interleaved lists apart. The map version is easier to get right and is the one to write first.

Straight lines are next, blue arcs are random. The copy of every node has been wired to the copy of its targets, never to an original.

Frequency levels

The most frequent element stack pops the most frequent value, and among equals the one pushed last. Keep count[value] and a list of stacks, where stack k holds one entry of a value each time its count reached k. Pushing a value whose count becomes c appends it to stack c. Popping takes the top of the highest non-empty stack. A value with count 3 appears once in each of stacks 1, 2 and 3, so after popping it from stack 3 it is still correctly in stacks 1 and 2 with count 2. The highest stack is always the highest frequency, and within a stack the top is the latest push, which is the tie-break.

The least-frequently-used cache is the same idea with the roles reversed: keep a recency list for each frequency, plus the current minimum frequency. A hit moves the key from its list to the next frequency's list; if the old list was the minimum and is now empty, the minimum goes up by one. A new key resets the minimum to 1.

Each column is one stack, bottom at the base. The amber entry, the top of the highest level, is the value the next pop returns.

Worked example

LRU cache with capacity 3. The order column lists keys from most to least recently used.

The first eviction is key b: it was the oldest because get(a) had just moved a to the front. The second put of c updates the value and moves it to the front without evicting. After the last step the cache holds d, e, c.

Copy a list with random pointers. The list has 5 nodes numbered from 0. Pass one creates 5 copies. Pass two wires them:

Frequency stack. Push 4, 6, 4, 8, 6, 4, then pop four times:

The pops return 4, 6, 4, 8. The value 4 comes first because it reached count 3, the highest; the later pops step down to level 2 and then level 1.

Implementation

class Node:
    __slots__ = ("key", "val", "prev", "next")

    def __init__(self, key=0, val=0):
        self.key, self.val = key, val
        self.prev = self.next = None


class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.nodes = {}
        self.front, self.back = Node(), Node()       # sentinels
        self.front.next, self.back.prev = self.back, self.front

    def _unlink(self, node):
        node.prev.next, node.next.prev = node.next, node.prev

    def _push_front(self, node):
        node.prev, node.next = self.front, self.front.next
        self.front.next.prev = node
        self.front.next = node

    def get(self, key):
        node = self.nodes.get(key)
        if node is None:
            return -1
        self._unlink(node)
        self._push_front(node)
        return node.val

    def put(self, key, val):
        node = self.nodes.get(key)
        if node:
            node.val = val
            self._unlink(node)
        else:
            if len(self.nodes) == self.cap:
                oldest = self.back.prev
                self._unlink(oldest)
                del self.nodes[oldest.key]           # why the node keeps its key
            node = self.nodes[key] = Node(key, val)
        self._push_front(node)


class RandomNode:
    def __init__(self, val=0, next=None, random=None):
        self.val, self.next, self.random = val, next, random


def copy_random_list(head):
    copies = {None: None}
    cur = head
    while cur:
        copies[cur] = RandomNode(cur.val)
        cur = cur.next
    cur = head
    while cur:
        copy = copies[cur]
        copy.next, copy.random = copies[cur.next], copies[cur.random]
        cur = cur.next
    return copies[head]


class FreqStack:
    def __init__(self):
        self.count = {}
        self.levels = []                             # levels[k] holds values whose count reached k + 1

    def push(self, x):
        c = self.count[x] = self.count.get(x, 0) + 1
        if c > len(self.levels):
            self.levels.append([])
        self.levels[c - 1].append(x)

    def pop(self):
        x = self.levels[-1].pop()
        if not self.levels[-1]:
            self.levels.pop()
        self.count[x] -= 1
        return x


class CircularQueue:
    def __init__(self, k):
        self.buf, self.head, self.size = [None] * k, 0, 0

    def enqueue(self, v):
        if self.size == len(self.buf):
            return False
        self.buf[(self.head + self.size) % len(self.buf)] = v
        self.size += 1
        return True

    def dequeue(self):
        if self.size == 0:
            return False
        self.head = (self.head + 1) % len(self.buf)
        self.size -= 1
        return True

copy_random_list needs its own RandomNode: the cache's Node has no random field, and LeetCode supplies its own class with val, next and random. The nodes are used as dictionary keys, which works because they keep the default identity hash. If you define __eq__ on a node class, the map would merge distinct nodes that happen to compare equal.

Variations and edge cases

• OrderedDict shortcut. collections.OrderedDict is a hash map plus a doubly linked list already: move_to_end(key) refreshes, and popitem(last=False) evicts the oldest. It is a legitimate answer in practice, but interviewers often want the hand-built version, so know both.
• LFU cache. Keep key_to_freq, a map from frequency to an ordered set of keys (oldest first), and min_freq. A hit removes the key from its frequency's set and adds it to the next one; if that emptied the minimum's set, increase the minimum. Eviction removes the oldest key of the minimum's set.
• Circular queue. A head index and a size suffice. Tracking only head and tail cannot tell empty from full, since both look like head equal to tail. Keeping the size removes the ambiguity.
• Time-based or capacity-by-weight caches. The same skeleton works; only the eviction condition changes, from "count exceeds capacity" to "total weight exceeds budget", sometimes evicting several nodes in a loop.
• Edge cases: capacity 1, putting an existing key when the cache is full (update, never evict), getting a missing key (must not change the order), and a stored value of 0 (the code above tests the node, which is always truthy, never the value).

Complexity and tradeoffs

• Time: O(1) per operation for the LRU cache, the frequency stack and the circular queue: one hash lookup plus a bounded number of pointer updates. Copying a list is O(n), two passes.
• Space: O(capacity) for the cache. Copying with a map uses O(n) extra beyond the copy itself; the interleaving trick brings that to O(1).
• Baseline. A plain list ordered by recency makes get O(n), since you must search and then move. A map with timestamps makes get O(1) but eviction O(n), since the oldest timestamp must be found by scanning. The combination is the only one of the three that makes both operations constant.
• When it fails. If the order you need is by value (the smallest, the median), a linked list does not help and a heap or balanced tree does. Under concurrency the two structures must change together under one lock, or the map and list disagree. Pointer-heavy structures also have poor cache locality in real programs; an array-based design can beat them even at the same asymptotics.

Problems

The home problems are all "design" questions: the LRU and LFU caches, the maximum frequency stack, the circular queue, and copying a list with random pointers. Design Twitter and Design Hit Counter are listed as "also uses" because the main idea belongs to merging sorted lists and to a time window, but they too need a map from a user or time to a small sequence.

Medium

• 138. Copy List with Random Pointer NeetCode 150 NeetCode 250
  Map each original node to its copy in one pass, then wire the copies' next and random pointers through the map in a second.
• 146. LRU Cache Grind 169 NeetCode 150 NeetCode 250
  A hash map finds a node in constant time and a doubly linked list keeps recency order, so both get and put stay O(1).
• 622. Design Circular Queue NeetCode 250
  Use a fixed array with a head index and a count, and wrap indices with modulo so the space is reused.

Hard

• 460. LFU Cache NeetCode 250
  Keep one recency-ordered list per frequency plus the current minimum frequency, so the least frequently used key can be evicted in O(1).
• 895. Maximum Frequency Stack Grind 169 NeetCode 250
  Keep one stack per frequency level plus each value's count, so pop takes from the highest level's stack.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 355. Design Twitter Medium
• 362. Design Hit Counter Medium

Connections

The pointer moves come from the linked list basics page, and the lookup half comes from the hash maps page, so a bug usually lives in one of those two habits: forgetting to save a pointer before overwriting it, or letting the map hold a stale node after it was evicted. The frequency stack is a cousin of the monotonic stack in spirit, in that the stack's structure encodes the answer, and the LFU cache shares the "bucket by count" idea with the counting and bucketing page.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, section 10.2 (doubly linked lists and sentinels) and chapter 11 (hash tables).
• Sedgewick and Wayne, Algorithms, sections 1.3 and 3.4: linked lists, and hash tables with symbol-table semantics.
• Skiena, The Algorithm Design Manual: dictionaries and the combination of structures to meet an operation budget.
• Shah, Mitra and Matani, "An O(1) algorithm for implementing the LFU cache eviction scheme" (2010): the frequency-list design sketched above.
• Knuth, The Art of Computer Programming, volume 1, sections 2.2.3 (linked allocation) and 2.2.5 (doubly linked lists).
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.