leetcode LRU cache

146. LRU 缓存

class LRUCache {
    Map<Integer, Node> cache;
    DLinkedNode list = new DLinkedNode();
    int capacity;

    public LRUCache(int capacity) {
        this.capacity =  capacity;
        cache = new HashMap<>(capacity);
    }
    
    public int get(int key) {
        Node node = cache.get(key);
        if(node == null) return -1;
        list.update(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        Node node = cache.get(key);
        if(node != null){
            list.remove(node);
        }else if(cache.size() >= capacity) {
            Node rNode = list.removeTail();
            cache.remove(rNode.key);
        }
        Node adder = new Node(key, value);
        list.add(adder);
        cache.put(key, adder);
    }
}
class Node{
    int key;
    int value;
    Node pre;
    Node next;
    public Node(int key, int value){
        this.key = key;
        this.value = value;
    }
}
class DLinkedNode{
    Node head;
    Node tail;

    public DLinkedNode(){
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        head.next = tail;
        tail.pre = head;
    }

    void add(Node node){
        node.next = head.next;
        node.pre = head;
        head.next = node;
        node.next.pre = node;
    }

    void update(Node node){
        remove(node);
        add(node);
    }

    void remove(Node node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
    
    Node removeTail(){
        Node res = tail.pre;
        remove(res);
        return res;
    }
}