LRU Cache [Medium] — Doubly Linked List + HashMap

Problem Statement

Design a data structure that follows the LRU eviction policy:

get(key): return value if exists, else -1
put(key, value): insert or update; evict LRU if capacity exceeded

Both operations must be O(1).

Intuition

HashMap provides O(1) access by key. Doubly Linked List (DLL) maintains order — recently used at head, LRU at tail.

On get: move node to head. On put: add to head; if over capacity, remove tail.

Solutions

Python (OrderedDict — easiest)

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache: return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.cap:
            self.cache.popitem(last=False)

Python (DLL — from scratch)

class Node:
    def __init__(self, k=0, v=0):
        self.k, self.v = k, v
        self.prev = self.next = None

class LRUCache:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.map = {}
        self.head = Node()  # dummy head (most recent)
        self.tail = Node()  # dummy tail (LRU)
        self.head.next = self.tail
        self.tail.prev = self.head

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

    def _insert_front(self, node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.map: return -1
        node = self.map[key]
        self._remove(node)
        self._insert_front(node)
        return node.v

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            self._remove(self.map[key])
        node = Node(key, value)
        self.map[key] = node
        self._insert_front(node)
        if len(self.map) > self.cap:
            lru = self.tail.prev
            self._remove(lru)
            del self.map[lru.k]

Java

class LRUCache extends LinkedHashMap<Integer,Integer> {
    private int cap;
    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.cap = capacity;
    }
    public int get(int key) { return super.getOrDefault(key,-1); }
    public void put(int key, int value) { super.put(key,value); }
    protected boolean removeEldestEntry(Map.Entry e){ return size()>cap; }
}

C++

class LRUCache {
    int cap;
    list<pair<int,int>> dll;  // {key,val}
    unordered_map<int,list<pair<int,int>>::iterator> mp;
public:
    LRUCache(int c):cap(c){}
    int get(int key){
        if(!mp.count(key)) return -1;
        dll.splice(dll.begin(),dll,mp[key]);
        return mp[key]->second;
    }
    void put(int key,int val){
        if(mp.count(key)) dll.erase(mp[key]);
        dll.push_front({key,val});
        mp[key]=dll.begin();
        if(mp.size()>cap){mp.erase(dll.back().first);dll.pop_back();}
    }
};

Complexity

get/put: O(1)
Space: O(capacity)