核心思想：HashMap+链表

class LRUCache {
    public class CacheNode{
        public CacheNode prev;
        public CacheNode next;
        public int key;
        public int value;

        public CacheNode(int key,int value){
            this.key=key;
            this.value=value;
            this.prev=null;
            this.next=null;
        }
    }

   private int capacity;
   Map<Integer,CacheNode> map=new HashMap();
   CacheNode head=new CacheNode(-1,-1);
   CacheNode tail=new CacheNode(-1,-1);

    public LRUCache(int capacity) {
        this.capacity=capacity;
        head.next=tail;
        tail.prev=head;

    }
    
    public int get(int key) {
        if(!map.containsKey(key)){
            return -1;
        }

        //先删除
        CacheNode current=map.get(key);
        current.prev.next=current.next;
        current.next.prev=current.prev;
        MoveToTail(current);
        return current.value;
    }
    
    public void put(int key, int value) {
      if(get(key)!=-1){
          map.get(key).value=value;
          return;
      }

      if(map.size()==capacity){
          map.remove(head.next.key);
          head.next=head.next.next;
          head.next.prev=head;
       
      }

      
      CacheNode insert=new CacheNode(key,value);
      map.put(key,insert);
      MoveToTail(insert);


    }

    public  void MoveToTail(CacheNode current){
        tail.prev.next=current;
        current.prev=tail.prev;
        current.next=tail;
        tail.prev=current;


    }
}

/**
 * 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);
 */