The Data Structure

What you should do next

With requirements agreed, draw the data structure before writing locks. The interviewer wants to see that you know why LRU is O(1), not just that LeetCode told you so.

Two structures, one cache

You need two things at once:

1. O(1) lookup by key — HashMap<Integer, Node>
2. O(1) reorder by recency — doubly linked list of nodes

Map values are direct pointers to list nodes. No scanning. No sorting.

map:  { 1 → ●, 3 → ●, 7 → ● }
               ↓       ↓      ↓
list: head → [1] ⇄ [3] ⇄ [7] ← tail
      (LRU)                    (MRU)

• Head = least recently used — eviction candidate
• Tail = most recently used — where hits and fresh inserts land

Node class

Each list node carries the key (needed for eviction from the map), the value, and prev/next pointers:

class Node {
    int key;
    int value;
    Node prev;
    Node next;

    Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

Store the key inside the node so when you evict from the head you know which map entry to remove.

LRUCache skeleton

class LRUCache {
    private final HashMap<Integer, Node> map;
    private final int capacity;
    private Node head;  // LRU end
    private Node tail;  // MRU end

    public LRUCache(int capacity) {
        this.map = new HashMap<>();
        this.capacity = capacity;
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        moveToTail(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            moveToTail(node);
            return;
        }
        if (map.size() == capacity) {
            map.remove(head.key);
            removeNode(head);
        }
        Node node = new Node(key, value);
        map.put(key, node);
        appendToTail(node);
    }
}

The helper methods do the pointer work:

private void removeNode(Node node) {
    if (node.prev != null) node.prev.next = node.next;
    else head = node.next;
    if (node.next != null) node.next.prev = node.prev;
    else tail = node.prev;
}

private void appendToTail(Node node) {
    node.prev = tail;
    node.next = null;
    if (tail != null) tail.next = node;
    else head = node;
    tail = node;
}

private void moveToTail(Node node) {
    removeNode(node);
    appendToTail(node);
}

Why every operation is O(1)

The doubly linked list is what makes reordering cheap. A singly linked list would force O(n) scans to find the node before the one you need to unlink.

Walk through one eviction

Capacity = 3. Operations: put(1,10), put(2,20), put(3,30), get(1), put(4,40).

After the first three puts, order is 1 ⇄ 2 ⇄ 3 (1 is LRU).

get(1) moves 1 to the tail: 2 ⇄ 3 ⇄ 1.

put(4,40) is a new key and the cache is full. Evict head (key 2). Map drops 2, list becomes 3 ⇄ 4 ⇄ 1.

That is the behavior the interviewer will trace on the board. Get this right before layering concurrency on top.