Classic Interview 150 Questions P146 LRU Cache

---

Timeline

Timeline

2025-11-23

init

linked list

---

Problem:

P146 LRUCache

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

It is best to move the most recently accessed node to the head, since deleting the tail node only requires two pointer modifications.

#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);
 */

leetcode hot 100 rewrite

#include <unordered_map>
using std::unordered_map;

struct MyListNode {
        int key;
        int val;
        struct MyListNode *next;
        struct MyListNode *prev;
};

class LRUCache {
    private:
        int capacity;
        int size;
        unordered_map<int, MyListNode *> umap; // key -> MyListNode(store value)
        MyListNode *virtual_head;
        MyListNode *virtual_tail;

        void move_to_head(MyListNode *p)
        {
                MyListNode *prev = p->prev;
                prev->next = p->next;
                p->next->prev = prev;

                MyListNode *next = virtual_head->next;
                virtual_head->next = p;
                p->next = next;
                next->prev = p;
                p->prev = virtual_head;
        }

    public:
        LRUCache(int capacity)
        {
                this->capacity = capacity;
                this->size = 0;

                // Doubly circular linked list
                virtual_head = new MyListNode;
                virtual_tail = new MyListNode;

                virtual_head->next = virtual_tail;
                virtual_head->prev = virtual_tail;
                virtual_tail->prev = virtual_head;
                virtual_tail->next = virtual_head;
        }

        int get(int key)
        {
                if (!umap.count(key))
                        return -1;
                MyListNode *p = umap[key];
                move_to_head(p);
                return p->val;
        }

        void put(int key, int value)
        {
                if (umap.count(key)) { // Already exists
                        MyListNode *p = umap[key];
                        p->val = value;
                        move_to_head(p);
                        return;
                }

                MyListNode *p = new MyListNode;
                p->val = value;
                p->key = key;

                MyListNode *q = virtual_head->next;
                // insert
                virtual_head->next = p;
                p->next = q;
                q->prev = p;
                p->prev = virtual_head;
                umap[key] = p;
                size++;

                if (size > capacity) { // remove the last one
                        q = virtual_tail->prev;
                        p = q->prev;
                        p->next = virtual_tail;
                        virtual_tail->prev = p;
                        umap.erase(q->key);
                        delete q;
                }
        }
};

/**
 * 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);
 */