OrderedDictionary-LinkedList.cs

using System.Collections;
using System.Diagnostics.CodeAnalysis;

namespace OrderedDictionary
{
    internal class OrderedDictionary<TKey, TValue> : IDictionary<TKey, TValue> where TKey : notnull
    {
        private readonly Dictionary<TKey, LinkedListNode<KeyValuePair<TKey, TValue>>> _dictionary = new();
        private readonly LinkedList<KeyValuePair<TKey, TValue>> _linkedList = new();

        private void SetValue(TKey key, TValue value)
        {
            if (_dictionary.ContainsKey(key))
            {
                _dictionary[key].Value = new KeyValuePair<TKey, TValue>(key, value);
            }
            else
            {
                var newNode = new LinkedListNode<KeyValuePair<TKey, TValue>>(new KeyValuePair<TKey, TValue>(key, value));
                _dictionary[key] = newNode;
                _linkedList.AddLast(newNode);
            }
        }

        public TValue this[TKey key] { get => _dictionary[key].Value.Value; set => SetValue(key, value); }

        public ICollection<TKey> Keys => _linkedList.Select(m => m.Key).ToList();

        public ICollection<TValue> Values => _linkedList.Select(m => m.Value).ToList();

        public int Count => _dictionary.Count;

        public bool IsReadOnly => false;

        public void Add(TKey key, TValue value)
        {
            SetValue(key, value);
        }

        void ICollection<KeyValuePair<TKey, TValue>>.Add(KeyValuePair<TKey, TValue> item)
        {
            SetValue(item.Key, item.Value);
        }

        public void Clear()
        {
            _dictionary.Clear();
            _linkedList.Clear();
        }

        public bool Contains(KeyValuePair<TKey, TValue> item)
        {
            return _dictionary.ContainsKey(item.Key) && _dictionary[item.Key].Value.Value.Equals(item.Value);
        }

        public bool ContainsKey(TKey key)
        {
            return _dictionary.ContainsKey(key);
        }

        public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
        {
            foreach (var entry in this)
                array[arrayIndex++] = entry;
        }

        public bool Remove(TKey key)
        {
            if (_dictionary.ContainsKey(key))
            {
                var node = _dictionary[key];
                _linkedList.Remove(node); //This method is an O(1) operation.
                _dictionary.Remove(key);
                return true;
            }
            return false;
        }

        bool ICollection<KeyValuePair<TKey, TValue>>.Remove(KeyValuePair<TKey, TValue> item)
        {
            return this.Remove(item.Key);
        }

        public bool TryGetValue(TKey key, [MaybeNullWhen(false)] out TValue value)
        {
            if (_dictionary.ContainsKey(key))
            {
                value = _dictionary[key].Value.Value;
                return true;
            }
            else
            {
                value = default(TValue);
                return false;
            }
        }

        private IEnumerator<KeyValuePair<TKey, TValue>> CreateEnumerator()
        {
            return _linkedList.GetEnumerator();
        }

        IEnumerator<KeyValuePair<TKey, TValue>> IEnumerable<KeyValuePair<TKey, TValue>>.GetEnumerator()
        {
            return CreateEnumerator();
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return CreateEnumerator();
        }
    }
}