using System.Collections.Generic;

​

public class LRUCache

{

    private const int NotFound = -1;

    private readonly int _capacity;

    private readonly LinkedList<CacheItem> _queue;

    private readonly Dictionary<int, LinkedListNode<CacheItem>> _cache;

​

    public LRUCache(int capacity)

    {

        _capacity = capacity;

        _queue = new LinkedList<CacheItem>();

        _cache = new Dictionary<int, LinkedListNode<CacheItem>>(capacity);

    }

    public int Get(int key)

    {

        if (_cache.ContainsKey(key) == false)

        {

            return NotFound;

        }

        var node = _cache[key];

        BringToFirst(node);

        var cacheItem = node.Value;

        return cacheItem.Value;

    }

    public void Put(int key, int value)

    {

        if (_cache.TryGetValue(key, out var node))

        {

            var cacheItem = node.Value;

            cacheItem.Value = value;

            BringToFirst(node);

        }

        else

        {

            node = new LinkedListNode<CacheItem>(new CacheItem(key, value));

            _cache[key] = node;

            _queue.AddFirst(node);

            if (_queue.Count > _capacity)

            {

                var lastNode = _queue.Last;

                _queue.Remove(lastNode);

                var cacheItem = lastNode.Value;

                _cache.Remove(cacheItem.Key);

            }

        }

    }

    private void BringToFirst(LinkedListNode<CacheItem> node)

    {

        if (_queue.Count > 1)

        {

            _queue.Remove(node);

            _queue.AddFirst(node);

        }

    }

    private class CacheItem

    {

        public int Key { get; }

        public int Value { get; set; }

        public CacheItem(int key, int value)

        {

            Key = key;

            Value = value;

        }

    }

}

​