LRU Cache

Pre Requisites: Knowledge of Hashmaps and Doubly Linked List data structure

Intuition:

As the name suggests, the data items (key-value pairs) that are least recently used will be staying in the cache memory. To mark the data items as recently used, a doubly linked list can be used. The most recently used data item will be placed in the front and the least recently used data item will be placed at the end of the doubly linked list.

Why using a Doubly Linked List?

Because doubly linked list data structure makes the insertion and deletion operation on data items in constant time while making sure the order of data items remains.

But in order to implement the get method for LRU cache, the searching operation will take linear time where each data-item needs to be checked. To improve the complexity of get method, a hashmap can be used to store the key and the address of node containing the key (if it exists).

This way, the two methods can be implemented in constant time:

Get method: Using hashmap, it can be found whether a key exists in the doubly linked list. If it exists, the corresponding value can be returned using the address of node, otherwise, -1 can be returned.
Put method: If the key exists in the doubly linked list, its value can be updated. Otherwise, the least recently used data-item can be removed and the current key-value pair can be inserted.

Approach:

The cache is initialized with a given capacity. Two dummy nodes, head and tail, are created to mark the start and end of cache. The head's next points to the tail, and the tail's previous points to the head.
Get operation:
- Check if the key exists in the hash map.
- If the key is present, retrieve the corresponding node, move it to the front (mark it as recently used), and return its value.
- If the key is not present, return -1.
Put operation:
- Check if the key already exists in the hash map.
- If the key is present, update the node's value, move it to the front (mark it as recently used). If the key is not present, check if the cache has reached its capacity.
- If at capacity, remove the least recently used node (node right before the tail) from both the hash map and the doubly linked list.
- Insert the new key-value pair as a new node at the front (mark it as recently used) and add it to the hash map.
There are two helper functions:
- DeleteNode: This function removes a given node from the doubly linked list by adjusting the pointers of its previous and next nodes.
- InsertAfterHead: This function inserts a given node right after the head, marking it as the most recently used.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

/* Class to implement Nodes
of a doubly linked list */
class Node {
public:
	int key, val;
	Node* next;
	Node* prev;
    
    // Constructors
	Node() {
		key = val = -1;
		next = prev = NULL;
	}

	Node(int k, int value) {
		key = k;
		val = value;
		next = prev = NULL;
	}
};

// Class implementing LRU cache
class LRUCache {
private:

	map <int, Node*> mpp; // Map data structure
	int cap; // Capacity
	Node* head; // Dummy head pointer
	Node* tail; // Dummy tail pointer

	/* Private method to delete node
	from doubly linked list */
	void deleteNode(Node* node) {

		// Get the previous and next pointers
		Node* prevNode = node-> prev;
		Node* nextNode = node-> next;

		// Remove pointers to node
		prevNode-> next = nextNode;
		nextNode-> prev = prevNode;
	}

	// Private method to insert node after head
	void insertAfterHead(Node* node) {

		Node* nextNode = head-> next;
		head-> next = node;
		nextNode-> prev = node;
		node-> prev = head;
		node-> next = nextNode;
	}

public:
	// Method to initialise cache with given capacity
	LRUCache(int capacity) {
		cap = capacity; // Set the capacity
		mpp.clear(); // Clear the cache

		head = new Node();
		tail = new Node();

		// Make the connections
		head-> next = tail;
		tail-> prev = head;
	}

	// Method to get the key from cache
	int get(int key_) {
		// Return -1 if it is not present in cache
		if(mpp.find(key_) == mpp.end())
			return -1;

		Node* node = mpp[key_]; // Get the node
		int val = node->val; // Get the value

		// Delete the node
		deleteNode(node);
		/* Insert this node to front
		as it was recently used */
		insertAfterHead(node);

		// Return the stored value
		return val;
	}

	/* Method to update value is key exists,
	otherwise insert the key-value pair */
	void put(int key_, int value) {

		// Update the value if key is already present
		if(mpp.find(key_) != mpp.end()) {
		    
			Node* node = mpp[key_]; // Get the node
			node->val = value; // Update the value
            
			// Delete the node
			deleteNode(node);
			
			/* Insert this node to front
			as it was recently used */
			insertAfterHead(node);
			
			return;
		}

		// Check if the capacity limit has reached
		if(mpp.size() == cap) {

			// Get the least recently used node
			Node* node = tail->prev;

			// Delete node from map
			mpp.erase(node-> key);

			// Delete node from doubly linked list
			deleteNode(node);
		}

		// Create a new node
		Node* newNode = new Node(key_, value);
		
		// Insert it in map
		mpp[key_] = newNode;

		// Insert in doubly linked list
		insertAfterHead(newNode);
	}
};


