using System;

using System.Collections.Generic;

​

public class Program

{

    public static void Main()

    {

        var cache = new LRUCache<int, int>(3);

        cache.Put(1, 1);

        cache.Put(2, 2);

        cache.Put(3, 3);

        cache.Put(4, 4);

        Console.WriteLine(cache.Get(4)); // 4

        Console.WriteLine(cache.Get(3)); // 3

        Console.WriteLine(cache.Get(2)); // 2

        Console.WriteLine(cache.Get(1)); // 0

        cache.Put(5, 5);

        Console.WriteLine(cache.Get(1)); // 0

        Console.WriteLine(cache.Get(2)); // 2

        Console.WriteLine(cache.Get(3)); // 3

        Console.WriteLine(cache.Get(4)); // 0

        Console.WriteLine(cache.Get(5)); // 5

        Console.WriteLine("Done");

        Console.ReadKey();

    }

​

    public class LRUCache<K, V>

    {

        private readonly int _capacity;

        private readonly Dictionary<K, LinkedListNode<(K Key, V Value)>> _cache;

        private readonly LinkedList<(K Key, V Value)> _lruList;

        public LRUCache(int capacity)

        {

            _capacity = capacity;

            _cache = new Dictionary<K, LinkedListNode<(K Key, V Value)>>(capacity);

            _lruList = new LinkedList<(K Key, V Value)>();

        }

​

        public V Get(K key)

        {

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

            {

                return default;

            //throw new KeyNotFoundException("The given key was not present in the cache.");

            }

​

            _lruList.Remove(node);

            _lruList.AddFirst(node);

            return node.Value.Value;

        }

​

        public void Put(K key, V value)

        {

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

            {

                node.Value = (key, value);

                _lruList.Remove(node);

                _lruList.AddFirst(node);

            }

            else

            {

                if (_cache.Count >= _capacity)

                {

                    var lru = _lruList.Last;

                    _cache.Remove(lru.Value.Key);

                    _lruList.RemoveLast();

                }

​

                var newNode = new LinkedListNode<(K Key, V Value)>((key, value));

                _lruList.AddFirst(newNode);

                _cache[key] = newNode;

            }

        }

    }

}