Is there a generic alternative to the ListDictionary class?

Question

I was looking at some sample code and in it they used a ListDictionary object to store a small amount of data (around 5-10 objects or so, but this number could change over time). The only issue I have with using this class is that, unlike everything else I've been doing, it's not generic. This means, and correct me if I'm wrong here, that every time I get an object out of here or enumerate over it that there's casting going on. Is there enough overhead in the larger Dictionary<T> object to justify the overhead of a non-generic ListDictionary?

The code that will be using this object will be enumerated over on each page load which I'm guessing is why the ListDictionary class was used over one of the other alternatives. This is also why I would like the most performance out of this list of data.

Answer 1

Unfortunately there is no generic equivalent of ListDictionary.

However it shouldn't be terribly difficult to implement one. ListDictionary essentially works by keeping a linked list of Key/Value pairs and iterating over them for lookup operations. You could build a ListDictionary<TKey,TValue> by wrapping a LinkedList<T> with some very simple LINQ expressions.

For example

public class LinkedDictionary<TKey,TValue> {
  private LinkedList<KeyValuePair<TKey,TValue>> _list = new LinkedList<KeyValuePair<TKey,TValue>>();
  private IEqualityComparer<TKey> _comp = EqualityComparer<TKey>.Default;

  public void Add(TKey key, TValue value) { 
    _list.Add(new KeyValuePair<TKey,TValue>(key,value)); 
  }
  public TValue Get(TKey key) {  
    return _list.Where(x => _comp.Equals(x.Key,key)).First().Value;
  }
  ...
}

Answer 2

If the data you are storing in the ListDictionary is always objects (classes), rather than value types, then it would probably be faster than Dictionary<T>. If you will be storing value types (structs, int, double, etc.), then the cost of boxing/unboxing will most likely balance things out, and I would recommend the Dictionary<T> instead.

Overall, however, I would point out that the performance difference between these two are likely to be the least of your performance problems overall. Small things like this are generally the last thing to worry about when it comes to performance optimization. Larger scale things, such as inter-process calls, database and web service interaction, etc. should be addressed first before ever being concerned about the minor performance difference between ListDictionary and Dictionary<T>.

Answer 3

There is no generic equivalent of ListDictionary.

If your use of this small dictionary isn't dominated by Add and Remove, you might consider SortedList<TKey, TValue> which, despite its name, implements IDictionary<TKey, TValue>. Unlike ListDictionary which is backed by a singly-linked list, SortedList is backed by an array of sorted keys and an array values.

Answer 4

A simple check on MSDN-ListDictionary class will reveal

This is a simple implementation of IDictionary using a singly linked list. It is smaller and faster than a Hashtable if the number of elements is 10 or less. This should not be used if performance is important for large numbers of elements.