LRU Cache (Using DLL + HashMap)

Welcome back, coders! Today, we're diving into a fascinating topic - the LRU Cache, implemented using a Doubly Linked List (DLL) and a HashMap. This lesson is perfect for beginners and intermediates alike, so let's get started!

What is an LRU Cache?

An LRU Cache (Least Recently Used Cache) is a data structure that stores data, with the policy of evicting the least recently used items first when the cache reaches its capacity. It's an essential tool in computer science, used in various applications like web browsers, operating systems, and databases.

💡 Pro Tip: The LRU Cache is a great way to balance between memory usage and speed, as it keeps frequently accessed data readily available while discarding infrequently used data.

Understanding DLL and HashMap

Before diving into the LRU Cache, let's briefly understand the two main components we'll be using:

Doubly Linked List (DLL): A DLL is a data structure that allows insertion and deletion of nodes at both ends, maintaining a link between the nodes in the reverse direction.
HashMap: A HashMap is a data structure that stores key-value pairs and allows fast lookups using the key.

📝 Note: We'll use these components to implement an efficient LRU Cache.

Implementing the LRU Cache

Now that we understand the basics, let's dive into the implementation. We'll create a custom LRUCache class with the following properties:

An internal HashMap (cache) that stores the key-value pairs.
A Doubly Linked List (lruList) that maintains the order of recently used items.
A maximum capacity (maxCapacity) for the cache.

Here's an outline of the methods we'll implement:

get(key): Retrieve the value for the given key from the cache.
put(key, value): Add the key-value pair to the cache and update the LRU List.
removeOldest(): Remove the least recently used item from the LRU List and the cache.

Example Code

java

import java.util.HashMap;
import java.util.Map;

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

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

class LRUCache {
    private int maxCapacity;
    private Map<Integer, ListNode> cache;
    private ListNode head;
    private ListNode tail;

    public LRUCache(int maxCapacity) {
        this.maxCapacity = maxCapacity;
        this.cache = new HashMap<>();
        this.head = new ListNode(-1, -1);
        this.tail = new ListNode(-1, -1);
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    // Implement the get(), put(), and removeOldest() methods here...
}

Putting it all together

In the following sections, we'll implement the get(), put(), and removeOldest() methods, along with detailed explanations and examples.

🎯 Stay tuned for the next parts of this lesson!

This lesson is just the beginning of our exploration into the LRU Cache using a DLL and HashMap. In the next parts, we'll implement the remaining methods and see practical examples that will help you understand and implement LRU Cache in your own projects. Happy coding! 🤖🚀