LRU DataStructure

 import java.util.*;

public class LRUCaheDataStructure {

    class Node {

        int key;

        int value;

        Node next;

        Node prev;

        public Node(int key, int value) {

            this.key = key;

            this.value = value;

        }

    }

    private int capacity;

    private HashMap<Integer, Node> cache = new HashMap<>();

    private Node head;

    private Node tail;

    public LRUCaheDataStructure(int capacity) {

        this.capacity = capacity;

        head = new Node(0, 0);

        tail = new Node(0, 0);

        head.next = tail;

        tail.prev = head;

    }

    private void remove(Node node) {

        Node prevNode = node.prev;

        Node nextNode = node.next;

        prevNode.next = nextNode;

        nextNode.prev = prevNode;

    }

    private void add(Node node) {

        node.next = head.next;

        node.prev = head;

        head.next.prev = node;

        head.next = node;

    }

    public int get(int key) {

        if (cache.containsKey(key)) {

            Node node = cache.get(key);

            remove(node);

            add(node);

            return node.value;

        }

        return -1;

    }

    public void put(int key, int value) {

        if (cache.containsKey(key)) {

            remove(cache.get(key));

        }

        Node node = new Node(key, value);

        add(node);

        cache.put(key, node);

        if (cache.size() > capacity) {

            Node lru = tail.prev;

            remove(lru);

            cache.remove(lru.key);

        }

    }

    public static void main(String[] args) {

        LRUCaheDataStructure lru = new LRUCaheDataStructure(2);

        lru.put(1, 1);

        lru.put(2, 2);

        System.out.println(lru.get(1));

        lru.put(3, 3);

        System.out.println(lru.get(2));

        lru.put(4, 4);

        System.out.println(lru.get(1));

        System.out.println(lru.get(3));

        System.out.println(lru.get(4));

    }

}