Understanding LRU Cache in Java

Introduction & Problem Explanation

An LRU (Least Recently Used) Cache is a popular caching mechanism used in systems design. Caches are high-speed, temporary storage structures with limited capacity. When the cache becomes full and a new item needs to be stored, the cache must evict an old item to make room. The LRU policy ejects the item that has not been accessed for the longest duration.

To design an efficient LRU Cache, we must support two core operations:

• get(key): Retrieve the value associated with the key if it exists in the cache; otherwise, return -1. When accessed, this key is marked as the most recently used.
• put(key, value): Insert or update the key-value pair. If the cache reaches its capacity, we must evict the least recently used key before inserting the new one.

Crucially, both operations must run in O(1) constant time complexity. To achieve this, we combine two data structures: a HashMap (for instant key-to-node lookups) and a custom Doubly Linked List (for instant removal and insertion of elements at the boundaries).

The Algorithmic Approach

HashMap + Doubly Linked List (O(1) Get and Put)

We implement a custom Doubly Linked List with dummy head and tail nodes:

• Dummy Nodes: Dummy head and tail act as sentinels. They linked together initially: head.next = tail and tail.prev = head. This eliminates null pointer checks during insertions and deletions.
• HashMap Lookup: The map stores the key and a reference to its corresponding Node in the list. This lets us jump directly to any node in O(1) time, avoiding linear list scans.
• Access Updates: Whenever a key is accessed (via get) or updated (via put), we disconnect its node from its current place in the list and insert it immediately after the dummy head. This keeps the list ordered by recency, with the most recently used at the front and the least recently used at the back (before the dummy tail).
• Ejection: When capacity is exceeded during a put, we remove the node right before the dummy tail (tail.prev) from both the list and the HashMap.

Step-by-Step Execution Walkthrough

Let's trace an LRU Cache with a capacity of 2:

1. Step 1 (Initialize):
   • Capacity = 2. Dummy list: head ↔ tail. Map is empty.
2. Step 2 (put(1, 1)):
   • Create Node(1, 1). Insert after head: head ↔ Node(1,1) ↔ tail.
   • Add to map: {1: Node(1,1)}.
3. Step 3 (put(2, 2)):
   • Create Node(2, 2). Insert after head: head ↔ Node(2,2) ↔ Node(1,1) ↔ tail.
   • Add to map: {1: Node(1,1), 2: Node(2,2)}.
4. Step 4 (get(1)):
   • Key 1 is in map. Retrieve Node(1,1).
   • Move to front: Remove Node(1,1) from list and insert after head: head ↔ Node(1,1) ↔ Node(2,2) ↔ tail.
   • Return value 1.
5. Step 5 (put(3, 3)):
   • Key 3 is new. Cache size (2) equals capacity (2). Eject least recently used node.
   • Eject node before tail: tail.prev is Node(2,2). Remove it from map: {1: Node(1,1)}. Remove from list: head ↔ Node(1,1) ↔ tail.
   • Create and insert Node(3, 3) after head: head ↔ Node(3,3) ↔ Node(1,1) ↔ tail.
   • Add to map: {1: Node(1,1), 3: Node(3,3)}.
6. Step 6 (get(2)):
   • Key 2 is not in map. Return -1.

Key Code Snippets & Explanations

Here is why the main logic in the solution is important:

• node.prev.next = node.next; node.next.prev = node.prev;: Disconnects a node from its current spot in the linked list. Because it is a doubly linked list, we can perform this deletion in O(1) time without scanning the list.
• head.next.prev = node; node.next = head.next; ...: Inserts a node immediately after the dummy head, marking it as the most recently accessed.
• remove(tail.prev);: Evicts the least recently used node. Since the tail node is connected to the back of the list, tail.prev points directly to the victim node.

Java Implementation Code

Below is the complete, self-contained Java source code that solves this problem. It also includes a main method that traces the execution with console outputs.

package io.practise.dsa;

import java.util.*;

public class LRUCache {

    // Doubly Linked List Node to store key-value pair and pointers
    static class Node {
        int key, val;
        Node prev, next;
        Node(int k, int v) { 
            key = k; 
            val = v; 
        }
    }

    private final int capacity;
    private final Map<Integer, Node> map;
    private final Node head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }

    // Get value from cache and mark node as recently accessed
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);
        remove(node);          // Remove node from its current position
        insertToFront(node);   // Move node to the head of the list
        return node.val;
    }

    // Add or update value in cache and evict least recently used if full
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            remove(map.get(key));
        }
        if (map.size() == capacity) {
            remove(tail.prev); // Evict least recently used (node before tail dummy)
        }
        insertToFront(new Node(key, value));
    }

    // Unlink node from list and remove from HashMap
    private void remove(Node node) {
        map.remove(node.key);
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // Insert node directly after dummy head and add to HashMap
    private void insertToFront(Node node) {
        map.put(node.key, node);
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    public static void main(String[] args) {
        System.out.println("--- LRU Cache Demonstration ---");
        LRUCache cache = new LRUCache(2);
        
        System.out.println("Putting (1, 1)");
        cache.put(1, 1);
        System.out.println("Putting (2, 2)");
        cache.put(2, 2);
        
        System.out.println("Get(1): " + cache.get(1) + " (Expected: 1)"); // returns 1
        
        System.out.println("Putting (3, 3) [Ejects Key 2]");
        cache.put(3, 3); // evicts key 2
        
        System.out.println("Get(2): " + cache.get(2) + " (Expected: -1)"); // returns -1 (not found)
        
        System.out.println("Putting (4, 4) [Ejects Key 1]");
        cache.put(4, 4); // evicts key 1
        
        System.out.println("Get(1): " + cache.get(1) + " (Expected: -1)"); // returns -1 (not found)
        System.out.println("Get(3): " + cache.get(3) + " (Expected: 3)");  // returns 3
        System.out.println("Get(4): " + cache.get(4) + " (Expected: 4)");  // returns 4
    }
}

Conclusion

Designing an LRU Cache demonstrates how mapping a Hash Table with a Doubly Linked List solves opposing performance constraints. The HashMap guarantees rapid access, while the list enables fast additions and updates, maintaining an O(1) runtime for all cache operations.