算法描述

LRU实际上是设计一个数据结构，有如下要求：

• 包含容量capacity和当前元素数量size
• 包含插入方法put和获取get
• 时间复杂度为O(1);

算法设计

一般来说通过两个数据结构来实现LRU机制，即

• 哈希表：用于存取【鍵-节点】对
• 双向链表：用于存取【键-值】对，尾节点为最新加入的节点，头节点的后一结点为LRU节点

struct Node{
    int key,value;
    Node *pre,*next;
    Node(int _k,int _v):
        key(_k),value(_v),pre(nullptr),next(nullptr){}
};
class LRUCache {
    const int MAXSIZE=3001;
    Node* head;				
    Node* tail;				/* for tail insertion method */
    vector<Node*> cache_;
    int capacity;
    int size;
public:
    LRUCache(int c):
        size(0),capacity(c) {
            head=new Node(-1,-1);
            tail=head;
            cache_.resize(MAXSIZE,nullptr);
    }
    
    int get(int key) {
        if(cache_[key]==nullptr){
            /* not existed */
            return -1;
        }else{
            /* existed */
            Node* cur=cache_[key];
            /* if cur is tail, ignore update*/
            if(cur!=tail){
                /* release from original position */
                cur->pre->next=cur->next;
                cur->next->pre=cur->pre;
                /* update position to tail */
                tail->next=cur;
                cur->pre=tail;
                cur->next=nullptr;
                tail=cur;
            }
            return cur->value;
        }
    }
    
    void put(int key, int value) {
        if(get(key)==-1){
            /* existed */
            if(size<capacity){
                size++;
            }else{
                /* delete the head->next node */
                Node *popNode=head->next;
                if(popNode==tail){
                    tail->next=nullptr;
                    tail->pre=nullptr;
                    head->next=nullptr;
                    tail=head;
                }else{
                    head->next=popNode->next;
                    popNode->next->pre=head;
                }
                popNode->next=nullptr;
                popNode->pre=nullptr;
                /* important! remove it from cache */
                cache_[popNode->key]=nullptr;
                delete popNode;
            }
            /* create new node (tail insertion)*/
            Node *newNode=new Node(key,value);
            cache_[key]=newNode;
            tail->next=newNode;
            newNode->pre=tail;
            tail=newNode;
        }else{
            cache_[key]->value=value;
        }
    }
};