int main() {
	// LRU Cache
	LRUCache cache(2);

	// Queries
	cache.put(1, 1);
	cache.put(2, 2);
	cout << cache.get(1) << " ";
	cache.put(3, 3);
	cout << cache.get(2) << " ";
	cache.put(4, 4);
	cout << cache.get(1) << " ";
	cout << cache.get(3) << " ";
	cout << cache.get(4) << " ";

	return 0;
}
import java.util.*;

class Node {
    public int key, val;
    public Node next, prev;
    
    // Constructors
    Node() {
        key = val = -1;
        next = prev = null;
    }

    Node(int k, int value) {
        key = k;
        val = value;
        next = prev = null;
    }
}

// Class implementing LRU cache
class LRUCache {
    private Map<Integer, Node> mpp; // Map data structure
    private int cap; // Capacity
    private Node head; // Dummy head pointer
    private Node tail; // Dummy tail pointer

    /* Private method to delete node
    from doubly linked list */
    private void deleteNode(Node node) {

        // Get the previous and next pointers
        Node prevNode = node.prev;
        Node nextNode = node.next;

        // Remove pointers to node
        prevNode.next = nextNode;
        nextNode.prev = prevNode;
    }

    // Private method to insert node after head
    private void insertAfterHead(Node node) {

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

    // Method to initialise cache with given capacity
    public LRUCache(int capacity) {
        cap = capacity; // Set the capacity
        mpp = new HashMap<>(); // Clear the cache

        head = new Node();
        tail = new Node();

        // Make the connections
        head.next = tail;
        tail.prev = head;
    }

    // Method to get the key from cache
    public int get(int key_) {
        // Return -1 if it is not present in cache
        if (!mpp.containsKey(key_))
            return -1;

        Node node = mpp.get(key_); // Get the node
        int val = node.val; // Get the value

        // Delete the node
        deleteNode(node);
        /* Insert this node to front
        as it was recently used */
        insertAfterHead(node);

        // Return the stored value
        return val;
    }

    /* Method to update value if key exists,
    otherwise insert the key-value pair */
    public void put(int key_, int value) {

        // Update the value if key is already present
        if (mpp.containsKey(key_)) {
            
            Node node = mpp.get(key_); // Get the node
            node.val = value; // Update the value
            
            // Delete the node
            deleteNode(node);
            
            /* Insert this node to front
            as it was recently used */
            insertAfterHead(node);
            
            return;
        }

        // Check if the capacity limit has reached
        if (mpp.size() == cap) {

            // Get the least recently used node
            Node node = tail.prev;

            // Delete node from map
            mpp.remove(node.key);

            // Delete node from doubly linked list
            deleteNode(node);
        }

        // Create a new node
        Node newNode = new Node(key_, value);
        
        // Insert it in map
        mpp.put(key_, newNode);

        // Insert in doubly linked list
        insertAfterHead(newNode);
    }

    public static void main(String[] args) {
        // LRU Cache
        LRUCache cache = new LRUCache(2);

        // Queries
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.print(cache.get(1) + " ");
        cache.put(3, 3);
        System.out.print(cache.get(2) + " ");
        cache.put(4, 4);
        System.out.print(cache.get(1) + " ");
        System.out.print(cache.get(3) + " ");
        System.out.print(cache.get(4) + " ");
    }
}
# Class to implement Nodes of a doubly linked list
class Node:
    def __init__(self, key=-1, val=-1):
        self.key = key
        self.val = val
        self.next = None
        self.prev = None

# Class implementing LRU cache
class LRUCache:

    def __init__(self, capacity):
        self.mpp = {} # Map data structure
        self.cap = capacity # Capacity
        self.head = Node() # Dummy head pointer
        self.tail = Node() # Dummy tail pointer

        # Make the connections
        self.head.next = self.tail
        self.tail.prev = self.head

    # Private method to delete node from doubly linked list
    def deleteNode(self, node):
        # Get the previous and next pointers
        prevNode = node.prev
        nextNode = node.next

        # Remove pointers to node
        prevNode.next = nextNode
        nextNode.prev = prevNode

    # Private method to insert node after head
    def insertAfterHead(self, node):
        nextNode = self.head.next
        self.head.next = node
        nextNode.prev = node
        node.prev = self.head
        node.next = nextNode

