LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. (link)

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. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

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
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

Constraints:

• 1 <= capacity <= 3000

• 0 <= key <= 10<sup>4</sup>

• 0 <= value <= 10<sup>5</sup>

• At most 2 * 10<sup>5</sup> calls will be made to get and put.

Solution

Ideation

If we want to get the value of a particular key-value in O(1) time, then our go-to data structure is a Hash map. If the capacity is full and we still want to add a key, we need to delete a key that is least used, also in O(1) time. This can be done using a linked list, as deletion at any given node is O(1) for a doubly linked list if we have the node. So, the two data structures required to implement these features are a Hash map and a doubly linked list.

Process

A map maintains the mapping of keys and values. A doubly linked list maintains the least recently used order. In the map, we store the key as the given key, and the value will be the node reference in the doubly linked list. This node contains the key and value pair inside it.

Here, we take two dummy nodes, head and tail, in the doubly linked list, which are not included in the map or capacity calculations. These provide a lot of flexibility and robustness to our code. All null pointer checks and exceptions are fully reduced.

get: Whenever we get any value for a key, we move the node to the position after the head. This is done in two steps: first, we delete the node, and then we insert it after the head. In the deletion of the node, we just manipulate the links of the previous and next nodes. Later, we use the same node for inserting.

put: If we create a new node, we insert it after the head. When the capacity is full, we delete the node that is before the tail. If the key is already present, update the value and move the node to the position after the head. This is also done in two steps: delete the current node and insert it after the head.

If the capacity is full and we have to put a new key, we remove the last node (before the tail), create a new node, and insert it after the head.

class Node{
    public Node next;
    public Node prev;
    public int key;
    public int val;

    public Node(int key, int val){
        this.key = key;
        this.val = val;
    }

    public String toString(){
        String print="";
        Node temp = this;
        while(temp!=null){
            print+="->"+temp.val;
            temp = temp.next;
        }
        return print;
    }
}

class LRUCache {

    public Node head; 
    public Node tail;
    public Map<Integer, Node> map;
    public int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;

        this.map = new HashMap<>();
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        this.head.next = tail;
        this.tail.prev = head;
    }

    public int get(int key) {
        if(!map.containsKey(key)) return -1;
        Node node = map.get(key);
        deleteNode(node);
        insertAfterHead(node);
        return node.val;
    }

    public void put(int key, int value) {
        if(map.size()==capacity && !map.containsKey(key)){
            Node node = deleteLastNode();
            map.remove(node.key);
        }

        if(map.containsKey(key)){
            Node node = map.get(key);
            deleteNode(node);
            node.val = value;
            insertAfterHead(node);
        }
        else{
            Node node = new Node(key, value);
            map.put(key,node);
            insertAfterHead(node);
        }
    }

    private void deleteNode(Node node){
        Node left = node.prev;
        Node right = node.next;

        left.next = right;
        right.prev = left;
    }

    private void insertAfterHead(Node node){
        Node next = head.next;
        head.next = node;
        next.prev = node;

        node.next = next;
        node.prev = head;
    }

    private Node deleteLastNode(){
        Node node = tail.prev;

        Node left = node.prev;
        left.next = tail;
        tail.prev = left;

        return node;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */