[数据结构与算法]C++实现LRU算法

#include<stdio.h>
#include<map>
#include<unordered_map>
using namespace std;

struct DLinkedNode {
    int key;
    int value;
    DLinkedNode* pre;
    DLinkedNode* next;
    DLinkedNode() :key(0), value(0), pre(nullptr), next(nullptr) {};
    DLinkedNode(int _key, int _value) :key(_key), value(_value), pre(nullptr), next(nullptr) {};
};

class LRUCache
{
private:
    unordered_map<int, DLinkedNode*> cache;
    DLinkedNode* head;
    DLinkedNode* tail;
    int size;
    int capacity;
public:
    LRUCache(int _capacity)
    {
        capacity = _capacity;
        size = 0;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->pre = head;
    }
    int get(int key)
    {
        //key不存在则返回-1；存在则将节点移至最前
        if (!cache.count(key))
            return -1;
        else
            MoveToHead(cache[key]);
        return cache[key]->value;
    }
    void put(int key, int value)
    {
        //key存在则变更为要替换的值，并将节点移至最前
        if (cache.count(key))
        {
            cache[key]->value = value;
            MoveToHead(cache[key]);
        }
        //key不存在，则在头节点后添加新节点
        else
        {
            DLinkedNode* node = new DLinkedNode(key, value);
            cache[key] = node;
            addHead(node);
            size++;
            //如果超出容量则删除最后一个节点
            if (size > capacity)
            {
                //因为是new出来的对象，所以要先记录节点，然后再释放掉
                DLinkedNode* removed = RemoveLast();
                cache.erase(removed->key);
                delete removed;
                size--;
            }
        }
    }
    //删除节点
    void removeNode(DLinkedNode* node)
    {
        node->pre->next = node->next;
        node->next->pre = node->pre;
    }
    //添加头节点
    void addHead(DLinkedNode* node)
    {
        head->next->pre = node;
        node->next = head->next;
        head->next = node;
        node->pre = head;
    }
    //节点移至最前
    void MoveToHead(DLinkedNode* node)
    {
        removeNode(node);
        addHead(node);
    }
    //删除最后一个节点
    DLinkedNode* RemoveLast()
    {
        DLinkedNode* node = tail->pre;
        removeNode(node);
        return node;
    }
};

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