About Us Contact Us Write for Us Advertise
Home > System Design > Low-Level Design > Design an LRU Cache (O(1) get & put) — Low-Level Design
System Design › Low-Level Design

Design an LRU Cache (O(1) get & put) — Low-Level Design

Design an LRU cache with O(1) get and put — the classic data-structure question. Combining a HashMap with a doubly-linked list, sentinel nodes, Java code, and the thread-safety / LinkedHashMap notes.

Shiv Pandey
Shiv Pandey
Oct 27, 2026 | 96 views
Design an LRU Cache (O(1) get & put) — Low-Level Design

🟠 Low-Level Design · Case Study · the classic data-structure problem

"Design an LRU cache" is a rite-of-passage coding/LLD question. An LRU (Least Recently Used) cache holds a fixed number of items and, when full, evicts the one used longest ago. The challenge is doing both get and put in O(1) time — which requires combining two data structures in a clever way. Let's build it.

The approach in one line: combine a HashMap (key → node, for O(1) lookup) with a doubly-linked list (ordered by recency, for O(1) move & evict) — most-recent at the front, least-recent at the back.

Step 1 — Requirements

  • get(key) → value if present (and mark it most-recently-used), else miss.
  • put(key, value) → insert/update; if over capacity, evict the least-recently-used item.
  • Both operations must be O(1). That constraint is the whole puzzle.

Step 2 — Why one data structure isn't enough

🟠 A HashMap gives O(1) lookup but no notion of order (which was used least recently?). A list/array gives order but O(n) to find or move an item. Neither alone hits O(1) for both. The trick is to combine them: a HashMap for instant lookup plus a doubly-linked list for instant reordering and eviction.

Step 3 — The design: HashMap + doubly-linked list

HashMap: key → node "a" → ● "b" → ● Doubly-linked list (recency) a (MRU) b c (LRU) ↑ evict from tail ↑ insert / move to head
  • The map points key → the list node, so you find any item in O(1).
  • The list keeps items in recency order: head = most recently used, tail = least. Because it's doubly-linked, you can unlink any node and re-insert at the head in O(1).
class LRUCache {
    private final int cap;
    private final Map<Integer,Node> map = new HashMap<>();
    private final Node head, tail;        // dummy head/tail sentinels

    int get(int key){
        if(!map.containsKey(key)) return -1;
        Node n = map.get(key);
        moveToHead(n);                    // mark most-recently-used
        return n.value;
    }
    void put(int key, int val){
        if(map.containsKey(key)){ Node n=map.get(key); n.value=val; moveToHead(n); return; }
        if(map.size()==cap){ Node lru=tail.prev; remove(lru); map.remove(lru.key); } // evict
        Node n=new Node(key,val); addToHead(n); map.put(key,n);
    }
    // remove(), addToHead(), moveToHead() are all O(1) pointer updates
}

Every operation is O(1): the map finds the node instantly, and the doubly-linked list lets you unlink/insert/evict with a few pointer swaps. Using dummy head and tail sentinels avoids null-checks and edge cases — a clean implementation detail worth mentioning.

Step 4 — The senior notes

🔴 Things to raise: (1) thread-safety — the above isn't thread-safe; a real cache needs locking or a concurrent structure. (2) In Java, LinkedHashMap with accessOrder=true gives you an LRU almost for free (override removeEldestEntry) — good to know, but interviewers usually want the from-scratch map+DLL. (3) Other eviction policies exist (LFU, FIFO) — LRU is one choice; naming the family shows breadth. (4) This is the same idea behind the eviction in a distributed cache, just at a single-node level.

The interview-ready walkthrough

"An LRU cache needs O(1) get and put, which no single structure gives — so I combine a HashMap (key → node, O(1) lookup) with a doubly-linked list ordered by recency (head = most recent, tail = least). get looks up the node and moves it to the head; put inserts at the head and, if over capacity, evicts the tail and removes it from the map. Doubly-linked so unlinking is O(1); I'd use sentinel head/tail nodes to simplify. For production I'd add locking, and note Java's LinkedHashMap can do LRU out of the box." That's the canonical answer with the right nuances."

What to read next

← Design Splitwise · Design Tic-Tac-Toe →

Related Articles

Design a Food Delivery App (Low-Level Design)
System Design › Low-Level Design

Design a Food Delivery App (Low-Level Design)

Design a Meeting Scheduler (Low-Level Design)
System Design › Low-Level Design

Design a Meeting Scheduler (Low-Level Design)

Design Snake and Ladder (Low-Level Design)
System Design › Low-Level Design

Design Snake and Ladder (Low-Level Design)

Design Chess (Low-Level Design)
System Design › Low-Level Design

Design Chess (Low-Level Design)