I just wonder whether singly linked list is a wrong choice...


  • 0
    L
    class LRUCache{
    
        class CacheNode {
            public:
                int key;
                int val;
                CacheNode* next;
                CacheNode(int k, int v):key(k), val(v), next(nullptr) {
                }
        };
        
        public:
            LRUCache(int capacity):n(capacity), dummy(0, 0) {
                head = tail = &dummy; 
            }
            
            int get(int key) {
                if (dict.find(key) == dict.end())
                    return -1;
                if (dict[key]->next != tail) {
                    tail->next = dict[key]->next;
                    dict[dict[key]->next->next->key] = dict[key];
                    dict[key]->next = dict[key]->next->next;
                    dict[key] = tail;
                    tail = tail->next;
                    tail->next = nullptr;
                }
                return tail->val;
            }
            
            void set(int key, int value) {
                if (dict.find(key) == dict.end()) {
                    tail->next = new CacheNode(key, value);
                    dict[key] = tail;
                    tail = tail->next;
                    if (n != 0)
                        n--;
                    else {
                        CacheNode *tmp = head->next;
                        head->next = head->next->next;
                        dict[tmp->next->key] = head;
                        dict.erase(tmp->key);
                        delete tmp;
                    }
                } else {
                    if (dict[key]->next != tail) {
                        tail->next = dict[key]->next;
                        dict[dict[key]->next->next->key] = dict[key];
                        dict[key]->next = dict[key]->next->next;
                        dict[key] = tail;
                        tail = tail->next;
                        tail->next = nullptr;
                    }
                    tail->val = value;
                }
            }
        private:
            int n;
            CacheNode *head, *tail;
            CacheNode dummy;
            unordered_map<int, CacheNode*> dict;
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.