C++ double linked list, very good for beginner


  • 0
    B

    in this code, we use an hashMap to store the node address for fast accessing

    the LRU order is stored in a double linked list, the access, move, and delete operation are all O(1).

    The operation on linked list pointers are good example for beginner who just started to learn data structure.

    class LRUCache{
    public:
        struct Node
        {
            int val;
            int key;
            Node * prev;
            Node * next;
            Node( int k, int v):key(k), val(v), prev(NULL), next(NULL){};
        };
        
        unordered_map<int,Node*>mp;
        Node* head;
        Node* end;
        int cap;
        
        //for debug
        void print()
        {
            Node * temp = head;
            cout << "from head to end: ";
            while(temp)
            {
                cout << temp -> key << " ";
                temp = temp -> next;
            }
            cout << endl << "from end to head: ";
            temp = end;
            while(temp)
            {
                cout << temp -> key << " ";
                temp = temp -> prev;
            }
            cout << endl;
        }
        
        LRUCache(int capacity) 
        {
            cap = capacity;
            head = new Node(0,0);
            end = new Node(0,0);
            head -> next = end;
            end -> prev = head;
        }
        
        int get(int key) 
        {
            if(mp.find(key)==mp.end()) return -1;
            Node * temp = mp[key];
            //remove temp from original position
            temp -> prev -> next = temp -> next;
            temp -> next -> prev = temp -> prev;
            //move temp to the end
            end -> prev -> next = temp;
            temp -> prev = end -> prev;
            temp -> next = end;
            end -> prev = temp;
            return temp -> val;
        }
        
        void set(int key, int value) 
        {
            if(mp.find(key)==mp.end())
            {
                //create new node
                Node * temp = new Node(key,value);
                //insert to map
                mp [key] = temp;
                //insert to list
                temp -> prev = end -> prev;
                temp -> prev -> next = temp;
                temp -> next = end;
                end -> prev = temp;
                //check size
                while(mp.size()>cap)
                {
                    temp = head -> next;
                    head -> next = temp -> next;
                    temp -> next -> prev = head;
                    mp.erase(temp->key);
                    delete temp;
                }
            }
            else
            {
                mp[key]->val = value;
                get(key);
            }
        }
    };

Log in to reply
 

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