LinkedDictionary for C#

I've been working on a couple of Java to C# ports, and I didn't have an acceptable C# implementation for a LinkedHashMap; so, I wrote one. It supports both access and insert order tracking. I've named this class LinkedDictionary<TKey, TValue>, which seems more in the spirit of the BCL.

A LinkedDictionary<TKey, TValue> is hybrid of a LinkedList<TValue> and Dictionary<TKey, TValue>. It supports both insert order retrieval (collection is ordered in the in the same order as keys were inserted) or access order retrieval (keys are reordered during to insert or access); therefore, enumeration of the collection gets the objects back in a predictable order (like a LinkedList<TValue>). Single object access by key is fast like a Dictionary<TKey, TValue> (close to O(1) vs. O(n) for a LinkedList<TValue>), and similar O(1) performance for LinkedList<TValue> operations (insert, remove and enumeration). Of course, there's memory overhead of having this functionality, but for reasonably sized collections this has some advantages.

Here's a couple of small tests that illustrate the ordering functionality in this class:

[Test]
public void SampleInsertOrder() {
    var map = new LinkedDictionary<int, int> {{2, 2}, {1, 1}, {0, 0}};
    // Check that ordering is still 0,1,2
    int count = 0;
    foreach (var entry in map) {
        Assert.AreEqual(count++, entry.Key);
    }
}

[Test]
public void SampleAccessOrder() {
    var map = new LinkedDictionary<int, int>(true) {{ 2, 2 }, { 1, 1 }, {0, 0} };
    // Access each entry from 0,1,2 (they were inserted 2,1,0)
    for (int i = 0; i < map.Count; i++) {
        var v = map[i];
    }
    // Check that ordering is 2,1,0
    int count = 2;
    foreach (var entry in map) {
        Assert.AreEqual(count--, entry.Key);
    }
}

The BCL SortedDictionary<TKey, TValue> class has similar functionality but is slower and isn't capable of handling access ordering.

The cool thing about access order this class is that one could create a subclass that would act like a fixed size cache. It would automatically track the most recently used objects and eject the least recently used object whenever a new object was added.

You can download a VS2008 solution here, it contains full source and NUnit tests.