一道经典题目，用双向链表去做能够满足O1的复杂度

核心代码如下

class LRUCache {
   MyLinkedList myLinkedList;
   int size;
   int capacity;
   HashMap map;
   public LRUCache(int capacity) {
​
​
       myLinkedList=new MyLinkedList();
       this.capacity=capacity;
       size=0;
       map=new HashMap<>();
  }
​
   public int get(int key) {
​
       if (!map.containsKey(key)){
           return -1;
      }
   //   拿出来 放到顶部
​
       MyNode current = map.get(key);
​
       myLinkedList.deleteAndAddFirst(current);
​
       return current.val;
  }
​
   public void put(int key, int value) {
​
       if (map.containsKey(key)){
       //   老人了
​
           MyNode current = map.get(key);
           current.val=value;
           myLinkedList.deleteAndAddFirst(current);
           map.put(key,current);
      }else {
​
           if (size<capacity){
           //   直接放进来就行
               MyNode temp = new MyNode(key, value);
               myLinkedList.add(temp);
               map.put(key,temp);
               size++;
          }else {
           //   踢人了
​
               MyNode myNode = myLinkedList.removeLast();
               map.remove(myNode.key);
​
           //   再放进
               MyNode temp = new MyNode(key, value);
               myLinkedList.add(temp);
               map.put(key,temp);
               
​
          }
​
​
​
​
​
​
      }
​
​
​
​
  }
}
class MyLinkedList{
   MyNode head;
   MyNode tail;
​
   public MyLinkedList() {
       head=new MyNode(-1,-1);
       tail=new MyNode(-1,-1);
       head.next=tail;
       tail.pre=head;
  }
​
   /**
    * 把之前的放到新的位置
    * @param current
    */
   public void deleteAndAddFirst(MyNode current){
​
       //去除之前的位置
       MyNode next = current.next;
       MyNode pre = current.pre;
​
       pre.next=next;
       next.pre=pre;
       add(current);
​
  }
​
   public void add(MyNode current){
​
       MyNode old = head.next;
       current.next=old;
       head.next=current;
       old.pre=current;
       current.pre=head;
​
​
  }
   public MyNode  removeLast(){
​
       MyNode last = tail.pre;
       MyNode pre= last.pre;
​
       pre.next=tail;
       tail.pre=pre;
       return last;
  }
}
​
class MyNode{
​
   Integer key;
   Integer val;
   MyNode next;
   MyNode pre;
​
   public MyNode(Integer key, Integer val) {
       this.key = key;
       this.val = val;
  }
}

题解