LRU Cache

Share

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.

Example 1
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).
Example 2
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]

Solution Approach

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
Java
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)