[Java] Cleanest solution and easiest to understand


  • 1
    P
    public class LRUCache{
    Node head;
    Node tail;
    HashMap<Integer, Node> map;
    int maxCapacity;
    public LRUCache(int capacity) {
        if (capacity < 1) throw new IllegalArgumentException();
        this.maxCapacity = capacity;
        this.map = new HashMap<>();
    }
    
    public int get(int key) {
        if (map.containsKey(key))
        {
            Node n = map.get(key);
            this.removeNode(n);
            this.addNode(n);
            return n.value;
        }
        
        return -1;
    }
    
    public void set(int key, int value) {
        if (map.containsKey(key))
        {
            Node n = map.get(key);
            n.value = value;
            this.removeNode(n);
            this.addNode(n);
            return;
        }
        
        if (map.size() == maxCapacity)
        {
            map.remove(this.tail.key);
            this.removeNode(this.tail);
        }
        
        Node n = new Node(key, value);
        this.addNode(n);
        map.put(key, n);
    }
    
    private void addNode(Node n)
    {
        n.prev = null;
        n.next = this.head;
        if (this.head != null)
        {
            this.head.prev = n;
            this.head = n;
        }
        else
        {
            this.head = n;
            this.tail = n;
        }
    }
    
    private void removeNode(Node n)
    {
        Node prev = n.prev;
        Node next = n.next;
        if (prev == null) this.head = next;
        else prev.next = next;
        
        if (next == null) this.tail = prev;
        else next.prev = prev;
    }
    
    class Node
    {
        int key;
        int value;
        Node next;
        Node prev;
        
        public Node(int key, int value)
        {
            this.key = key;
            this.value = value;
        }
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.