Share C# explained solution: mix of Dictionary and linkedlist


  • 0
    O
    public class LRUCache
    {
      int mCapacity;
      // I mixed HashTable and Doubly linked list concepts in order to 
      // update and extract Top and Bottom in O(1) time
      IDictionary<int, LRUNode> mCache;
      LRUNode mTop, mBottom;
    
      public LRUCache(int capacity)
      {
        mCapacity = capacity;
        mCache = new Dictionary<int, LRUNode>();
      }
    
      public int Get(int key)
      {
        LRUNode node;
        if (mCache.TryGetValue(key, out node))
        {
          UpdateNodeTop(node);
          return node.Value;
        }
    
        return -1;
      }
    
      public void Set(int key, int value)
      {
        if (mCapacity < 1)
          return;
        LRUNode node;
        if (mCache.TryGetValue(key, out node))
        {
          node.Value = value;
          UpdateNodeTop(node);
        }
        else
        {
          if (mCache.Count == mCapacity)
          {
            // extract bottom item from the linked list
            int leastused = RemoveNodeBottom();
            // remove least recently used item from the cache
            mCache.Remove(leastused);
          }
    
          node = new LRUNode(key, value);
          // Add new item to the cache
          mCache.Add(key, node);
          // Add item to the top of the linkedlist
          AddNodeTop(node);
        }
      }
    
      private void AddNodeTop(LRUNode node)
      {
        if (mTop == null || mBottom == null)
        {
          // Empty list
          mTop = node;
          mBottom = node;
        }
        else
        {
          // Add to the top
          mTop.Next = node;
          node.Prev = mTop;
          mTop = node;
        }
      }
    
      private void UpdateNodeTop(LRUNode node)
      {
        if (mTop == node)
          return;
        // Remove node links
        var next = node.Next;
        var prev = node.Prev;
        if (mBottom == node)
        {
          next.Prev = null;
          mBottom = next;
        }
        else
        {
          next.Prev = prev;
          prev.Next = next;
        }
    
        // set node as the top
        mTop.Next = node;
        node.Prev = mTop;
        node.Next = null;
        mTop = node;
      }
    
      private int RemoveNodeBottom()
      {
        var node = mBottom;
        if (mBottom == mTop)
        {
          // if one item list
          mBottom = null;
          mTop = null;
        }
        else
        {
          // Put next node as the bottom
          mBottom = node.Next;
          node.Next.Prev = null;
        }
    
        // Clear links
        node.Next = null;
        node.Prev = null;
    
        return node.Key;
      }
    
      // Helper class to create nodes
      public class LRUNode
      {
        public int Key { get; private set; }
        public int Value { get; set; }
        public LRUNode Prev { get; set; }
        public LRUNode Next { get; set; }
    
        public LRUNode(int key, int value)
        {
          Key = key;
          Value = value;
          Prev = null;
          Next = null;
        }
      }
    }

Log in to reply
 

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