Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class with capacity k:
get(key) — return the value if the key exists, otherwise return -1put(key, value) — update or insert. If the number of keys exceeds capacity, evict the least recently used key.Example 1
Input: capacity=2; put(1,1); put(2,2); get(1); put(3,3); get(2); put(4,4); get(1); get(3); get(4)
Output: 1, -1, -1, 3, 4
Explanation: After put(3,3) key 2 is evicted (LRU). After put(4,4) key 1 is evicted.
1 <= capacity <= 30000 <= key <= 10^4At most 2*10^5 calls to get and put.HashMap for O(1) lookup + Doubly Linked List for O(1) insert/delete.
class LRUCache {
private final int capacity;
private final Map<Integer, Node> map = new HashMap<>();
private final Node head = new Node(0, 0); // dummy
private final Node tail = new Node(0, 0); // dummy
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (!map.containsKey(key)) return -1;
Node node = map.get(key);
moveToFront(node); // mark as recently used
return node.val;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
Node node = map.get(key);
node.val = value;
moveToFront(node);
} else {
if (map.size() == capacity) {
Node lru = tail.prev; // least recently used
remove(lru);
map.remove(lru.key);
}
Node node = new Node(key, value);
map.put(key, node);
addToFront(node);
}
}
private void remove(Node n) {
n.prev.next = n.next;
n.next.prev = n.prev;
}
private void addToFront(Node n) {
n.next = head.next;
n.prev = head;
head.next.prev = n;
head.next = n;
}
private void moveToFront(Node n) { remove(n); addToFront(n); }
private static class Node {
int key, val;
Node prev, next;
Node(int k, int v) { key = k; val = v; }
}
}Time: O(1) get and put · Space: O(capacity)