LRU Cache - Java Solution

1. Introduction

In this post, we'll explore the design and implementation of a Least Recently Used (LRU) Cache in Java. An LRU Cache is a popular data structure used to store a limited number of items such that, when the cache reaches its capacity, the least recently accessed items are discarded to make space for new ones. This data structure is commonly used in applications where quick access to data is crucial, like in web servers and database query optimizations.

Problem

Implement an LRUCache class that supports two operations in O(1) average time complexity:

1. get(int key): Return the value of the key if it exists in the cache, otherwise return -1.

2. put(int key, int value): Insert or update the value of the key. If the number of keys exceeds the cache's capacity, evict the least recently used key.

2. Solution Steps

1. Use a combination of a HashMap and a Doubly Linked List to achieve O(1) time complexity for both get and put operations.

2. The HashMap will map keys to nodes in the linked list, which will store the key-value pairs.

3. For every get and put operation, update the linked list to move the accessed node to the front (head), indicating recent use.

4. When the capacity is exceeded, remove the node from the end (tail) of the list.

5. Implement methods to add and remove nodes from the linked list.

3. Code Program

import java.util.HashMap;

class LRUCache {
    class Node {
        int key;
        int value;
        Node prev;
        Node next;
    }

    private void addNode(Node node) {
        // Add new node right after head
        node.prev = head;
        node.next = head.next;

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

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

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

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

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

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

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

        head = new Node();
        tail = new Node();

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

    public int get(int key) {
        Node 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) {
        Node node = cache.get(key);

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

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

            size++;

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

public class Main {
    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println(cache.get(1)); // returns 1
        cache.put(3, 3); // evicts key 2
        System.out.println(cache.get(2)); // returns -1 (not found)
        cache.put(4, 4); // evicts key 1
        System.out.println(cache.get(1)); // returns -1 (not found)
        System.out.println(cache.get(3)); // returns 3
        System.out.println(cache.get(4)); // returns 4
    }
}

Output:

1
-1
-1
3
4

Explanation:

1. LRUCache: The class constructor initializes the cache with a given capacity. It uses a HashMap to store key-node pairs and a Doubly Linked List to track the order of use.

2. addNode, removeNode, and moveToHead are helper methods for managing nodes in the doubly linked list.

3. get: This method returns the value for the key if it exists in the cache. It moves the accessed node to the head of the list to mark it as recently used.

4. put: This method inserts a new key-value pair or updates the value of an existing key. It also ensures that the least recently used item is evicted if the cache exceeds its capacity.

5. The combination of HashMap and Doubly Linked List allows both get and put operations to be performed in O(1) time.

6. The implementation efficiently tracks the most and least recently used items, making it suitable for scenarios where quick access to frequently used items is required.