LeetCode - 146 LRU缓存 （哈希双链表)

LRU讲的很不错https://leetcode.cn/problems/lru-cache/solution/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/

class LRUCache {
    //明确LRU缓存要实现什么功能
    //get(key) 如果key存在 获取其值 并把它设为最近使用过的节点
    // put(key,val) 如果key存在 更改节点的值 并且把它设为最近使用过的节点 如果它不存在 缓存满了 先删掉最近最少使用的节点 并讲它加入
    //缓存
    //头部节点存放最近最少使用的节点
    //尾部节点刚刚使用过
    class Node{//双链表节点
         int key;
         int val;
         Node prev;//前驱指针
         Node next;//后继指针
         public Node(int key,int val){
             this.key = key;
             this.val = val;
         }
    }
    class DoubleList{//双向链表
        private Node head;//头节点
        private Node tail;//尾节点
        private int size;
        public DoubleList(){
            this.head = new Node(0,0);
            this.tail = new Node(0,0);
            head.next = tail;
            tail.prev = head;
            size = 0;
        }
        //在尾节点之前添加节点x
        public void addLast(Node x){
          x.prev = tail.prev;
          x.next = tail;
          tail.prev.next = x;
          tail.prev = x;
          size += 1; 
        }
        //删除节点x
        public void remove(Node x){
           x.prev.next = x.next;
           x.next.prev = x.prev;
           size -= 1;
        }
        public int getSize(){
            return size;
        }
        public Node removeFirst(){
            if(head.next == tail)
              return null;
            Node first = head.next;
            remove(first);
            return first;
        }

    }
    private Map<Integer,Node> map;
    private DoubleList cache;
    private int cap;
    public LRUCache(int capacity) {
         this.map = new HashMap<>();
         this.cache = new DoubleList();
         this.cap = capacity;
    }
    public void makeRecently(int key){
         Node x = map.get(key);
         cache.remove(x);
         cache.addLast(x);
    }
    public int get(int key) {
          if(map.containsKey(key) == false)
            return -1;
          makeRecently(key);
          return map.get(key).val;
    }
    
    public void put(int key, int value) {
          if(map.containsKey(key) == true){
              // 修改map
              Node node = map.get(key);
              node.val = value;
              makeRecently(key);
              return ;
          }
          if(cache.getSize() == cap){
              Node first = cache.removeFirst();
              //这里说明了 在节点中也需要记录key值
              map.remove(first.key);
          }
          Node x = new Node(key,value);
          map.put(key,x);
          cache.addLast(x);
    }
}