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.
At most 2 * 105 calls will be made to get and put.
Solutions
Solution 1: Hash Table + Doubly Linked List
We can implement an LRU (Least Recently Used) cache using a "hash table" and a "doubly linked list".
Hash Table: Used to store the key and its corresponding node location.
Doubly Linked List: Used to store node data, sorted by access time.
When accessing a node, if the node exists, we delete it from its original position and reinsert it at the head of the list. This ensures that the node stored at the tail of the list is the least recently used node. When the number of nodes exceeds the maximum cache space, we eliminate the node at the tail of the list.
When inserting a node, if the node exists, we delete it from its original position and reinsert it at the head of the list. If it does not exist, we first check if the cache is full. If it is full, we delete the node at the tail of the list and insert the new node at the head of the list.
The time complexity is $O(1)$, and the space complexity is $O(\textit{capacity})$.
classNode:def__init__(self,key=0,val=0):self.key=keyself.val=valself.prev=Noneself.next=NoneclassLRUCache:def__init__(self,capacity:int):self.cache={}self.head=Node()self.tail=Node()self.capacity=capacityself.size=0self.head.next=self.tailself.tail.prev=self.headdefget(self,key:int)->int:ifkeynotinself.cache:return-1node=self.cache[key]self.move_to_head(node)returnnode.valdefput(self,key:int,value:int)->None:ifkeyinself.cache:node=self.cache[key]node.val=valueself.move_to_head(node)else:node=Node(key,value)self.cache[key]=nodeself.add_to_head(node)self.size+=1ifself.size>self.capacity:node=self.remove_tail()self.cache.pop(node.key)self.size-=1defmove_to_head(self,node):self.remove_node(node)self.add_to_head(node)defremove_node(self,node):node.prev.next=node.nextnode.next.prev=node.prevdefadd_to_head(self,node):node.next=self.head.nextnode.prev=self.headself.head.next=nodenode.next.prev=nodedefremove_tail(self):node=self.tail.prevself.remove_node(node)returnnode# Your LRUCache object will be instantiated and called as such:# obj = LRUCache(capacity)# param_1 = obj.get(key)# obj.put(key,value)
classNode{intkey;intval;Nodeprev;Nodenext;Node(){}Node(intkey,intval){this.key=key;this.val=val;}}classLRUCache{privateMap<Integer,Node>cache=newHashMap<>();privateNodehead=newNode();privateNodetail=newNode();privateintcapacity;privateintsize;publicLRUCache(intcapacity){this.capacity=capacity;head.next=tail;tail.prev=head;}publicintget(intkey){if(!cache.containsKey(key)){return-1;}Nodenode=cache.get(key);moveToHead(node);returnnode.val;}publicvoidput(intkey,intvalue){if(cache.containsKey(key)){Nodenode=cache.get(key);node.val=value;moveToHead(node);}else{Nodenode=newNode(key,value);cache.put(key,node);addToHead(node);++size;if(size>capacity){node=removeTail();cache.remove(node.key);--size;}}}privatevoidmoveToHead(Nodenode){removeNode(node);addToHead(node);}privatevoidremoveNode(Nodenode){node.prev.next=node.next;node.next.prev=node.prev;}privatevoidaddToHead(Nodenode){node.next=head.next;node.prev=head;head.next=node;node.next.prev=node;}privateNoderemoveTail(){Nodenode=tail.prev;removeNode(node);returnnode;}}/** * 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); */
structNode{intk;intv;Node*prev;Node*next;Node():k(0),v(0),prev(nullptr),next(nullptr){}Node(intkey,intval):k(key),v(val),prev(nullptr),next(nullptr){}};classLRUCache{public:LRUCache(intcapacity):cap(capacity),size(0){head=newNode();tail=newNode();head->next=tail;tail->prev=head;}intget(intkey){if(!cache.count(key))return-1;Node*node=cache[key];moveToHead(node);returnnode->v;}voidput(intkey,intvalue){if(cache.count(key)){Node*node=cache[key];node->v=value;moveToHead(node);}else{Node*node=newNode(key,value);cache[key]=node;addToHead(node);++size;if(size>cap){node=removeTail();cache.erase(node->k);--size;}}}private:unordered_map<int,Node*>cache;Node*head;Node*tail;intcap;intsize;voidmoveToHead(Node*node){removeNode(node);addToHead(node);}voidremoveNode(Node*node){node->prev->next=node->next;node->next->prev=node->prev;}voidaddToHead(Node*node){node->next=head->next;node->prev=head;head->next=node;node->next->prev=node;}Node*removeTail(){Node*node=tail->prev;removeNode(node);returnnode;}};/** * 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); */
classLRUCache{capacity:number;map:Map<number,number>;constructor(capacity:number){this.capacity=capacity;this.map=newMap();}get(key:number):number{if(this.map.has(key)){constval=this.map.get(key)!;this.map.delete(key);this.map.set(key,val);returnval;}return-1;}put(key:number,value:number):void{this.map.delete(key);this.map.set(key,value);if(this.map.size>this.capacity){this.map.delete(this.map.keys().next().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) */
usestd::cell::RefCell;usestd::collections::HashMap;usestd::rc::Rc;structNode{key:i32,value:i32,prev:Option<Rc<RefCell<Node>>>,next:Option<Rc<RefCell<Node>>>,}implNode{#[inline]fnnew(key:i32,value:i32)->Self{Self{key,value,prev:None,next:None,}}}structLRUCache{capacity:usize,cache:HashMap<i32,Rc<RefCell<Node>>>,head:Option<Rc<RefCell<Node>>>,tail:Option<Rc<RefCell<Node>>>,}/** * `&self` means the method takes an immutable reference. * If you need a mutable reference, change it to `&mut self` instead. */implLRUCache{fnnew(capacity:i32)->Self{Self{capacity:capacityasusize,cache:HashMap::new(),head:None,tail:None,}}fnget(&mutself,key:i32)->i32{matchself.cache.get(&key){Some(node)=>{letnode=Rc::clone(node);self.remove(&node);self.push_front(&node);letvalue=node.borrow().value;value}None=>-1,}}fnput(&mutself,key:i32,value:i32){matchself.cache.get(&key){Some(node)=>{letnode=Rc::clone(node);node.borrow_mut().value=value;self.remove(&node);self.push_front(&node);}None=>{letnode=Rc::new(RefCell::new(Node::new(key,value)));self.cache.insert(key,Rc::clone(&node));self.push_front(&node);ifself.cache.len()>self.capacity{letback_key=self.pop_back().unwrap().borrow().key;self.cache.remove(&back_key);}}};}fnpush_front(&mutself,node:&Rc<RefCell<Node>>){matchself.head.take(){Some(head)=>{head.borrow_mut().prev=Some(Rc::clone(node));node.borrow_mut().prev=None;node.borrow_mut().next=Some(head);self.head=Some(Rc::clone(node));}None=>{self.head=Some(Rc::clone(node));self.tail=Some(Rc::clone(node));}};}fnremove(&mutself,node:&Rc<RefCell<Node>>){match(node.borrow().prev.as_ref(),node.borrow().next.as_ref()){(None,None)=>{self.head=None;self.tail=None;}(None,Some(next))=>{self.head=Some(Rc::clone(next));next.borrow_mut().prev=None;}(Some(prev),None)=>{self.tail=Some(Rc::clone(prev));prev.borrow_mut().next=None;}(Some(prev),Some(next))=>{next.borrow_mut().prev=Some(Rc::clone(prev));prev.borrow_mut().next=Some(Rc::clone(next));}};}fnpop_back(&mutself)->Option<Rc<RefCell<Node>>>{matchself.tail.take(){Some(tail)=>{self.remove(&tail);Some(tail)}None=>None,}}}
publicclassLRUCache{classNode{publicNodePrev;publicNodeNext;publicintKey;publicintVal;}privateNodehead=newNode();privateNodetail=newNode();privateDictionary<int,Node>cache=newDictionary<int,Node>();privatereadonlyintcapacity;privateintsize;publicLRUCache(intcapacity){this.capacity=capacity;head.Next=tail;tail.Prev=head;}publicintGet(intkey){Nodenode;if(cache.TryGetValue(key,outnode)){moveToHead(node);returnnode.Val;}return-1;}publicvoidPut(intkey,intVal){Nodenode;if(cache.TryGetValue(key,outnode)){moveToHead(node);node.Val=Val;}else{node=newNode(){Key=key,Val=Val};cache.Add(key,node);addToHead(node);if(++size>capacity){node=removeTail();cache.Remove(node.Key);--size;}}}privatevoidmoveToHead(Nodenode){removeNode(node);addToHead(node);}privatevoidremoveNode(Nodenode){node.Prev.Next=node.Next;node.Next.Prev=node.Prev;}privatevoidaddToHead(Nodenode){node.Next=head.Next;node.Prev=head;head.Next=node;node.Next.Prev=node;}privateNoderemoveTail(){Nodenode=tail.Prev;removeNode(node);returnnode;}}/** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.Get(key); * obj.Put(key,Val); */