Untitled

public class LRUCache1<K, V> extends LRUCache<K, V> {
 
    private class Node<T, U> {
        Node<T, U> previous;
        Node<T, U> next;
        T key;
        U value;
 
        public Node(Node<T, U> previous, Node<T, U> next, T key, U value) {
            this.previous = previous;
            this.next = next;
            this.key = key;
            this.value = value;
        }
 
        @Override
        public String toString() {
            return "{" + key + "," + value + "}";
        }
 
        public String toStringWithNeighbors() {
            StringBuilder sb = new StringBuilder();
            if (previous != null) {
                sb.append("prev ");
                sb.append(previous);
                sb.append(" ");
            }
            sb.append(this);
            if (next != null) {
                sb.append(" next ");
                sb.append(next);
            }
            return sb.toString();
        }
    }
 
    private Node<K, V> leastRecentlyUsed;
    private Node<K, V> mostRecentlyUsed;
    private final int capacity;
    private int currentSize;
 
    LRUCache1(int capacity) {
        super(capacity);
        this.capacity = capacity;
        this.currentSize = 0;
        leastRecentlyUsed = new Node<>(null, null, null, null);
        mostRecentlyUsed = leastRecentlyUsed;
    }
 
    @Override
    V get(K key) {
        Node<K, V> tempNode = findNode(key);
        if (tempNode == null) {
            return null;
        }
        promoteNode(tempNode);
        return tempNode.value;
    }
 
    @Override
    void put(K key, V value) {
        Node<K, V> node = findNode(key);
        if (node != null) { // just update the value
            node.value = value;
            return;
        } else {
            addMostRecentlyUsed(key, value);
            if (currentSize == 0) {
                leastRecentlyUsed = mostRecentlyUsed;
            }
        }
 
        if (currentSize == capacity) {
            removeLeastRecentlyUsed();
        } else {
            currentSize++;
        }
    }
 
    private void addMostRecentlyUsed(K key, V value) {
        Node<K, V> myNode = new Node<>(mostRecentlyUsed, null, key, value);
        mostRecentlyUsed.next = myNode;
        mostRecentlyUsed = myNode;
    }
 
    private void removeLeastRecentlyUsed() {
        leastRecentlyUsed = leastRecentlyUsed.next;
        leastRecentlyUsed.previous = null;
    }
 
    private Node<K, V> findNode(K key) {
        Node<K, V> tempNode = mostRecentlyUsed;
        while (tempNode.key != key) {
            if (tempNode.previous == null) {
                return null; // not found
            }
            tempNode = tempNode.previous;
        }
        return tempNode;
    }
 
    private void promoteNode(Node<K, V> tempNode) {
        if (tempNode.key == mostRecentlyUsed.key) {
            return; // if it's most recently node, don't promote
        }
 
        Node<K, V> nextNode = tempNode.next;
        Node<K, V> previousNode = tempNode.previous;
 
        if (tempNode.key == leastRecentlyUsed.key) { // If we are in the beginning
            nextNode.previous = null;
            leastRecentlyUsed = nextNode;
        } else { // If we are in the middle,
            previousNode.next = nextNode;
            nextNode.previous = previousNode;
        }
 
        // Move node to the most recently used (right/end)
        tempNode.previous = mostRecentlyUsed;
        mostRecentlyUsed.next = tempNode;
        mostRecentlyUsed = tempNode;
        mostRecentlyUsed.next = null;
    }
}