146. LRU 缓存

难度：🟡 Medium | 标签：哈希、双向链表、设计 | 状态：⬜ LeetCode 链接

思路

哈希 + 双向链表：

• 双向链表按访问时序：最近用过的在头，最久未用的在尾
• 哈希 key → 链表节点*，O(1) 定位

操作：

• get：哈希查节点，命中则搬到头
• put：已存在则改值 + 搬到头；不存在则插头；超容则删尾

代码

class LRUCache {
    struct Node { int k, v; Node *prev, *next; };
    int cap;
    Node head, tail;        // dummy head & tail
    unordered_map<int, Node*> mp;

    void remove(Node* x) { x->prev->next = x->next; x->next->prev = x->prev; }
    void addFront(Node* x) {
        x->next = head.next; x->prev = &head;
        head.next->prev = x; head.next = x;
    }
public:
    LRUCache(int capacity) : cap(capacity) {
        head.next = &tail; tail.prev = &head;
    }
    int get(int key) {
        auto it = mp.find(key);
        if (it == mp.end()) return -1;
        remove(it->second); addFront(it->second);
        return it->second->v;
    }
    void put(int key, int value) {
        auto it = mp.find(key);
        if (it != mp.end()) {
            it->second->v = value;
            remove(it->second); addFront(it->second);
            return;
        }
        if ((int)mp.size() == cap) {
            Node* lru = tail.prev;
            remove(lru); mp.erase(lru->k); delete lru;
        }
        Node* x = new Node{key, value, nullptr, nullptr};
        addFront(x); mp[key] = x;
    }
};

复杂度

• 时间 O(1) 单次操作
• 空间 O(capacity)

易错 / 回顾

• dummy head / tail 简化边界判断
• put 时已存在记得搬到头
• C++ 也可用 std::list + unordered_map<int, list<>::iterator>，代码更短
• LFU 是另一道题（460），结构更复杂