1、刚写入的元素，是最有可能被马上读出的，拿注册举例来说，有一个网站，注册完，紧接着下一步的动作就应该是登录，注册是一个写入的行为，登录是从数据库读取校验的过程，立刻写入，立刻读出的过程，LRU就是基于这样的思想，刚写入的数据是有一个热度的概念，热度是最高的，热度低的数据就是很久没有被访问过，如果数据刚被写入，或者刚被访问过，那么这个数据的热度就很高。
我们将真实数据的data结点放在双向链表中，设置虚结点head和tail不存元素，只是为了方便表达。
2、如何表达记录一个数据的热度？什么时候链表结点会被删除？
1）当data数据结点刚被访问过，它的热度是最高的，需要删除它在原本的位置，将此data结点移动到head的下一个结点。我们时刻维护head的next是热度最高的结点，那么当新的data数据来临的时候，我们也是需要将它插入到head后面的。
2）链表的长度已经到达规定容量capacity，那么需要淘汰热度最低的结点，也就是需要删除链表的tail结点前面的一个结点。我们时刻维护tail的前一个结点就是热度最低的结点。
3、我们会进行的操作，读取(不会触发淘汰机制)，新来结点（可能触发淘汰机制）
读取：从plist中获取data结点，将data从plist中删除，把data结点插入到plist的头部结点后面，返回plist中的data结点存储的value。
插入：如果链表长度没有超过容量，直接插入头部，链表长度超过容量，先删除尾部tail的前一个结点，然后将新的data结点插入到head结点的后面。
现在的问题就在于我们如何确认到我们需要的value在哪个data节点中。我们需要定位data结点。借助hashmap，hash的key就是data结点的key，对应的hash值就是data结点的地址。
4、时间复杂度计算
双向链表的插入和删除是在O（1）时间复杂度之内完成的，因为我们已经知道了插入和删除的具体位置。hashmap的查找时间复杂度也是O（1），所以整个算法的时间复杂度就是O(1)。
5、代码实现
class LRUCache{
public:
struct Node{
int key,val;
Node* pre;
Node* next;
Node (int k,int v){
key = k;
val = v;
pre = next = nullptr;
}
};
Node * head;
Node * tail;
int C;
unordered_maphashmap; //key data地址
LRUCache(int Capacity){
C = Capacity;
head = new Node(-1,-1);
tail = new Node(-1,-1);
head->next = tail; //空的LRU 头尾先连接起来
tail->pre = head;
}
int get(int key){
if(!hashmap.count(key)) return -1;
Node* ptr = hashmap[key];
remove(ptr);
insert(ptr);
return ptr->val;
}
void put(int key,int value){
if(!hashmap.count(key)){
//insert逻辑 增加结点
if(hashmap.size() == C){
//淘汰热度最低的结点
Node* ptr = tail->pre;//尾巴的 pre不可能是 head 因为 Capacity至少是1，hashmap中至少存在一个真正的key。
remove(ptr);
hashmap.erase(ptr->key);
delete ptr;
}
Node*ptr = new Node(key,value);
hashmap[ptr->key] = ptr;
insert(ptr);
return;
}
//存在的话就是一个更新操作
Node *ptr = hashmap[key];
ptr->val = value;
remove(ptr);
insert(ptr);
}
void remove(Node*ptr){
Node *a = ptr->pre;
Node *b = ptr->next;
a->next = b;
b->pre = a;
ptr->pre = ptr->next = nullptr;
}
void insert(Node*ptr){ //将一个结点插入到双向链表的头部（head-》next）
Node* a = head->next;
a->pre = ptr;
ptr->next = a;
ptr->pre = head;
head->next = ptr;
}
};
