Lesson 40.1 · Designing Data Structures

The Design Method and LRU Cache

Write each operation with its target cost, choose a structure that gives each cost, then make every operation update all structures together. LRU = hash map + doubly linked list.

18 min

Think of it like this

A small desk with room for a few books: whenever you use a book you put it on top of the pile, and when the desk is full the book at the bottom (used longest ago) goes back to the shelf.

1.From requirements to structures

LRU cache: get(key) and put(key, value) in O(1), evicting the least recently used key when over capacity. Needs: find a key fast → HashMap<key, node>. Know the recency order and move any item to the front in O(1) → doubly linked list (a node can unlink itself). Evict from the back in O(1) → sentinel tail.

The invariant: the map and the list always contain the same keys. Every operation that touches one updates the other. Sentinel head and tail nodes remove all null checks.

In Java, LinkedHashMap with access order and removeEldestEntry is a ready-made LRU. Interviewers usually want you to build it, but mention it.

Main.java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Map<Integer, String> lru = new LinkedHashMap<>(16, 0.75f, true) {   // true = access order
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, String> eldest) {
                return size() > 2;
            }
        };
        lru.put(1, "a");
        lru.put(2, "b");
        lru.get(1);                  // 1 becomes most recent
        lru.put(3, "c");             // evicts 2
        System.out.println(lru.keySet());
    }
}

Output

[1, 3]

▶ Dry run: LRU with capacity 2put(1), put(2), get(1), put(3)

null

map(map)

1 → node

Step 1/4put(1): new node at the front (most recent).

Remember

Operation → cost → structure.
Map + doubly linked list for O(1) recency.
Keep structures in sync in every method.

Common mistakes

A singly linked list (removing a middle node needs its predecessor).
Updating the value on put without moving the node to the front.

Words used in this lesson

LRU: Least recently used: evict the item untouched for the longest time.
Sentinel node: A dummy head or tail that is never removed, so edge cases disappear.
Invariant: A fact that every operation keeps true (here: map and list hold the same keys).

Command Palette

The Design Method and LRU Cache

1.From requirements to structures