思路分析

LRU(最近最少使用)的设计策略重点在于维护固定格式的缓存，这里用双向链表来维护这些缓存数据，更准确的来说是利用哈希表和双向链表来完成这一设计，哈希表的作用是在O(1)的时间内完成查找，双端链表则是用来保持按使用频率排序的操作,这个题目我们需要理解的是，如果进行了插入和取出，那么就要对缓存的数据进行排序。
因为数据既有key又有value,那么肯定需要使用到HashMap，并且我们如果插入或者取出数据后都要排序，并且set和get的时间复杂度都要是O(1),那么必须使用双向链表来维持缓存数据，因为如果是单向的链表删除数据的时候无法做到O(1)时间复杂度。

  1. class LRUCache {
  3.     /*
  4.     定义一个Node
  6.     */
  7.     class Node{
  8.     int key;
  9.     int value;
  10.     Node next;
  11.        Node pre;
  12.     public Node(int key, int value){
  13.         this.key = key;
  14.         this.value = value;
  15.     }
  17.     }
  19.     //需要定义一个map
  20.     private HashMap<Integer,Node> map;
  21.     //定义缓存容量
  22.     private int capacity;
  24.     //定义头结点
  25.     private Node head;
  26.     //定义尾结点
  27.     private Node tail;
  31.     public LRUCache(int capacity) {
  32.         //对这个cache进行初始化
  33.         map = new HashMap<>();
  34.         this.capacity = capacity;
  35.         head = null;
  36.         tail = null;
  38.     }
  40.     public int get(int key) {
  41.         Node node = map.get(key);
  42.         if(node==null){
  43.         return -1;
  45.         }
  46.         //重新排序
  47.         if(node!=tail){
  48.             if(node==head){
  49.               head = head.next;
  50.             }else{
  51.             node.pre.next = node.next;
  52.             node.next.pre = node.pre;
  54.             }
  56.             tail.next = node;
  57.             node.pre = tail;
  58.             node.next = null;
  59.             tail = node;
  60.         }
  62.         return node.value;
  64.     }
  66.     public void put(int key, int value) {
  67.         Node node = map.get(key);
  68.         if(node!=null){
  69.         node.value = value;
  70.         //重新排序
  71.         if(node!=tail){
  72.             if(node==head){
  73.               head = head.next;
  74.             }else{
  75.             node.pre.next = node.next;
  76.             node.next.pre = node.pre;
  78.             }
  80.             tail.next = node;
  81.             node.pre = tail;
  82.             node.next = null;
  83.             tail = node;
  84.         }
  85.         }else{
  86.             Node newNode = new Node(key, value);
  87.             if(capacity==0){
  88.             Node temp = head;
  89.             head = head.next;
  90.             if(temp==tail){
  91.                 tail = null;
  92.             }
  93.             map.remove(temp.key);
  94.             capacity++;
  95.             }
  97.             if(head==null&&tail==null){
  98.             head = newNode;
  99.             }else{
  100.             tail.next = newNode;
  101.             newNode.pre = tail;
  102.                 newNode.next = null;
  103.             }
  105.             tail = newNode;
  106.             map.put(key,newNode);
  107.             capacity--;
  110.         }
  112.     }
  113. }
  114. /**
  115.  * Your LRUCache object will be instantiated and called as such:
  116.  * LRUCache obj = new LRUCache(capacity);
  117.  * int param_1 = obj.get(key);
  118.  * obj.put(key,value);
  119.  */