Dictionary vs List

Question

So I ran into a Dictionary<int, int> today at work. This just seemed weird to me because I would have probably just used a List<int> instead. Is there a difference and would there be a use case where one structure would be preferred over the other?

Answer 1

You would use a Dictionary<int, int> if your indexes have a special meaning besides just positional placement.

The immediate example that comes to mind is storing an id column and an int column in a database. For example, if you have a [person-id] column and a [personal-pin] column, then you might bring those into a Dictionary<int, int>. This way pinDict[person-id] gives you a PIN, but the index is meaningful and not just a position in a List<int>.

But really, any time you have two related lists of integers, this could be an appropriate data structure.

Answer 2

Think of the List as an array and the Dictionary as a hash table. You would only use the Dictionary if you needed to map (or associate) meaningful keys to values, whereas a List only maps (or associates) positions (or indices) to values.

For example, say you wanted to store an association between a person's age and their height. You could use a Dictionary<int, int> to map the person's age (an int) to their height (an int):

Dictionary<int, int> personHeightMap = new Dictionary<int, int>();

personHeightMap.Add(21, 185);
personHeightMap.Add(31, 174);

int height = personHeightMap.ContainsKey(21) ? personHeightMap[21] : -1;

Not a very useful example, but the point is you wouldn't be able to do this as elegantly with a List because it would need to store these values positionally.

Answer 3

Semantically, a Dictionary<int, T> and List<T> are very similar, both are random access containers of the .NET framework. To use a list as a replacement for a dictionary, you need a special value in your type T (like null) to represent the empty slots in your list. If T is not a nullable type like int, you could use int? instead, or if you are just expecting to store positive values, you could also use a special value like -1 to represent empty slots.

Which one you will choose should depend on the range of the key values. If your keys in the Dictionary<int, T> are within an integer interval, without many gaps between them (for example, 80 values out of [0,...100]), then a List<T> will be more appropriate, since the accessing by index is faster, and there is less memory and time overhead compared to a dictionary in this case.

If your key values are 100 int values from a range like [0,...,1000000], then a List<T> needs memory to hold 1000000 values of T, where your dictionary will just need memory in an order of magnitude around 100 values of T, 100 values of int (plus some overhead, in reality expect about 2 times the memory for storing those 100 keys and values). So in the latter case a dictionary will be more appropriate.