C# LinkedDictionary<K, V>

Enhancement to a Dictionary<K,V> object which maintains an ordering of all Values such that they can be iterated in the forward or reverse direction, according to this ordering, in O(N). This is typically used for most-recently used (MRU) lists. The type used for V must inherit from the DoubleLink class, which provides members to support the doubly-linked list. The ordering is established by calling InsertAtFront for element(s) which have been added to the associated Dictionary<K,V> but which are not yet in the list. In a typical use, the list might be ordered by time of touch: the "current" element or element of interest is located by its key, unlinked from the list, and reinserted at the front, all in O(1) time.

using System;
using System.Collections.Generic;
using System.Diagnostics;

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// DoubleLink
//
// Base type for Values in LinkedDictionary<K, V>
//
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
[DebuggerDisplay("prev = {prev} next = {next}")]
public class DoubleLink
{
	DoubleLink next;
	DoubleLink prev;

	public DoubleLink Next
	{
		get { return next; }
		// Rude setter: doesn't examine or patch existing links 
		set
		{
			value.prev = this;
			next = value;
		}
	}

	public DoubleLink Prev
	{
		get { return prev; }
		// Rude setter: doesn't examine or patch existing links 
		set
		{
			value.next = this;
			prev = value;
		}
	}

	// Remove this item from a list by patching over it
	public void Unlink()
	{
		prev.next = next;
		next.prev = prev;
		next = prev = null;
	}

	// Insert this item into a list after the specified element
	public void InsertAfter(DoubleLink e)
	{
		e.next.prev = this;
		next = e.next;
		prev = e;
		e.next = this;
	}
};

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// LinkedDictionary<K, V>
//
// Enhancement to a Dictionary<K,V> object which maintains an ordering of all Values such that they can be
// iterated in the forward or reverse direction, according to this ordering, in O(N). The type used for V
// must inherit from DoubleLink class, a doubly-linked list. The ordering is established by calling 
// InsertAtFront for element(s) which have been added to the associated Dictionary<K,V> but which are not yet 
// in the list. In a typical use, the list might be ordered by time of touch: the "current" element or element
// of interest is located by its key, unlinked from the list, and reinserted at the front, all in O(1) time.
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public class LinkedDictionary<K, V> : Dictionary<K, V> where V : DoubleLink
{
	readonly DoubleLink first = new DoubleLink();
	readonly DoubleLink last = new DoubleLink();

	public LinkedDictionary()
	{
		first.Next = last;
	}

	/// <summary>
	/// Enumerate in forward order
	/// </summary>
	public IEnumerable<V> Forward
	{
		get
		{
			DoubleLink i = first.Next;
			while (i != last)
			{
				yield return (V)i;
				i = i.Next;
			}
		}
	}

	/// <summary>
	/// Enumerate in reverse order
	/// </summary>
	public IEnumerable<V> Reverse
	{
		get
		{
			DoubleLink i = last.Prev;
			while (i != first)
			{
				yield return (V)i;
				i = i.Prev;
			}
		}
	}

	/// <summary>
	/// Truncates all element(s) beyond e in the ordering. They should already be removed from the dictionary, 
	/// this only unlinks them
	/// </summary>
	public void TruncateAt(V e)
	{
		e.Next = last;
	}

	/// <summary>
	/// Element should already be removed from the dictionary, this only unlinks it
	/// </summary>
	public void Unlink(V e)
	{
		e.Unlink();
	}

	/// <summary>
	/// Element should already be in dictionary, but not linked
	/// </summary>
	public void LinkToFront(V e)
	{
		e.InsertAfter(first);
	}
};