LRUCache.cs

namespaceLeetCodeNet.G0101_0200.S0146_lru_cache{

// #Medium #Top_100_Liked_Questions #Top_Interview_Questions #Hash_Table #Design #Linked_List
// #Doubly_Linked_List #Udemy_Linked_List #Top_Interview_150_Linked_List
// #Big_O_Time_O(1)_Space_O(capacity) #2024_01_09_Time_780_ms_(34.57%)_Space_239.2_MB_(12.44%)

publicclassLRUCache{
privatereadonlyintcapacity;
privatereadonlyDictionary<int,LinkedListNode<CacheItem>>cacheMap;
privatereadonlyLinkedList<CacheItem>cacheList;

publicLRUCache(intcapacity){
this.capacity=capacity;
cacheMap=newDictionary<int,LinkedListNode<CacheItem>>(capacity);
cacheList=newLinkedList<CacheItem>();
}

publicintGet(intkey){
if(cacheMap.TryGetValue(key,outvarnode)){
cacheList.Remove(node);
cacheList.AddFirst(node);
returnnode.Value.Value;
}
return-1;
}

publicvoidPut(intkey,intvalue){
if(cacheMap.TryGetValue(key,outvarnode)){
node.Value.Value=value;
cacheList.Remove(node);
cacheList.AddFirst(node);
}else{
if(cacheMap.Count>=capacity){
varlastNode=cacheList.Last;
cacheMap.Remove(lastNode.Value.Key);
cacheList.RemoveLast();
}
varnewNode=newLinkedListNode<CacheItem>(newCacheItem(key,value));
cacheMap.Add(key,newNode);
cacheList.AddFirst(newNode);
}
}

privateclassCacheItem{
publicintKey{get;}
publicintValue{get;set;}

publicCacheItem(intkey,intvalue){
Key=key;
Value=value;
}
}
}

publicclassKeyNode{
privateint_key;
privateint_val;
privateKeyNode_next;

publicintkey{
get{return_key;}
set{_key=value;}
}

publicintval{
get{return_val;}
set{_val=value;}
}

publicKeyNodenext{
get{return_next;}
set{_next=value;}
}

publicKeyNode(){
_key=int.MinValue;
_val=int.MinValue;
_next=null;
}

publicKeyNode(intkey,intval):this(){
_key=key;
_val=val;
}
}

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