146. LRU 缓存

approach 1

class LRUCache {
    int cap;
    int size;
    Node head;
    Node tail;
    Map<Integer, Node> map = new HashMap<>();
    public LRUCache(int capacity) {
        cap = capacity;
        size = 0;
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;
    }
    
    public int get(int key) {
        Node n = map.get(key);
        if (n == null) return -1;

        get(n);
        insert(n);

        return n.val;
    }
    
    public void put(int key, int value) {
        if (cap == 0) return;
        Node n = map.get(key);
        if (n == null) {
            if (cap == size) {
                Node p = poll();
                map.remove(p.key);
            } else {
                size++;
            }
            n = new Node();
        }
        n.key = key;
        n.val = value;
        map.put(key, n);

        get(n);
        insert(n);
    }


    public Node poll() {
        if (size == 0) return null;
        Node n = head.next;

        Node next = n.next;
        head.next = next;
        next.pre = head;
        return n;
    }

    public void get(Node n) {
        Node pre = n.pre;
        Node next = n.next;

        if (pre != null) {
            pre.next = next;
        }
        if (next != null) {
            next.pre = pre;
        }
    }

    public void insert(Node n) {
        Node pre = tail.pre;
        
        pre.next = n;
        tail.pre = n;
        n.pre = pre;
        n.next = tail;
    }

    class Node {
        int key;
        int val;
        Node pre;
        Node next;

        public String toString() {
            return "[key:" + key + "; val:" + val + "; pre:" + pre + "; next:" + next + "]";
        }
    }
}