LRU Cache (using HashMap + Doubly Linked List)

Welcome to our comprehensive guide on implementing an LRU Cache using a combination of HashMap and Doubly Linked List! This lesson is designed for both beginners and intermediate learners, so let's get started. 🎯

What is an LRU Cache?

An LRU Cache (Least Recently Used Cache) is a data structure that stores frequently used data and removes the least recently used data when the cache is full. It's a common technique used to optimize performance in many real-world applications, such as web browsers, operating systems, and database systems. 📝

Why Use an LRU Cache?

An LRU Cache provides a trade-off between memory usage and speed. By keeping track of the most frequently used data and removing the least recently used data, we can maintain a cache with a fixed size while still providing quick access to frequently accessed data. 💡

Implementing an LRU Cache with HashMap and Doubly Linked List

To implement an LRU Cache, we'll use two main components:

HashMap: To store key-value pairs, where the key represents the cache key and the value represents the node in the Doubly Linked List.
Doubly Linked List: To maintain the order of elements based on their usage, with the most recently used element at the head and the least recently used element at the tail.

Creating the Doubly Linked List Node

First, let's define our Doubly Linked List Node.

java

class Node {
    int key;
    int value;
    Node prev;
    Node next;

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

Creating the LRUCache Class

Now, let's create the LRUCache class.

java

import java.util.HashMap;

class LRUCache {
    private int capacity;
    private HashMap<Integer, Node> cache;
    private Node head;
    private Node tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
    }
}

Adding and Removing Elements

We'll need methods to add and remove elements from the cache and the Doubly Linked List.

java

public void put(int key, int value) {
    // ...
}

public int get(int key) {
    // ...
}

private Node removeOldestNode() {
    // ...
}

private void addToFront(Node node) {
    // ...
}

Implementing the put and get Methods

Finally, we'll implement the put and get methods, which will handle the core functionality of the LRUCache.

java

public void put(int key, int value) {
    Node node = cache.get(key);
    if (node == null) {
        if (cache.size() >= capacity) {
            // Remove the least recently used node
            Node oldestNode = removeOldestNode();
            // Remove the node from the cache
            cache.remove(oldestNode.key);
        }
        // Create a new node and add it to the cache and the Doubly Linked List
        Node newNode = new Node(key, value);
        cache.put(key, newNode);
        addToFront(newNode);
    } else {
        // Update the value and move the node to the front of the Doubly Linked List
        node.value = value;
        removeNode(node);
        addToFront(node);
    }
}

public int get(int key) {
    Node node = cache.get(key);
    if (node == null) {
        return -1; // or some default value
    }
    // Move the node to the front of the Doubly Linked List
    removeNode(node);
    addToFront(node);
    return node.value;
}

Implementing the removeOldestNode, addToFront, and removeNode Methods

Here's how you can implement the remaining methods.

java

private Node removeOldestNode() {
    if (head == null) {
        return null;
    }
    Node oldestNode = head;
    head = head.next;
    if (head != null) {
        head.prev = null;
    }
    return oldestNode;
}

private void addToFront(Node node) {
    node.next = head;
    if (head != null) {
        head.prev = node;
    }
    head = node;
    if (tail == null) {
        tail = head;
    }
}

private void removeNode(Node node) {
    if (node.prev != null) {
        node.prev.next = node.next;
    }
    if (node.next != null) {
        node.next.prev = node.prev;
    }
    if (node == head) {
        head = node.next;
        if (head != null) {
            head.prev = null;
        }
    }
}

Quiz

With this detailed guide, you should now have a solid understanding of implementing an LRU Cache using a combination of HashMap and Doubly Linked List. Happy coding! 🎉