C# simple solution


  • 0
    0
    public class LRUCache 
    {
        class LRUCacheNode
        {
            internal LRUCacheNode prev;
            internal LRUCacheNode next;
            internal int key;
            internal int val;
            
            internal LRUCacheNode(int key, int val)
            {
                this.key = key;
                this.val = val;
            }
        }
        
        private int capacity;
        private LRUCacheNode head;
        private LRUCacheNode tail;    
        private Dictionary<int, LRUCacheNode> dic;
        
        public LRUCache(int capacity)
        {
            if (capacity < 1) throw new ArgumentException("capacity must be greater than 0");
            
            this.capacity = capacity;
            this.head = null;
            this.tail = null;
            this.dic = new Dictionary<int, LRUCacheNode>(capacity);        
        }
        
        public int Get(int key)
        {
            if (!dic.ContainsKey(key)) return -1;
            var node = dic[key];
            UpdateNodeRecentness(node);
            return node.val;
        }
        
        public void Put(int key, int value) 
        {
            if (dic.ContainsKey(key))
            {
                // update existing key/value
                var node = dic[key];
                node.val = value;
                UpdateNodeRecentness(node);
            }
            else
            {
                if (dic.Count == capacity)
                {
                    // out of capacity, evict least recent node (tail)
                    // remove from dic
                    dic.Remove(tail.key);
                    // update tail and head
                    if (head == tail) head = null;
                    if (tail.prev != null) tail.prev.next = null;
                    tail = tail.prev;                
                }
                
                var newNode = new LRUCacheNode(key, value);
                dic.Add(key, newNode);
                UpdateNodeRecentness(newNode);
            }
        }
        
        private void UpdateNodeRecentness(LRUCacheNode node)
        {
            if (node == null) return;
            
            if (node.prev == null && node.next == null)
            {
                // newly added node, set as the new head
                node.next = head;
                if (head != null) head.prev = node;
                head = node;
                if (tail == null) tail = node;
                return;
            }
            
            // remove the node from the doubly linked list
            if (node.prev != null)
            {
                node.prev.next = node.next;
            }
            else
            {
                // node.prev == null, so node is head, no need to update
                return;
            }
            
            if (node.next != null)
            {
                node.next.prev = node.prev;
            }
            else
            {
                // node.next == null, so node is tail, set node.prev as the new tail
                tail = node.prev;
            }
            
            // add it back to the head of the doubly linked list and set node as the new head
            node.next = head;
            node.prev = null;
            head.prev = node;
            head = node;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.