Leetcode linked list queue stack problem

Double linked list

146. LRU cache

• LRUCache(int capacity) With Positive integer As capacity capacity initialization LRU cache
• int get(int key) If the keyword key In the cache , The value of the keyword is returned , Otherwise return to -1 .
• void put(int key, int value) If the keyword key Already exist , Change its data value value ; If it doesn't exist , Then insert the group into the cache key-value . If the insert operation causes the number of keywords to exceed capacity , Should be Eviction The longest unused keyword .
• function get and put Must be O(1) The average time complexity of running .Link

• Realize the idea
• get function
  • Hash map not found ： return -1
  • Hash map found ： Delete this node from the linked list 、 Move this node to the head of the linked list 、 Returns the value of the node
• put function
  • Hash map not found ：
    • The cache is full ： Delete the end node of the linked list , Create a new node , Insert the head of the linked list , Update hash map
    • Cache not full ： Create a new node , Insert the head of the linked list , Update hash map
      • Merge ： When the cache is full, delete the end of the linked list node , Then create a new one and insert it into the head , Update hash map
  • Hash map found ： Move the node to the head , Update the value value

---

• Bidirectional linked list is used for caching , Hash mapping is used to find
• Borrow existing list Container and iterator realize the function of bidirectional linked list
  • list The underlying time of is based on a two-way linked list
  • Delete the keywords in the cache 、 Insert keyword into header ; Keyword advance is realized
  • After cache operation, pay attention to Update hash map

class LRUCache {
    
public:
    LRUCache(int capacity) : cap(capacity){
    

    }
    
    int get(int key) {
    
        if (hashtable.find(key) == hashtable.end()) return -1;
        auto key_value = *hashtable[key]; // * iterator,  Take out list The pair in  pair  Value 
        //  Delete the cache first , Then insert into  list  The first , Implement recently used 
        cache.erase(hashtable[key]);
        cache.push_front(key_value);
        hashtable[key] = cache.begin(); //  Update hash map 
        return key_value.second;
    }
    
    void put(int key, int value) {
    
        //  If the keyword is not in the cache 
        if (hashtable.find(key) == hashtable.end()) {
    
            if (hashtable.size() == cap) {
     //  If the cache is full 
                //  Delete the last cache , Clear its hash map 
                hashtable.erase(cache.back().first);
                cache.pop_back();
            }
        }else {
    
            cache.erase(hashtable[key]); //  Keywords in cache 
        }
        cache.push_front({
    key, value}); //  Add keywords to the cache header , And update the hash map 
        hashtable[key] = cache.begin();
    }
private:
    int cap;
    list<pair<int,int>> cache;
    unordered_map<int, list<pair<int,int>>::iterator> hashtable;
};

---

• Manual implementation of two-way linked list

• Established key、 Mapping of node pointers , Therefore, the hash map does not need to be updated after the node is moved

• First remove the node from the linked list 、 Then move to the head of the linked list

• Remove nodes from the linked list node
  

• The nodes node Move to the head of the list
  

class LRUCache {
    
public:
    struct DLinkNode {
    
        int key, value;
        DLinkNode *prev, *next;
        DLinkNode (){
    };
        DLinkNode(int _key, int _value) : key(_key), value(_value), prev(nullptr), next(nullptr) {
    };
    };
    LRUCache(int capacity) : cap(capacity){
    
        //  Create header 、 The last two nodes are easy to find 
        head = new DLinkNode(-1, -1);
        tail = new DLinkNode(-1, -1);
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
    
        if (hash.find(key) == hash.end()) return -1;
        DLinkNode* node = hash[key];
        //  Remove this node from its original location , Then move to the head 
        removeNode(node); //  It's very important 
        moveHead(node);
        return node->value;
    }
    
    void put(int key, int value) {
    
        if (hash.find(key) == hash.end()) {
    
            if (hash.size() == cap) {
    
                DLinkNode *node = removeTail();
                //  Delete last node , And clear the hash map 
                hash.erase(node->key);
                delete node;
            }
            //  Add nodes and create hash maps 
            addHead(key, value);
            hash[key] = head->next;
        }else {
    
            DLinkNode* node = hash[key];
            node->value = value;
            //  Delete this node from its original position and move it to the head 
            removeNode(node);
            moveHead(node);
        }
    }

    void moveHead(DLinkNode* node) {
    
        DLinkNode *nextNode;
        nextNode = head->next;
        //  Insert the current node into  head  and  head  In the middle of the next node of , Head 
        node->prev = head;
        node->next = nextNode;
        nextNode->prev = node;
        head->next = node;
    }

    void addHead(int key, int value) {
    
        //  Create a new node , And move it to the head of the linked list 
        DLinkNode *node = new DLinkNode(key, value);
        moveHead(node);
    }

    void removeNode(DLinkNode* node) {
    
        //  Remove the current node from the linked list 
        DLinkNode *prevN = node->prev;
        DLinkNode *nextN = node->next;
        prevN->next = nextN;
        nextN->prev = prevN;
    }

    DLinkNode* removeTail() {
    
        DLinkNode* node = tail->prev; //  The tail node of the linked list 
        removeNode(node); //  Remove this node from the linked list 
        return node; //  return 
    }
private:
    int cap;
    DLinkNode *head;
    DLinkNode *tail;
    unordered_map<int, DLinkNode*> hash;
};