LRU Cache

medium linked list hash map design

Problem

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class: LRUCache(int capacity) Initialize the LRU cache with positive size capacity. int get(int key) Return the value of the key if the key exists, otherwise return -1. void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache.

Combine a hash map (key → node) with a doubly-linked list. The list orders entries by recency: head is most-recent, tail is least-recent. On get, look up the node and move it to the head. On put, update the existing node or insert a new one at the head; if size exceeds capacity, drop the tail and remove its key from the map.

Inputcapacity 2 · put(1,1) · put(2,2) · get(1) · put(3,3) · get(2) · get(3)

Output1, −1, 3

capacity

ops (semi-colon separated, e.g. put 1 1; put 2 2; get 1; put 3 3; get 2; get 3)

class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.map = {}
        self.head = Node(); self.tail = Node()
        self.head.next = self.tail; self.tail.prev = self.head
    def _add_front(self, n):
        n.prev = self.head; n.next = self.head.next
        self.head.next.prev = n; self.head.next = n
    def _remove(self, n):
        n.prev.next = n.next; n.next.prev = n.prev
    def get(self, key):
        if key not in self.map: return -1
        n = self.map[key]
        self._remove(n); self._add_front(n)
        return n.val
    def put(self, key, val):
        if key in self.map:
            n = self.map[key]; n.val = val
            self._remove(n); self._add_front(n)
            return
        if len(self.map) == self.cap:
            lru = self.tail.prev
            self._remove(lru); del self.map[lru.key]
        n = Node(key, val); self.map[key] = n
        self._add_front(n)

class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.map = new Map();
    this.head = {}; this.tail = {};
    this.head.next = this.tail; this.tail.prev = this.head;
  }
  addFront(n) {
    n.prev = this.head; n.next = this.head.next;
    this.head.next.prev = n; this.head.next = n;
  }
  remove(n) { n.prev.next = n.next; n.next.prev = n.prev; }
  get(key) {
    if (!this.map.has(key)) return -1;
    const n = this.map.get(key);
    this.remove(n); this.addFront(n);
    return n.val;
  }
  put(key, val) {
    if (this.map.has(key)) {
      const n = this.map.get(key); n.val = val;
      this.remove(n); this.addFront(n); return;
    }
    if (this.map.size === this.cap) {
      const lru = this.tail.prev;
      this.remove(lru); this.map.delete(lru.key);
    }
    const n = { key, val };
    this.map.set(key, n);
    this.addFront(n);
  }
}

class LRUCache {
    static class Node { int key, val; Node prev, next; Node(int k,int v){key=k;val=v;} }
    int cap;
    Map<Integer,Node> map = new HashMap<>();
    Node head = new Node(0,0), tail = new Node(0,0);
    public LRUCache(int capacity) {
        cap = capacity; head.next = tail; tail.prev = head;
    }
    void addFront(Node n) { n.prev = head; n.next = head.next; head.next.prev = n; head.next = n; }
    void remove(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }
    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node n = map.get(key); remove(n); addFront(n); return n.val;
    }
    public void put(int key, int val) {
        if (map.containsKey(key)) { Node n = map.get(key); n.val = val; remove(n); addFront(n); return; }
        if (map.size() == cap) { Node lru = tail.prev; remove(lru); map.remove(lru.key); }
        Node n = new Node(key, val); map.put(key, n); addFront(n);
    }
}

struct Node { int key, val; Node *prev, *next; };
class LRUCache {
    int cap;
    unordered_map<int, Node*> mp;
    Node *head, *tail;
    void addFront(Node* n) { n->prev = head; n->next = head->next; head->next->prev = n; head->next = n; }
    void remove(Node* n) { n->prev->next = n->next; n->next->prev = n->prev; }
public:
    LRUCache(int capacity) : cap(capacity) {
        head = new Node(); tail = new Node();
        head->next = tail; tail->prev = head;
    }
    int get(int key) {
        if (!mp.count(key)) return -1;
        auto n = mp[key]; remove(n); addFront(n); return n->val;
    }
    void put(int key, int val) {
        if (mp.count(key)) { auto n = mp[key]; n->val = val; remove(n); addFront(n); return; }
        if ((int)mp.size() == cap) { auto lru = tail->prev; remove(lru); mp.erase(lru->key); delete lru; }
        auto n = new Node{key, val, nullptr, nullptr}; mp[key] = n; addFront(n);
    }
};

Explanation

An LRU cache keeps the most recently used items and throws away the least recently used one when it runs out of room. The hard part is making both get and put run in constant time.

The winning combo is two data structures working together: a hash map from key to node for instant lookup, plus a doubly linked list that orders nodes by recency. The list's head end is the most-recently-used and the tail end is the least-recently-used. Two dummy head and tail sentinels remove all the awkward edge cases.

On get, we find the node via the map, then _remove it from its current spot and _add_front it right behind the head — touching a key makes it most recent. A doubly linked list is essential here because it lets us unlink a node in O(1) by rewiring its prev and next neighbors.

On put, if the key exists we update its value and move it to the front. If it is new and the cache is full, we grab tail.prev (the least recent), remove it, and delete its key from the map before inserting the new node at the front.

Example (capacity 2): put(1,1), put(2,2), then get(1) returns 1 and bumps key 1 to the front, making key 2 the LRU. put(3,3) evicts key 2, so get(2) returns -1 while get(3) returns 3.

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