LRU（Least Recently Used）算法是一种常用的缓存淘汰算法，用于确定在缓存中删除哪个元素。LRU算法的基本思想是，当缓存已满时，优先删除最近最少使用的元素。

LRU算法的具体实现方式可以使用哈希表和双向链表结合的数据结构来实现。哈希表用于快速查找元素，双向链表用于记录元素的访问顺序。

当元素被访问时，如果元素已经在缓存中，则将该元素移到链表的头部，表示该元素是最近使用的。如果元素不在缓存中，则将元素加入到缓存中，并将其放置在链表的头部。如果缓存已满，则删除链表尾部的元素，同时从哈希表中删除该元素的索引。

LRU算法的优点是可以很好地利用局部性原理，即最近被访问的元素可能在将来被再次访问。因此，LRU算法通常能够提供较好的缓存命中率。

LRU算法步骤如下：

1. 当访问一个元素时，如果该元素已经在缓存中，则将其移到链表的头部。
2. 如果该元素不在缓存中，将其加入缓存，并将其放置在链表的头部。
3. 如果缓存已满，删除链表尾部的元素，并从哈希表中删除该元素的索引。

基于双向链表和哈希表的简单实现

cpp
#include <iostream>
#include <unordered_map>
using namespace std;

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

class LRUCache {
private:
    unordered_map<int, Node*> cache;
    Node* head;
    Node* tail;
    int capacity;
    int size;
    
public:
    LRUCache(int cap) : capacity(cap), size(0) {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->prev = head;
    }
    
    ~LRUCache() {
        while (head) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }
    
    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;
    }
    
    void moveToHead(Node* node) {
        removeNode(node);
        addToHead(node);
    }
    
    Node* removeTail() {
        Node* node = tail->prev;
        removeNode(node);
        return node;
    }
    
    int get(int key) {
        if (cache.find(key) != cache.end()) {
            Node* node = cache[key];
            moveToHead(node);
            return node->value;
        }
        return -1;
    }
    
    void put(int key, int value) {
        if (cache.find(key) != cache.end()) {
            Node* node = cache[key];
            node->value = value;
            moveToHead(node);
        } else {
            Node* newNode = new Node(key, value);
            cache[key] = newNode;
            addToHead(newNode);
            size++;
            if (size > capacity) {
                Node* removedNode = removeTail();
                cache.erase(removedNode->key);
                delete removedNode;
                size--;
            }
        }
    }
};

int main() {
    
    LRUCache cache(2);
    
    
    cache.put(1, 1);
    cache.put(2, 2);
    
    cout << cache.get(1) << endl;  // 输出 1
    
    
    cache.put(3, 3);
    
   
    cout << cache.get(2) << endl;  // 输出 -1
    
    
    cout << cache.get(3) << endl;  // 输出 3
    
    
    cache.put(4, 4);
    
   
    cout << cache.get(1) << endl;  // 输出 -1
    
    
    cout << cache.get(3) << endl;  // 输出 3
    
    
    cout << cache.get(4) << endl;  // 输出 4
    
    return 0;
}