Untitled

package production.practiceDev.feb;

import java.util.HashMap;
import java.util.Map;

/**
 * LRU Cache Implementation
 * Time Complexity:
 *      get()  -> O(1)
 *      put()  -> O(1)
 * Space Complexity:
 *      O(capacity)
 */
public class LRUCache {

    /**
     * Doubly Linked List Node
     */
    private static class Node {
        int key;
        int value;
        Node prev;
        Node next;

        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private final int capacity;
    private final Map<Integer, Node> cache;

    // Dummy head and tail nodes
    private final Node head;
    private final Node tail;

    /**
     * Constructor
     */
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();

        head = new Node(-1, -1);
        tail = new Node(-1, -1);

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

    /**
     * Get value from cache
     */
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }

        Node node = cache.get(key);
        moveToHead(node);
        return node.value;
    }

    /**
     * Put key-value in cache
     */
    public void put(int key, int value) {

        if (cache.containsKey(key)) {
            Node existingNode = cache.get(key);
            existingNode.value = value;
            moveToHead(existingNode);
            return;
        }

        if (cache.size() == capacity) {
            Node lruNode = tail.prev;
            removeNode(lruNode);
            cache.remove(lruNode.key);
        }

        Node newNode = new Node(key, value);
        cache.put(key, newNode);
        addAfterHead(newNode);
    }

    /**
     * Move existing node to head (mark as recently used)
     */
    private void moveToHead(Node node) {
        removeNode(node);
        addAfterHead(node);
    }

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

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

    /**
     * Remove node from list
     */
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    /**
     * Print cache (MRU -> LRU)
     */
    public void printCache() {
        Node current = head.next;

        System.out.print("Cache (MRU -> LRU): ");

        while (current != tail) {
            System.out.print("[" + current.key + "=" + current.value + "] ");
            current = current.next;
        }

        System.out.println();
    }

    /**
     * Driver
     */
    public static void main(String[] args) {

        LRUCache cache = new LRUCache(3);

        cache.put(12, 320);
        cache.put(42, 234);
        cache.put(3, 3);

        cache.printCache();

        cache.get(42);
        cache.printCache();

        cache.put(34, 34);
        cache.printCache();
    }
}