Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:


	LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
	int get(int key) Return the value of the key if the key exists, otherwise return -1.
	void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.


The functions get and put must each run in O(1) average time complexity.

&nbsp;
Example 1:

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]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4


&nbsp;
Constraints:


	1 &lt;= capacity &lt;= 3000
	0 &lt;= key &lt;= 104
	0 &lt;= value &lt;= 105
	At most 2 * 105 calls will be made to get and put.


class LRUCache {
    int N;
    list<int> pages;
    unordered_map<int, pair<int, list<int>::iterator>> cache;
public:
    LRUCache(int capacity) : N(capacity) {
        
    }
    
    int get(int key) {
        if (cache.find(key) != cache.end()) {
            pages.erase(cache[key].second);
            pages.push_front(key);
            cache[key].second = pages.begin();
            return cache[key].first;
        }
        
        return -1;
    }
    
    void put(int key, int value) {
        if (cache.find(key) != cache.end()) {
            pages.erase(cache[key].second);
        } else {
            if (pages.size() == N) {
                int lru = pages.back();
                cache.erase(lru);
                pages.pop_back();
            }
        }
        
        pages.push_front(key);
        cache[key] = {value, pages.begin()};
    }
};
class LRUCache {
    // Declare Node class for Doubly Linked List 
    class Node{
        int key,value;// to store key and value 
        Node next,prev; // Next and Previous Pointers
        Node(int k, int v){
            key=k;
            value=v;
        }
    }
    Node head=new Node(-1,-1); // Default values 
    Node tail=new Node(-1,-1);
    Map<Integer,Node>mp;  // to store key and Node
    int cap;
    public LRUCache(int capacity) {
        // initializing in constructor
        cap=capacity;
        head.next=tail;
        tail.prev=head;
        mp=new HashMap<Integer,Node>();
    }
    
    public int get(int key) {
        // if map contains the specific key 
        if(mp.containsKey(key)){
            Node existing=mp.get(key);
            del(existing);
            ins(existing);// reinserting to keep key after the head pointer and to update LRU list
            return existing.value;
        }
        //otherwise
        return -1;
    }
    
    public void put(int key, int value) {
        // if map contains the key
        if(mp.containsKey(key)){
            Node existing=mp.get(key);
            // remove from the map and delete from the LRU list
            mp.remove(key);
            del(existing);
        }
        // if map size is equal to spcified capacity of the LRU list
        if(mp.size()==cap){
            // remove from the map and delete from the LRU list
            mp.remove(tail.prev.key);
            del(tail.prev);
        }
        Node newNode = new Node(key,value);
        ins(newNode); 
        mp.put(key,head.next); 
    }
    public void ins(Node newNode){
        //Insert always after the head of the linkedList
        Node temp=head.next;
        head.next=newNode;
        newNode.prev=head;
        newNode.next=temp;
        temp.prev=newNode;
    }
    public void del(Node newNode){
        //Remove the specified node using previous and next pointers
        Node pr=newNode.prev;
        Node nx=newNode.next;
        pr.next=nx;
        nx.prev=pr;
        
    }
}
class LRUCache {
public:
    int mx;
    class node{
        public:
        node *prev,*next;
        int key,val;
        node(int k,int v){
            key=k,val=v;
        }
    };
    unordered_map<int,node*> mp;
        node *head=new node(-1,-1);
        node *tail=new node(-1,-1);
    LRUCache(int capacity) {
        mx=capacity;
        mp.reserve(1024);
        mp.max_load_factor(0.25);

        head->next=tail;tail->prev=head;
    }
    
    void addnode(node *temp){
        node *temp1=head->next;
        head->next=temp;temp->prev=head;
        temp->next=temp1;temp1->prev=temp;
    }
    
    void deletenode(node *temp){
        node *temp1=temp->prev;
        node *temp2=temp->next;
        temp1->next=temp2;
        temp2->prev=temp1;
    }
    
    int get(int key) {
        if(mp.find(key)!=mp.end()){
            node *temp=mp[key];
            int res=temp->val;
            mp.erase(key);
            deletenode(temp);
            addnode(temp);
            mp[key]=head->next;
            return res;
        }
        return -1;
    }
    
    void put(int key, int value) {
        if(mp.find(key)!=mp.end()){
            node *temp=mp[key];
            mp.erase(key);
            deletenode(temp);
        }
        if(mp.size()==mx){
            mp.erase(tail->prev->key);
            deletenode(tail->prev);
        }
        addnode(new node(key,value));
        mp[key]=head->next;
    }
};
/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if(!this.cache.has(key)){
        return -1
    }
    
    let val = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, val)
    return val
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    if(this.cache.has(key)){
        this.cache.delete(key);
    }else{
        if(this.cache.size >= this.capacity){
            let [lastElm] = this.cache.keys()
            this.cache.delete(lastElm)
        }
    }
    this.cache.set(key, value)
    
};

/** 
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */
LRU Cache