Contribute one c/c++ version (home cooked doubly linked list+map)


  • 0
    2
    struct Node {
        struct Node *prev, *next;
        int key, val;
        Node(int k, int v) { key=k; val=v; prev=next=NULL; }
    };
    
    class LRUCache{
        int capacity, size;
        Node *head, *tail;
        map<int, Node *> m;
    
        void input(Node *n) {
            if(head) {
                n->next=head; n->prev=NULL; head->prev=n; head=n;
            } else {
                tail=n; head=n;
            }
        }
    
        void removeTail() {
            if(tail->prev) {
                tail=tail->prev; delete tail->next; tail->next=NULL;
            } else {
                delete head; head=NULL; tail=NULL;
            }
        }
    
        void moveToHead(Node * n) {
            if(n==head) return;
            else if(n==tail) {
                tail=tail->prev; tail->next=NULL; n->next=head; head->prev=n; head=n;
            } else {
                n->prev->next=n->next; n->next->prev=n->prev; n->next=head; head->prev=n; head=n;
            }
        }
    public:
        LRUCache(int capacity) {
            this->capacity=capacity;
            size=0;
            head=tail=NULL;
        }
    
        int get(int key) {
            if(!m.count(key)) {
            	return -1;
            }
            Node * n= m[key];
            moveToHead(n);
            return m[key]->val;
        }
    
        void set(int key, int value) {
            if(m.count(key)) {
                Node * n= m[key];
                moveToHead(n);
                n->val=value;
                return;
            }
            if(size==capacity) {
                m.erase(tail->key);
                removeTail();
                size--;
            }
            Node * n= new Node(key, value);
            input(n);
            m[key]=n;
            size++;
        }
    };
    

Log in to reply
 

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