• 分析
  LeetCode 146就是实现一个LRU算法，LRU算法的原理不再记录。LRU算法的实现的核心数据结构是哈希链表，就是双向链表和哈希表的结合体。LRU算法需要满足下面3个条件。1）cache中的元素必须是有时序的，以区分最近使用的和久未使用的数据，当容量满之后要删除最久未使用的那个元素腾出位置 ；2）我们要在cache中快速找某个key是否存在并得到value；3） 每次访问cache中的某个key，需要将这个元素变为最近使用的，也就是说cache要支持在任意位置快速插入和删除元素。哈希链表可以满足各种要求。需要思考的是为什么使用双向链表？为什么在哈希表中存了key还要在链表中存储？这两个问题在代码注释中进行了解释。
• 代码

class node{
public:
    int key,val;
    node* prev;
    node* next;
    node(int key, int val) : key(key), val(val), prev(nullptr), next(nullptr){}
};

class List{
private:
    node* head;
    node* tail;
    int size;
public:
    List(){
        head = new node(0, 0);
        tail = new node(0, 0);
        head -> next = tail;
        tail -> prev = head;
        size = 0;
    }        

    //在链表尾部添加节点x
    void addNode(node* x){
        x -> prev = tail -> prev;
        x -> next = tail;
        tail -> prev -> next = x;
        tail -> prev = x;
        size++;
    }

    //删除链表中的x节点（x一定存在）
    void delNode(node* x){//因为要删除结点，所以需要使用双链表，已达到节省时间的目的
        x -> prev -> next = x -> next;
        x -> next -> prev = x -> prev;
        size--;
    }

    //删除链表中的第一个节点，并返回该节点，时间复杂度O（1）
    node* removeFirst(){
        if(head -> next == tail) return nullptr;

        node* temp = head -> next;
        delNode(temp);
        return temp;
    }

    int getsize(){ 
        return this -> size; 
    }
};

class LRUCache {
private:
    unordered_map<int, node*> map;
    List cache;
    int cap;    
public:
    LRUCache(int capacity) {
        cap = capacity;
    }
    
    int get(int key) {
        
        if(map.find(key) == map.end()) return -1;
        makeRecently(key);
        return map[key] -> val;        
    }
    
    void put(int key, int value) {
        if(map.find(key) != map.end()){
        //key已存在
            delKey(key);
            addRecently(key, value);
            return;
        }

        if(cap == cache.getsize()){
            //删除最久未使用的元素
            removeLeastRecently();
        }
        addRecently(key, value);
    }
    //将某个key提升为最近使用
    void makeRecently(int key){
        node* x = map[key];
        cache.delNode(x);
        cache.addNode(x);
    }

    //添加最近使用的元素
    void addRecently(int key, int val){
        node* x = new node(key, val);

        cache.addNode(x);
        map[key] = x;
    }

    //删除某一个key
    void delKey(int key){
        node* x = map[key];

        cache.delNode(x);
        map.erase(key);
    }

    //删除最久未使用的元素
    void removeLeastRecently(){
    //链表头部的第一个元素就是最久未使用的
        node* x = cache.removeFirst();
        int deleteKey = x -> key;

    //就是因为要删除map中的key，所以才必须在双链表中同时存储key和val
        map.erase(deleteKey);
    }
};