LRU（Least Recently Used，最近最少使用）缓存是一道非常经典的设计题，同时也是面试中高频出现的问题。它不仅考察数据结构的选择，还考察对时间复杂度和细节的把控。

题目链接–146. LRU 缓存

题目要求设计一个缓存结构，支持 get 和 put 两种操作，并且在容量达到上限时，自动淘汰最近最少使用的元素。所有操作都需要在 O(1) 时间复杂度内完成。

---

一、设计思路

要在 O(1) 时间内完成查询、插入和删除，单一数据结构是无法满足的，因此需要组合使用数据结构。

核心思路

• 哈希表（unordered_map）
  用于通过 key 快速定位缓存中的节点，保证查找是 O(1)。
• 双向链表（Doubly Linked List）
  用于维护数据的访问顺序：
  • 链表头部：最近访问的节点
  • 链表尾部：最久未访问的节点

二者结合后：

• get(key)：
  哈希表定位节点 → 将节点移动到链表头部
• put(key, value)：
  • 若 key 不存在：新建节点，插入头部
  • 若容量超限：删除链表尾部节点
  • 若 key 已存在：更新值，并移动到头部

---

二、数据结构定义

双向链表节点

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

每个节点同时保存 key 和 value，这样在淘汰节点时可以直接通过 key 从哈希表中删除对应项。

---

三、LRUCache 类设计

class LRUCache {
private:
    unordered_map<int,DLinkedNode*> cache;
    DLinkedNode* head;
    DLinkedNode* tail;
    int capacity;
    int size;

• cache：key 到链表节点的映射
• head / tail：哨兵节点，避免处理空指针边界情况
• capacity：缓存容量
• size：当前缓存大小

---

四、初始化

public:
    LRUCache(int _capacity):capacity(_capacity),size(0) {
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head -> next = tail;
        tail -> prev = head; 
    }

使用 虚拟头节点和尾节点，可以让链表插入和删除逻辑更加统一，减少边界判断。

---

五、get 操作

int get(int key) {
    if(!cache.count(key)){
        return -1;
    }
    DLinkedNode* node = cache[key];
    moveToHead(node);
    return node -> value;
}

逻辑说明：

• 若 key 不存在，直接返回 -1
• 若存在：
  • 将该节点移动到链表头部（表示最近使用）
  • 返回对应的 value

---

六、put 操作

void put(int key, int value) {
    if(!cache.count(key)){
        DLinkedNode* node = new DLinkedNode(key,value);
        cache[key] = node;
        addToHead(node);
        size++;
        if(size > capacity){
            DLinkedNode* removed = removeTail();
            cache.erase(removed -> key);
            delete removed;
            size--;
        }
    }
    else{
        DLinkedNode* node = cache[key];
        node -> value = value;
        moveToHead(node); 
    }
}

分两种情况：

1️⃣ key 不存在

• 创建新节点
• 插入链表头部
• 容量超限时，删除链表尾部节点（最久未使用）

2️⃣ key 已存在

• 更新 value
• 将节点移动到头部

---

七、链表辅助操作函数

删除节点

void removeNode(DLinkedNode* node){
    node -> next -> prev = node -> prev;
    node -> prev -> next = node -> next;
}

---

插入到头部

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

---

移动到头部

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

---

删除尾部节点（LRU）

DLinkedNode* removeTail(){
    DLinkedNode* node = tail -> prev;
    removeNode(node);
    return node;
}

---

八、完整代码

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

class LRUCache {
private:
    unordered_map<int,DLinkedNode*>cache;
    DLinkedNode* head;
    DLinkedNode* tail;
    int capacity;
    int size;


public:
    LRUCache(int _capacity):capacity(_capacity),size(0) {
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head -> next = tail;
        tail -> prev = head; 
    }
    
    int get(int key) {
        if(!cache.count(key)){
            return -1;
        }
        DLinkedNode* node = cache[key];
        moveToHead(node);
        return node -> value;
    }
    
    void put(int key, int value) {
        if(!cache.count(key)){
            DLinkedNode* node = new DLinkedNode(key,value);
            cache[key] = node;
            addToHead(node);
            size++;
            if(size > capacity){
                DLinkedNode* removed = removeTail();
                cache.erase(removed -> key);
                delete removed;
                size--;
            }
        }
        else{
            DLinkedNode* node = cache[key];
            node -> value = value;
            moveToHead(node); 
        }
        
    }
    void removeNode(DLinkedNode* node){
        node -> next -> prev = node -> prev;
        node -> prev -> next = node -> next;
    }

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

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

    DLinkedNode* removeTail(){
        DLinkedNode* node = tail -> prev;
        removeNode(node);
        return node;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */