1. Title

Design and implement an LRU (least recently used) caching mechanism with your data structure.
Implement the LRUCache class:

• LRUCache(int capacity) initializes the LRU cache with a positive integer as the capacity
• int get(int key) if the key exists in the cache, the value of the key is returned, otherwise - 1 is returned.
• void put(int key, int value) if the keyword already exists, change its data value; If the keyword does not exist, insert the group keyword value. When the cache capacity reaches the maximum, it should delete the longest unused data value before writing new data, so as to make room for new data values.

Advanced: can you perform these two operations in O(1) time complexity?

Example:

input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
output
[null, null, null, 1, null, -1, null, -1, 3, 4]

explain
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // The cache is {1 = 1}
lRUCache.put(2, 2); // The cache is {1 = 1, 2 = 2}
lRUCache.get(1);    // Return to 1
lRUCache.put(3, 3); // This operation will void keyword 2 and cache {1 = 1, 3 = 3}
lRUCache.get(2);    // Return - 1 (not found)
lRUCache.put(4, 4); // This operation will void keyword 1 and cache {4 = 4, 3 = 3}
lRUCache.get(1);    // Return - 1 (not found)
lRUCache.get(3);    // Return to 3
lRUCache.get(4);    // Back to 4

Tips:

• 1 <= capacity <= 3000
• 0 <= key <= 3000
• 0 <= value <= 104
• Call 3 * 104 get and put at most

2. Ideas

(double linked list + hash) O ( 1 ) O(1) O(1)
Use a double linked list and a hash table:

• The double linked list stores the time stamp of a node being used (get or put), which is sorted from left to right according to the latest use time. The first used node is placed in the first bit of the double linked list, so the last bit of the double linked list is the longest unused node;
• The hash table stores the node addresses in the linked list corresponding to the key, which is used to add, delete, modify and query the key value;

initialization:

• n is the cache size;
• The double linked list and hash table are empty;

get(key):
First, the hash table is used to determine whether the key exists

• If the key does not exist, - 1 is returned;

• If the key exists, the corresponding value is returned, and the node corresponding to the key is placed on the leftmost side of the double linked list;

put(key, value):
First, the hash table is used to determine whether the key exists

• If the key exists, modify the corresponding value and put the node corresponding to the key on the leftmost side of the double linked list;
• If the key does not exist:
  • If the cache is full, delete the rightmost node of the double linked list (the node with the oldest last use time) and update the hash table;
  • Otherwise, insert (key, value): at the same time, put the node corresponding to the key on the leftmost side of the double linked list to update the hash table;

Time complexity analysis: the time complexity of double linked list and hash table is O(1), so the time complexity of get and set is O(1).

Several operations of corresponding double linked list

1. Delete p node

 p->right->left = p->left;
 p->left->right = p->right;

2. Insert p node after L node

p->right = L->right;
p->left = L;
L->right->left = p;
L->right = p;

3. Code

class LRUCache {
public:

    //Define double linked list
    struct Node{
        int key,value;
        Node* left ,*right;
        Node(int _key,int _value): key(_key),value(_value),left(NULL),right(NULL){}
    }*L,*R;//The leftmost and rightmost nodes of a double linked list do not store values.
    int n;
    unordered_map<int,Node*>hash;

    void remove(Node* p)
    {
        p->right->left = p->left;
        p->left->right = p->right;
    }
    void insert(Node *p)
    {
        p->right = L->right;
        p->left = L;
        L->right->left = p;
        L->right = p;
    }
    LRUCache(int capacity) {
        n = capacity;
        L = new Node(-1,-1),R = new Node(-1,-1);
        L->right = R;
        R->left = L;    
    }
    
    int get(int key) {
        if(hash.count(key) == 0) return -1; //There is no keyword key 
        auto p = hash[key];
        remove(p);
        insert(p);//Put the current node in the first place of the double linked list
        return p->value;
    }
    
    void put(int key, int value) {
        if(hash.count(key)) //If the key exists, modify the corresponding value
        {
            auto p = hash[key];
            p->value = value;
            remove(p);
            insert(p);
        }
        else 
        {
            if(hash.size() == n) //If the cache is full, delete the rightmost node of the double linked list
            {
                auto  p = R->left;
                remove(p);
                hash.erase(p->key); //Update hash table
                delete p; //Free memory
            }
            //Otherwise, insert (key, value)
            auto p = new Node(key,value);
            hash[key] = p;
            insert(p);
        }
    }
};

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

Link to the original question: 146. LRU caching mechanism