Design a data structure that follows the Least Recently Used (LRU) cache eviction policy. Implement get(key) and put(key, value) in O(1) time.
Input: ["LRUCache","put","put","get","put","get","put","get","get","get"], [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
Output: [null,null,null,1,null,-1,null,-1,3,4]
Explanation: Cache capacity=2. get(2) returns -1 (evicted).
Input: capacity=1; put(2,1); get(2)→1; put(3,2); get(2)→-1; get(3)→2
Output: [-1,1,null,null,1,null,null,-1,2]
Use a HashMap<key, Node> for O(1) lookup and a doubly linked list to maintain access order. Most recently used is at head, least recently used at tail.
- On get: move node to head, return value
- On put: if key exists update and move to head; if new add to head; if over capacity remove tail
class LRUCache {
class Node {
int key, val;
Node prev, next;
Node(int k, int v) { key = k; val = v; }
}
Map<Integer, Node> map = new HashMap<>();
Node head = new Node(0,0), tail = new Node(0,0);
int cap;
public LRUCache(int capacity) {
cap = capacity;
head.next = tail; tail.prev = head;
}
public int get(int key) {
if (!map.containsKey(key)) return -1;
Node n = map.get(key);
remove(n); addToHead(n);
return n.val;
}
public void put(int key, int value) {
if (map.containsKey(key)) { map.get(key).val = value; get(key); return; }
Node n = new Node(key, value);
map.put(key, n); addToHead(n);
if (map.size() > cap) { Node t = tail.prev; remove(t); map.remove(t.key); }
}
void remove(Node n) { n.prev.next = n.next; n.next.prev = n.prev; }
void addToHead(Node n) { n.next = head.next; n.prev = head; head.next.prev = n; head.next = n; }
}
Complexity Analysis:
Time complexity: O(1) for get and put
Space complexity: O(capacity)