LRU Cache - Java Solution

1. Introduction

In this blog post, we will design and implement a data structure for a Least Recently Used (LRU) cache in Java. An LRU cache is a popular caching algorithm that removes the least recently used item when the cache reaches its capacity.

Problem

Design an LRU Cache that supports two operations: get(key) to retrieve a value and put(key, value) to set or insert a value. When the cache reaches its capacity, it should invalidate the least recently used item before inserting a new item.

2. Solution Steps

1. Use a HashMap for constant-time lookups and a Doubly Linked List to maintain insertion order.

2. For get(key), if the key is present in the cache, move the corresponding node to the front of the list (most recently used).

3. For put(key, value), insert the new node at the front of the list. If the cache is at capacity, remove the node at the end of the list (least recently used) before inserting a new one.

4. Ensure constant time operations for both get and put.

3. Code Program

import java.util.HashMap;

class LRUCache {

    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
    }

    private void addNode(DLinkedNode node) {
        // Always add the new node right after head
        node.prev = head;
        node.next = head.next;

        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DLinkedNode node){
        // Remove an existing node from the linked list
        DLinkedNode prev = node.prev;
        DLinkedNode next = node.next;

        prev.next = next;
        next.prev = prev;
    }

    private void moveToHead(DLinkedNode node){
        // Move certain node in between to the head
        removeNode(node);
        addNode(node);
    }

    private DLinkedNode popTail() {
        // Pop the current tail
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }

    private HashMap<Integer, DLinkedNode> cache = new HashMap<>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;

        head = new DLinkedNode();
        tail = new DLinkedNode();

        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) return -1;

        // Move the accessed node to the head
        moveToHead(node);

        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);

        if(node == null) {
            DLinkedNode newNode = new DLinkedNode();
            newNode.key = key;
            newNode.value = value;

            cache.put(key, newNode);
            addNode(newNode);

            size++;

            if(size > capacity) {
                // Pop the tail
                DLinkedNode tail = popTail();
                cache.remove(tail.key);
                size--;
            }
        } else {
            // Update the value
            node.value = value;
            moveToHead(node);
        }
    }
}

// Main method for testing
public class Main {
    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);

        cache.put(5, 7);
        cache.put(8, 20);
        System.out.println("Get 5: " + cache.get(5));       // returns 7
        cache.put(3, 6);    // evicts key 8
        System.out.println("Get 8: " + cache.get(8));       // returns -1 (not found)
        cache.put(4, 12);   // evicts key 5
        System.out.println("Get 5: " + cache.get(5));       // returns -1 (not found)
        System.out.println("Get 3: " + cache.get(3));       // returns 6
        System.out.println("Get 4: " + cache.get(4));       // returns 12
    }
}

Output:

Get 5: 7
Get 8: -1
Get 5: -1
Get 3: 6
Get 4: 12

Explanation:

The LRU cache is designed with a capacity of 2. 

When we put keys 5 and 8, they are stored in the cache. 

A get(5) returns 7. Then, putting key 3 causes key 8 to be evicted (as it's the least recently used), making a get(8) return -1. 

Similarly, putting key 4 evicts key 5, making a get(5) return -1. 

Finally, get(3) and get(4) return 6 and 12, respectively, as they are present in the cache.