OrderedDictionary is data structure that is similar to Dictionary, but allow to track sequence of adding key/value pairs (e.g. Queue and Dictionary in one class)

OrderedDictionary.cs

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace DataStructures
{
    /// <summary>
    /// OrderedDictionary is data structure that is similar to Dictionary, but allow to track sequence of adding key/value pairs (e.g. Queue and Dictionary in one class)
    /// </summary>
    public class OrderedDictionary<TKey, TValue> : IDictionary<TKey, TValue>
    {
        private class Node
        {
            public Node Previos;
            public Node Next;

            public readonly TKey Key;
            public TValue Value;

            public Node(TKey key, TValue value)
            {
                Key = key;
                Value = value;
            }

            public KeyValuePair<TKey, TValue> CreatePair()
            {
                return new KeyValuePair<TKey, TValue>(Key, Value);
            }
        }

        private Node _head;
        private Node _tail;

        // In inner Dictionary use hash-table that allows to perform most operations with complexity O(1). Key should override GetHashCode() and Equals methods for correct work.
        private readonly Dictionary<TKey, Node> _dict;

        public OrderedDictionary()
        {
            _dict = new Dictionary<TKey, Node>();
        }

        public OrderedDictionary(int capacity)
        {
            _dict = new Dictionary<TKey, Node>(capacity);
        }

        public OrderedDictionary(IDictionary<TKey, TValue> collection)
        {
            _dict = new Dictionary<TKey, Node>(collection.Count);

            foreach (var pair in collection)
                Add(pair.Key, pair.Value);
        }

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

        /// <summary>
        /// Insert element. Complexity O(1)
        /// </summary>
        public void Add(TKey key, TValue value)
        {
            var node = new Node(key, value);

            _dict.Add(key, node); // It will throw an exception if there is dublicate

            node.Previos = _tail;
            if (_tail != null)
                _tail.Next = node;
            _tail = node;

            if (_head == null)
                _head = node;
        }

        /// <summary>
        /// Return element by key. Complexity O(1)
        /// </summary>
        public TValue Get(TKey key)
        {
            return _dict[key].Value; // It will throw an exception if there is no element
        }

        public bool TryGetValue(TKey key, out TValue value)
        {
            Node node;
            bool exists = _dict.TryGetValue(key, out node);

            if (!exists)
            {
                value = default(TValue);
                return false;
            }

            value = node.Value;
            return true;
        }

        public TValue this[TKey key]
        {
            get { return _dict[key].Value; }
            set { _dict[key].Value = value; }
        }

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

        ICollection<TKey> IDictionary<TKey, TValue>.Keys
        {
            get { return _dict.Keys; }
        }

        public IEnumerable<TKey> Keys
        {
            get
            {
                var node = _head;

                while (node != null)
                {
                    yield return node.Key;
                    node = node.Next;
                }
            }
        }

        ICollection<TValue> IDictionary<TKey, TValue>.Values
        {
            get { return _dict.Values.Select(v => v.Value).ToList(); }
        }

        public IEnumerable<TValue> Values
        {
            get
            {
                var node = _head;

                while (node != null)
                {
                    yield return node.Value;
                    node = node.Next;
                }
            }
        }

        /// <summary>
        /// Return first inserted element. Complexity O(1)
        /// </summary>
        public KeyValuePair<TKey, TValue> Peek()
        {
            if (_head == null)
                throw new ApplicationException("There are no elements");

            return _head.CreatePair();
        }

        /// <summary>
        /// Remove first inserted element. Complexity O(1)
        /// </summary>
        public void Remove()
        {
            Remove(Peek().Key);
        }

        /// <summary>
        /// Remove element by key. Complexity O(1)
        /// </summary>
        public bool Remove(TKey key)
        {
            var node = _dict[key];

            bool ret = _dict.Remove(key);

            if (_tail == node)
                _tail = node.Previos;
            if (_head == node)
                _head = node.Next;

            if (node.Previos != null)
                node.Previos.Next = node.Next;
            if (node.Next != null)
                node.Next.Previos = node.Previos;

            return ret;
        }

        public void Clear()
        {
            _head = _tail = null;
            _dict.Clear();
        }

        bool ICollection<KeyValuePair<TKey, TValue>>.Contains(KeyValuePair<TKey, TValue> item)
        {
            Node node;
            _dict.TryGetValue(item.Key, out node);

            return node != null && EqualityComparer<TValue>.Default.Equals(node.Value, item.Value);
        }

        void ICollection<KeyValuePair<TKey, TValue>>.CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
        {
            throw new NotSupportedException();
        }

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

        public int Count
        {
            get { return _dict.Count; }
        }

        bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly
        {
            get { return false; }
        }

        public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
        {
            var node = _head;

            while (node != null)
            {
                yield return node.CreatePair();
                node = node.Next;
            }
        }

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