Least-Recently-Used Cache
Problem
Design a fixed-capacity cache supporting get(key) and put(key, value) in O(1). When at capacity, evict the least-recently-used entry on insert.
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.
Input
capacity 2 · put(1,1) · put(2,2) · get(1) · put(3,3) · get(2) · get(3)Output
1, −1, 3class 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);
}
};