Understanding LRU Cache in Java

Understanding the Problem & Caching Strategies

An LRU (Least Recently Used) Cache is a foundational structure in modern software engineering, acting as a high-speed, temporary storage buffer with strict capacity constraints. When the buffer becomes full and a new entry needs to be recorded, the cache must evict an older item to make room. The LRU eviction policy targets the item that has remained unaccessed for the longest duration.

To implement a production-grade LRU Cache, we must support two basic operations:

• get(key): Retrieves the value associated with the key if it exists in the cache; otherwise, it returns -1. Crucially, fetching a key must mark it as the most recently accessed item.
• put(key, value): Inserts a new key-value pair or updates an existing key. If inserting causes the cache to exceed capacity, we must evict the least recently used key prior to writing.

Crucially, both operations must execute in O(1) constant time complexity. Achieving constant-time execution for both search and update requires combining two complementary data structures: a HashMap (providing instant O(1) lookup mapping keys to node references) and a Doubly Linked List (allowing O(1) node removal and insertion at the boundary sentinels).

Solving the Problem

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

Let's look at the implementation details of this dual-structure pattern:

• Dummy Sentinel Nodes: We initialize dummy head and dummy tail nodes that remain fixed at the boundaries. Initially, they link directly to each other: head.next = tail and tail.prev = head. These sentinels eliminate the need for edge-case null pointer checks during node insertions and deletions.
• Map-to-Node Reference Map: The HashMap maps keys directly to the memory address of their corresponding Node structures in the Doubly Linked List. This allows us to jump straight to any node, bypassing the need to search the list sequentially.
• Access Updates: When a key is read or updated, we unlink the node from its current position in the list and insert it immediately after the dummy head sentinel. This keeps the list ordered chronologically, with the most recently used node at the front and the least recently used node sitting right before the dummy tail sentinel.
• Eviction Trigger: When a put operation exceeds capacity, we locate the victim node at tail.prev. We unlink it from the list and delete its key from the HashMap to free up capacity.

Step-by-Step Execution Trace

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

1. Step 1 (Initialization):
   • Cache capacity is set to 2. Sentinel state: head ↔ tail. HashMap: {}.
2. Step 2 (put(1, 1)):
   • Create Node(1, 1). Insert it at the front: head ↔ Node(1, 1) ↔ tail.
   • Add to map: {1: Node(1, 1)}.
3. Step 3 (put(2, 2)):
   • Create Node(2, 2). Insert it at the front: head ↔ Node(2, 2) ↔ Node(1, 1) ↔ tail.
   • Add to map: {1: Node(1, 1), 2: Node(2, 2)}.
4. Step 4 (get(1)):
   • HashMap lookup finds Node(1, 1).
   • Update recency: Unlink Node(1, 1) from the middle and move it to the head: head ↔ Node(1, 1) ↔ Node(2, 2) ↔ tail.
   • Return value 1.
5. Step 5 (put(3, 3)):
   • The key 3 is new. Cache size 2 is at capacity.
   • We must evict the least recently used element. We locate tail.prev, which is Node(2, 2).
   • Unlink Node(2, 2) from the list: head ↔ Node(1, 1) ↔ tail.
   • Remove key 2 from the map: {1: Node(1, 1)}.
   • Create Node(3, 3) and insert it at the front: head ↔ Node(3, 3) ↔ Node(1, 1) ↔ tail.
   • Add key 3 to the map: {1: Node(1, 1), 3: Node(3, 3)}.
6. Step 6 (get(2)):
   • Key 2 is searched in the HashMap. It is missing (returning -1).

Code Implementation Details

Let's highlight the low-level pointer manipulations:

• node.prev.next = node.next; node.next.prev = node.prev; bypasses the node completely. By having references to both the previous and next nodes, we execute deletions in O(1) time.
• node.next = head.next; node.prev = head; head.next.prev = node; head.next = node; patches the new node right between head and the first element.
• The node immediately preceding the dummy tail (tail.prev) is always the least recently used element, making it the eviction candidate.

Full Java Solution

Below is the complete Java implementation featuring sentinel nodes, a lookup HashMap, and a custom doubly linked list implementation, including a test harness in the main method.

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 & Takeaways

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.