算法-146. LRU缓存机制

题目：LRU缓存机制

1. 题目描述

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get 和写入数据 put 。

获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

2. 解题：双链表+HashMap

新建链表类存储节点的访问顺序，使用HashMap存储包含的关键字。

插入操作
插入操作判断容量是否超限或者已经包含有关键字，如果包含关键字则直接设置value为输入值，获取关键字节点，将节点移至链表的尾端。如果插入插入的key不存在：1. 容量未超限或容量为空，新建节点放置到链表的尾端，且将(key, Node)放置到HashMap中；2.容量已经达到最大值，从双链表中取下头结点，从HashMap中移除头结点的key，利用取下节点设置新节点的key, value。插入到双链表的尾部，且放入hashMap。

查询操作
查询操作，如果HashMap中不存在查询的key则直接返回-1。如果存在查询的key，则将与之对应的双链表节点取下，放置到双链表的尾部，返回对应的value。
具体代码如下：

class LRUCache {

 static class Node{
     int value, key;
     Node next;
     Node pre;
     public Node(int key, int value){
         this.key = key;
         this.value = value;
     }
 }
 Node head;
 Node tail;
 int capacity;
 int size;

 HashMap<Integer, Node> map = new HashMap<>();
 public LRUCache(int capacity) {
     this.capacity = capacity;
 }

 public int get(int key) {
     if (map.containsKey(key)) {
         Node node = map.get(key);
         reconnect(node);
         return node.value;
     }
     return -1;
 }

 public void put(int key, int value) {
     if(map.containsKey(key)){
         Node node = map.get(key);
         node.value = value;
         reconnect(node);
     }else{
         Node node = null;
         if(size == capacity){
             node  = head;
             map.remove(node.key);
             node.value = value;
             node.key = key;
             if(capacity > 1){
                 head = head.next;
                 head.pre = null;
                 node.pre = tail;
                 tail.next = node;
                 tail = node;
                 node.next = null;
             }
             map.put(key, node);                
         }else{
             if(size == 0){
                 node = new Node(key, value);
                 head = node;
                 tail= node;
             }else{
                 node = new Node(key, value);
                 node.pre = tail;
                 tail.next = node;
                 tail = node;
             }
             ++size;
         }
         map.put(key, node);
     }
 }

 private void reconnect(Node node){
     if(node == head && size != 1){
         head = head.next;
         node.next = null;
         head.pre = null;
         tail.next = node;
         node.pre = tail;
         tail = node;
     }else if(node != tail && size != 1){
         Node temp = node.next;
         node.pre.next = temp;
         temp.pre = node.pre;
         node.next = null;
         tail.next = node;
         node.pre = tail;
         tail = node;
     }
 }
}