C++实现LRU缓存算法详解

struct Node {
    int key, value;
    Node* prev;
    Node* next;
    Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};

void removeNode(Node* node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
}
void addToHead(Node* node) {
node->prev = head;
node->next = head->next;
head->next->prev = node;
head->next = node;
}

#include <unordered_map>
using namespace std;
class LRUCache {
private:
struct Node {
int key, value;
Node prev;
Node next;
Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
int capacity;
unordered_map&lt;int, Node*&gt; cache;
Node* head;
Node* tail;

void removeNode(Node* node) {
    node-&gt;prev-&gt;next = node-&gt;next;
    node-&gt;next-&gt;prev = node-&gt;prev;
}

void addToHead(Node* node) {
    node-&gt;prev = head;
    node-&gt;next = head-&gt;next;
    head-&gt;next-&gt;prev = node;
    head-&gt;next = node;
}

void moveToHead(Node* node) {
    removeNode(node);
    addToHead(node);
}

Node* removeTail() {
    Node* node = tail-&gt;prev;
    removeNode(node);
    return node;
}
public:
LRUCache(int cap) : capacity(cap), size(0) {
head = new Node(0, 0);
tail = new Node(0, 0);
head->next = tail;
tail->prev = head;
}
int get(int key) {
    auto it = cache.find(key);
    if (it == cache.end()) return -1;
    Node* node = it-&gt;second;
    moveToHead(node);
    return node-&gt;value;
}

void put(int key, int value) {
    auto it = cache.find(key);
    if (it != cache.end()) {
        Node* node = it-&gt;second;
        node-&gt;value = value;
        moveToHead(node);
    } else {
        Node* newNode = new Node(key, value);
        cache[key] = newNode;
        addToHead(newNode);

        if (cache.size() &gt; capacity) {
            Node* removed = removeTail();
            cache.erase(removed-&gt;key);
            delete removed;
        }
    }
}

~LRUCache() {
    Node* curr = head;
    while (curr) {
        Node* temp = curr;
        curr = curr-&gt;next;
        delete temp;
    }
}
};