146. LRU 缓存

class LRUCache {
    //双线链表的节点类
    class DoublyListNode { 
        public int key;
        public int val;
        public DoublyListNode pre;
        public DoublyListNode next;
        public DoublyListNode() {}
        public DoublyListNode(int val) { this.val = val; }
    }
    //双相链表的头节点
    private DoublyListNode head;
    //双线链表的尾结点
    private DoublyListNode tail;
    //维护索引的Map
    Map<Integer,DoublyListNode> map;
    //大小
    int capacity;
    public LRUCache(int capacity) {
        //保存大小
        this.capacity = capacity;
        //链表头尾节点初始化，然后头尾相连形成双链表结构
        head = new DoublyListNode();
        tail = new DoublyListNode();
        head.next = tail;
        tail.pre = head;
        //初始化索引MAp
        map = new HashMap<>();
    }
    public int get(int key) {
        //如果map里面没有就直接返回-1
        if(!map.containsKey(key)){
            return -1;
        }
        DoublyListNode node = map.get(key);
        //从中间移除node
        doublyListNodeRemove(node);
        // 再 从头部插入node
        doublyListNodeInsert(head,node);
        return node.val;
    }
    public void put(int key, int value) {
        //如果map里不存在这个key
        if(!map.containsKey(key)){
            DoublyListNode node = new DoublyListNode();
            node.key  = key;
            node.val = value;
            //保存hashMap
            map.put(key,node);
            //从头部插入链表
            doublyListNodeInsert(head,node);
            //如果超过最大长度限制了，则删除链表尾部最后一个节点，删除最后一个节点的hashMap的缓存
            if(map.size() > capacity){     
                //清掉map的缓存，tail的pre的key
                map.remove(tail.pre.key);
                //删除尾部最后一个节点，也就是tald的pre
                doublyListNodeRemove(tail.pre);
            }
        }else {
            //如果存在MAP里了，就更新这个值，然在在链表中删掉，放入开头插入
            DoublyListNode node = map.get(key);
            node.val = value;
            //从中间移除node
            doublyListNodeRemove(node);
            // 再 从头部插入node
            doublyListNodeInsert(head,node);
        }
    }
    /**
     * 双向链表删除一个node(从中间直接删掉)
     * @param node
     */
    public void doublyListNodeRemove(DoublyListNode node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }
    /**
     * 双向链表。在P后面插入一个节点
     * @param p
     * @param node
     */
    public void doublyListNodeInsert(DoublyListNode p ,DoublyListNode node){
        //node 和 p的next建立联系
        p.next.pre = node;
        node.next = p.next;
        // node 和 p 建立联系
        p.next = node;
        node.pre = p;
    }
}