LRU Cache

Thought Process

To implement an LRU Cache, we use a combination of a doubly linked list and a hash map. The doubly linked list helps maintain the order of recently used items, while the hash map provides O(1) access to any node. When a 'get' operation is performed, the accessed node is moved to the front of the list to mark it as recently used. For a 'put' operation, if the cache is full, the least recently used node (at the tail) is removed. Finally, the new node is added to the front of the list as the most recent node. This ensures that the cache always maintains the most recently used items within the specified capacity.

class Node{

    int key;
    int val;
    Node next;
    Node prev;

    Node(int key, int val){
        this.key = key;
        this.val = val;
        this.next = null;
        this.prev = null;
    }
}

class LRUCache {

    Map<Integer,Node> mp;
    int cap;
    Node head = new Node(-1,-1);
    Node tail = new Node(-1,-1);

    public LRUCache(int capacity) {
        this.cap = capacity;
        mp = new HashMap<>();
        head.next = tail;
        tail.prev = head;
    }
    // If element is present, then 
    // 1. Take the corresponding nod & remove it from the Linked List
    // 2. Add the node at the front of the Linked List.
    // 3. At last, return the value.
    public int get(int key) {

        if(mp.containsKey(key)){

            Node nod = mp.get(key);
            int val = nod.val;
            removeNode(nod);
            addNode(nod);
            return val;
        }
        return -1;
        
    }
    // 1. Check if element is already present 
    // 2. Or if size == capacity
    // 3. Add the element into the map
    public void put(int key, int value) {
        
        // Key is already present
        if(mp.containsKey(key)){

            Node nod = mp.get(key);
            removeNode(nod);
            mp.remove(key);
        }

        // Capacity is full
        if(mp.size()==cap){
            Node toRemove = tail.prev;
            removeNode(toRemove);
            mp.remove(toRemove.key);
        }

        Node nod = new Node(key,value);
        addNode(nod);
        mp.put(key,nod);
    }
    // Remove Node from the end of LL
    void removeNode(Node nod){

        Node nextt = nod.next;
        Node prevv = nod.prev;

        prevv.next = nextt;
        nextt.prev = prevv;
    }

    // Add Node at the Front of LL
    void addNode(Node nod){

        Node secondNode = head.next;
        head.next = nod;
        nod.prev = head;

        nod.next = secondNode;
        secondNode.prev = nod;
    }
}

/**
 * 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);
 */

Code Complexity

Time Complexity: O(1)

Both get and put operations are performed in constant time due to the use of a hash map and a doubly linked list.

Space Complexity: O(capacity)

The space used is proportional to the capacity of the cache, as it stores nodes in both the hash map and the doubly linked list.

Java: LRU Cache

Thought Process

Code Complexity

Time Complexity: O(1)

Space Complexity: O(capacity)