面试经典150题 P146 LRU缓存

---

时间轴

2025-11-23

init

---

题目：

P146 LRU缓存

https://leetcode.cn/problems/lru-cache/description/?envType=study-plan-v2&envId=top-interview-150

最好是把最近访问的结点加入头部，毕竟删除尾部结点只需要两次指针修改。

#include <unordered_map>

using std::unordered_map;

typedef struct CacheNode {
	int key, val;
	struct CacheNode *prev, *next;
} CacheNode;

class LRUCache {
    private:
	unordered_map<int, CacheNode *> key2val;
	CacheNode *head, *tail;
	int size;
	int capacity;
	void move_to_tail(CacheNode *node)
	{
		node->prev->next = node->next;
		node->next->prev = node->prev;
		node->next = tail;
		node->prev = tail->prev;
		tail->prev = node;
		node->prev->next = node;
	}

    public:
	LRUCache(int capacity)
	{
		this->capacity = capacity;
		this->size = 0;
		head = new CacheNode;
		tail = new CacheNode;
		head->next = tail;
		head->prev = nullptr;
		tail->prev = head;
		tail->next = nullptr;
	}

	int get(int key)
	{
		if (key2val.count(key)) {
			CacheNode *node = key2val[key];
			move_to_tail(node);
			return node->val;
		} else {
			return -1;
		}
	}

	void put(int key, int value)
	{
		CacheNode *node;
		if (key2val.count(key)) {
			node = key2val[key];
			node->val = value;
			move_to_tail(node);
		} else {
			node = new CacheNode;
			node->key = key;
			node->val = value;
		  
			node->next = tail;
			node->prev = tail->prev;
			tail->prev->next = node;
			tail->prev = node;
		  
			key2val[key] = node;
			size++;
			if (size > capacity) {
				node = head->next;
				head->next = node->next;
				node->next->prev = head;
				key2val.erase(node->key);
				delete 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);
 */