    # Method to get the key from cache
    def get(self, key_):
        # Return -1 if it is not present in cache
        if key_ not in self.mpp:
            return -1

        node = self.mpp[key_] # Get the node
        val = node.val # Get the value

        # Delete the node
        self.deleteNode(node)
        # Insert this node to front as it was recently used
        self.insertAfterHead(node)

        # Return the stored value
        return val

    # Method to update value if key exists, otherwise insert the key-value pair
    def put(self, key_, value):
        # Update the value if key is already present
        if key_ in self.mpp:
            node = self.mpp[key_] # Get the node
            node.val = value # Update the value

            # Delete the node
            self.deleteNode(node)
            # Insert this node to front as it was recently used
            self.insertAfterHead(node)

            return

        # Check if the capacity limit has reached
        if len(self.mpp) == self.cap:
            # Get the least recently used node
            node = self.tail.prev

            # Delete node from map
            del self.mpp[node.key]

            # Delete node from doubly linked list
            self.deleteNode(node)

        # Create a new node
        newNode = Node(key_, value)

        # Insert it in map
        self.mpp[key_] = newNode

        # Insert in doubly linked list
        self.insertAfterHead(newNode)


# LRU Cache
cache = LRUCache(2)

# Queries
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1), end=" ")
cache.put(3, 3)
print(cache.get(2), end=" ")
cache.put(4, 4)
print(cache.get(1), end=" ")
print(cache.get(3), end=" ")
print(cache.get(4), end=" ")
// Class to implement Nodes of a doubly linked list
class Node {
    constructor(key = -1, val = -1) {
        this.key = key;
        this.val = val;
        this.next = null;
        this.prev = null;
    }
}

// Class implementing LRU cache
class LRUCache {
    constructor(capacity) {
        this.mpp = new Map(); // Map data structure
        this.cap = capacity; // Capacity
        this.head = new Node(); // Dummy head pointer
        this.tail = new Node(); // Dummy tail pointer

        // Make the connections
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    // Private method to delete node from doubly linked list
    deleteNode(node) {
        // Get the previous and next pointers
        const prevNode = node.prev;
        const nextNode = node.next;

        // Remove pointers to node
        prevNode.next = nextNode;
        nextNode.prev = prevNode;
    }

    // Private method to insert node after head
    insertAfterHead(node) {
        const nextNode = this.head.next;
        this.head.next = node;
        nextNode.prev = node;
        node.prev = this.head;
        node.next = nextNode;
    }

    // Method to get the key from cache
    get(key_) {
        // Return -1 if it is not present in cache
        if (!this.mpp.has(key_)) {
            return -1;
        }

        const node = this.mpp.get(key_); // Get the node
        const val = node.val; // Get the value

        // Delete the node
        this.deleteNode(node);
        // Insert this node to front as it was recently used
        this.insertAfterHead(node);

        // Return the stored value
        return val;
    }

    // Method to update value if key exists, otherwise insert the key-value pair
    put(key_, value) {
        // Update the value if key is already present
        if (this.mpp.has(key_)) {
            const node = this.mpp.get(key_);
            node.val = value;

            // Delete the node
            this.deleteNode(node);
            // Insert this node to front as it was recently used
            this.insertAfterHead(node);

            return;
        }

        // Check if the capacity limit has reached
        if (this.mpp.size === this.cap) {
            // Get the least recently used node
            const node = this.tail.prev;

            // Delete node from map
            this.mpp.delete(node.key);

            // Delete node from doubly linked list
            this.deleteNode(node);
        }

        // Create a new node
        const newNode = new Node(key_, value);

        // Insert it in map
        this.mpp.set(key_, newNode);

        // Insert in doubly linked list
        this.insertAfterHead(newNode);
    }
}

// LRU Cache
const cache = new LRUCache(2);

// Queries
cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1) + " ");
cache.put(3, 3);
console.log(cache.get(2) + " ");
cache.put(4, 4);
console.log(cache.get(1) + " ");
console.log(cache.get(3) + " ");
console.log(cache.get(4) + " ");

Complexity Analysis:

Time Complexity: O(N) (where N is the number of queries)
Since the Put and Get method takes an average of constant time, the overall complexity to process all the queries is O(N) time.

Space Complexity: O(cap) (where cap is the capacity of the LRU cache)
Since the doubly linked list can store at most of the capacity number of key-value pairs, this takes O(cap) space.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Why using a Doubly Linked List?

Approach:

Dry Run:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code

Facts