LeetCode 146. LRU 缓存

题目

class LRUCache{
    //HashMap的value  双向链表维护LRU
    class Node {
        int key, value;
        Node l, r;
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
        public Node(){}
    }

    //size当前大小，capacity总容量
    private int size, capacity;
    private HashMap<Integer, Node> mp = new HashMap<>();
    //虚拟头尾
    Node head, tail;

    //初始化
    public LRUCache(int capacity) {
        head = new Node();
        tail = new Node();
        head.r = tail;
        tail.l = head;
        this.size = 0;
        this.capacity = capacity;
    }
    
    public int get(int key) {
        //表中已有该key，移动到头
        if (mp.containsKey(key)) {
            Node node = mp.get(key);
            moveToHead(node);
            return node.value;
        } else {
            return -1;
        }
    }
    
    public void put(int key, int value) {
        //表中有key，移动到头并更新值
        if (mp.containsKey(key)) {
            Node node = mp.get(key);
            node.value = value;
            moveToHead(node);
            //System.out.println(key + " " + size + " " + node.value);
        } else {
            //没有key，添加node到头并维护链表大小
            Node node = new Node(key, value);
            addToHead(node);
            size ++ ;
            if (size > capacity) {
                removeTail();
                size -- ;
            }
        }
    }

    public void moveToHead(Node node) {
        remove(node);
        addToHead(node);
    }

    public void addToHead(Node node) {
        node.r = head.r;
        node.l = head;
        head.r.l = node;
        head.r = node;
        //维护mp
        mp.put(node.key, node);
    }

    public void removeTail() {
        remove(tail.l);
    }

    public void remove(Node node) {
        node.l.r = node.r;
        node.r.l = node.l;
        //维护mp
        mp.remove(node.key);
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */