LeetCode 146 · Linked List

LRU Cache, explained with a picture

A small hotel that evicts the guest who’s been idle longest.

MediumLinked List
▶ Watch it step by step

The problem

Design an LRU (Least Recently Used) cache with a fixed capacity: get(key) returns the value or −1; put(key, value) adds or updates, and if the cache is full it first throws out the key that was used least recently. Both must be O(1).

Input:  capacity 2; put 1 1, put 2 2, get 1, put 3 3, get 2, put 4 4, get 1, get 3, get 4
Output: get 1 → 1, get 2 → −1, get 1 → −1, get 3 → 3, get 4 → 4

Picture it

Picture a tiny hotel with a fixed number of rooms and a queue of guests ordered by when they last did something. Whenever a guest is used (get or put), they move to the “most recent” end. When a new guest arrives and the hotel is full, the guest at the “least recent” end is checked out. A dictionary finds any guest’s room instantly; a doubly linked list keeps the order and lets us move a guest in one step.

How to recognise it

  • You are asked to design a data structure, with several operations that must each run in O(1).
  • You need two things at once: find any key instantly (a dictionary) and keep keys in order of last use so the oldest can be removed (a list ordered by time).
  • An ordinary list can keep the order, but moving a key from the middle to the end costs O(n). A doubly linked list (each node links to both neighbours) can unhook any node in O(1) if you already hold a reference to it, and the dictionary gives you that reference.
  • "Least recently used", "evict the oldest", "move to front when touched" all point to hash map + doubly linked list. In Python, collections.OrderedDict is exactly that pair.

Start with brute force

Keep the values in a dictionary and the keys in a Python list ordered from oldest to newest. On every use, remove the key from the list and append it again.

class LRUCacheBrute:
    def __init__(self, capacity):
        self.cap, self.data, self.order = capacity, {}, []   # order: oldest first
    def get(self, key):
        if key not in self.data:
            return -1
        self.order.remove(key)
        self.order.append(key)
        return self.data[key]
    def put(self, key, value):
        if key in self.data:
            self.order.remove(key)
        elif len(self.data) == self.cap:
            del self.data[self.order.pop(0)]
        self.data[key] = value
        self.order.append(key)

order.remove(key) searches the list and shifts everything after it, and pop(0) shifts the whole list, so each operation is O(c) for capacity c. LeetCode allows c = 3,000 and 2 × 10^5 calls: up to about 6 × 10^8 steps, and it breaks the O(1) requirement.

From brute force to the idea

  1. Find the waste. The dictionary already finds a key in O(1). The slow part is finding the same key again inside the order list.
  2. Link the order. Store the order as a doubly linked list and let the dictionary point at each key's node. Unhooking a node and re-attaching it at the "newest" end is a few pointer changes.
  3. Use the ready-made version. OrderedDict keeps its keys in insertion order using exactly this design. move_to_end(key) makes a key the newest in O(1), and popitem(last=False) removes the oldest in O(1).
  4. get: if the key is missing return −1; otherwise move it to the end (it was just used) and return its value.
  5. put: store the value and move the key to the end. If that pushed the size past the capacity, evict the oldest. Updating an existing key never grows the cache, so it never evicts.

This is the key idea: a dictionary for finding, a doubly linked list for ordering, kept in step on every operation.

The key idea

Hash map for O(1) lookup + doubly linked list for O(1) reordering and eviction.

Python solution

class LRUCache:
    def __init__(self, capacity):
        self.cap, self.data = capacity, OrderedDict()   # oldest first
    def get(self, key):
        if key not in self.data:
            return -1
        self.data.move_to_end(key)           # just used: now newest
        return self.data[key]
    def put(self, key, value):
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.cap:
            self.data.popitem(last=False)    # evict the oldest

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import OrderedDict

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO(c) per call: list.remove and pop(0) scan and shift the order listO(c): the dictionary and the list
OrderedDict (shown code)O(1) per call: dictionary lookup, move_to_end and popitem(last=False) are all constant timeO(c): one entry per cached key

Edge cases

  • Capacity 1: every put of a new key evicts the previous one.
  • Updating an existing key (put(1, 10) when 1 is cached): changes the value, makes 1 the newest, and evicts nothing.
  • get of a missing key: returns −1 and changes nothing.
  • Stored value 0: get returns 0, because the code checks key not in self.data, not the truthiness of the value.
  • get counts as a use: in the LeetCode example (capacity 2: put 1, put 2, get 1, put 3), key 2 is evicted, not key 1.
  • Imports: the shown code needs from collections import OrderedDict.

Common mistakes

  • Forgetting move_to_end in get, so reads do not refresh a key and the wrong one is evicted.
  • Evicting before inserting, even when the key already exists. That throws out a key needlessly when you are only updating.
  • Using popitem() without last=False, which removes the newest key instead of the oldest.
  • Building the order with timestamps and scanning for the smallest on eviction: O(c) again.
Your turn: without OrderedDict

Interviewers often ask you to build the same cache without OrderedDict. Write it with a plain dictionary and your own doubly linked list. Describe your approach, then write it if you like.

Compare with our answer

Use two sentinel nodes (dummy nodes that are never removed), old and new, so every real node always has neighbours on both sides and no None checks are needed. The dictionary maps key → node. Each node stores its key too, so the evicted node can be deleted from the dictionary.

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

class LRUCacheDLL:
    def __init__(self, capacity):
        self.cap, self.map = capacity, {}
        self.old, self.new = DNode(), DNode()      # sentinels at both ends
        self.old.next, self.new.prev = self.new, self.old
    def _remove(self, node):
        node.prev.next, node.next.prev = node.next, node.prev
    def _add_newest(self, node):
        node.prev, node.next = self.new.prev, self.new
        self.new.prev.next = node
        self.new.prev = node
    def get(self, key):
        if key not in self.map:
            return -1
        node = self.map[key]
        self._remove(node)
        self._add_newest(node)
        return node.val
    def put(self, key, value):
        if key in self.map:
            self._remove(self.map[key])
        node = DNode(key, value)
        self.map[key] = node
        self._add_newest(node)
        if len(self.map) > self.cap:
            lru = self.old.next
            self._remove(lru)
            del self.map[lru.key]

Every operation is O(1); space O(c).

A strong answer mentions: sentinel nodes, storing the key inside each node for eviction, and updating both the dictionary and the list on every put and get.

Check what stuck

1. A server caches up to 10,000 thumbnails. When full, it must drop the one not viewed for the longest time, with O(1) lookups and updates. Which design fits best?

2. Why is move_to_end O(1) in the shown code rather than O(c)?

3. A learner deletes self.data.move_to_end(key) from get. With capacity 2, the calls are put 1, put 2, get 1, put 3, get 2. What changes?

Score 60% or more and the lesson is marked complete.