Demystifying LRU Cache in Java Using a Custom HashMap

---

What is an LRU Cache?

In many systems such as browsers, operating system memory management, and databases, we need to keep recently used items easily accessible while discarding the least used ones. That’s where LRU (Least Recently Used) Cache comes in.

An LRU Cache evicts the least recently used item once it reaches its fixed capacity.

But how do we ensure both:

• Fast updates when data is accessed or inserted

• Constant time complexity for get and put

We achieve this by combining:

1. A HashMap for fast key-based lookups.

2. A Doubly Linked List for tracking access order.

---

Design Overview

Let’s understand the two core data structures used:

1. Doubly Linked List

Maintains the order of usage — the most recently used item is kept at the front, and the least recently used item is pushed toward the back.

Each node contains:

• key

• value

• prev

• next

2. Custom MyHashMap

LINK TO CUSTOM HASHMAP

Instead of Java’s built-in HashMap, a custom implementation (MyHashMap) is used for learning purposes. It maps keys to their corresponding nodes for fast access.

---

Core Operations

put(key, value)

• If the key exists, update its value and move it to the front of the list.

• If the key doesn’t exist, insert it at the front.

• If the cache is at full capacity, remove the node at the tail (the least recently used item).

get(key)

• If the key is found, move the corresponding node to the front and return its value.

• If not, return null.

---

Full Java Implementation

package misc;
import java.util.*;

public class LRU<K,V> {
    class Node {
        K key;
        V val;
        Node prev, next;
        Node(K key, V val) {
            this.key = key;
            this.val = val;
        }
    }

    final int capacity;
    private MyHashMap<K, Node> map;
    private Node head, tail;

    public LRU(int capacity) {
        this.capacity = capacity;
        map = new MyHashMap<>();
        head = new Node(null, null);  // dummy head
        tail = new Node(null, null);  // dummy tail
        head.next = tail;
        tail.prev = head;
    }

    public V get(K key) {
        Node node = map.get(key);
        if (node == null) return null;
        moveToFront(node);
        return node.val;
    }

    public void put(K key, V value) {
        Node node = map.get(key);
        if (node != null) {
            node.val = value;
            moveToFront(node);
        } else {
            if (map.size() == capacity) {
                removeLeastRecentlyUsed();
            }
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            addToFront(newNode);
        }
    }

    private void moveToFront(Node node) {
        removeNode(node);
        addToFront(node);
    }

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

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void removeLeastRecentlyUsed() {
        Node lru = tail.prev;
        if (lru != head) {
            removeNode(lru);
            map.remove(lru.key);
        }
    }

    public void printCacheState() {
        Node curr = head.next;
        while (curr != tail) {
            System.out.print("[" + curr.key + ":" + curr.val + "] ");
            curr = curr.next;
        }
        System.out.println();
    }

    public int size() {
        return map.size();
    }

    public static void main(String[] args) {
        LRU<Integer, String> cache = new LRU<>(3);

        cache.put(1, "A");
        cache.put(2, "B");
        cache.put(3, "C");
        cache.printCacheState(); // [3:C] [2:B] [1:A]

        cache.get(2);
        cache.printCacheState(); // [2:B] [3:C] [1:A]

        cache.put(4, "D");
        cache.printCacheState(); // [4:D] [2:B] [3:C]

        System.out.println(cache.get(1)); // null
        System.out.println(cache.get(3)); // C
    }
}

---

Dry Run Walkthrough

Let’s walk through the steps in the main method:

1. put(1, "A"), put(2, "B"), put(3, "C")

   Cache state: [3:C] [2:B] [1:A]

2. get(2)

   Moves 2 to the front

   New state: [2:B] [3:C] [1:A]

3. put(4, "D")

   Cache is full — evicts 1

   Final state: [4:D] [2:B] [3:C]

4. get(1) returns null (evicted)

5. get(3) returns C

---

Why a Doubly Linked List?

Using a doubly linked list allows:

• Constant time removal of any node from any position

• Efficient updates of both previous and next references

A singly linked list would require traversal from the head to remove the tail, which is not optimal for this use case.

---

Key Takeaways

• All operations (get, put, remove) run in constant time.

• Separation of concerns: HashMap for access, Linked List for order.

• Custom MyHashMap improves learning of internal structures.

• This is a great foundational exercise in system design and low-level data structure implementation.