10 C# Generic Collection Types You Should Know

It is every programmer dilemma to choose which collection type to use for a particular scenario. Even worse, some people use List<T> all the time whenever they encounter a collection of objects. You might have heard some other collection types such as the primitive Array (T[]), Dictionary<TKey, TValue>, Stack<T>, Queue<T>, etc. We will look at 10 of the most used generic collection types, its advantages, and disadvantages as well as the best type to choose for different scenarios. When processing a large amount of data, it is critical to choose the right type, as it will significantly affect the performance of your code.

A collection type itself is an object, in which responsible for managing groups of objects in memory. Most of it derive from the interfaces ICollection, IComparer, IEnumerable, IList, IDictionary, and IDictionaryEnumerator and their generic equivalents. All of the C# built-in collection types can be access from within the System.Collections namespace.

In general, collection types can be categorized into 3 groups:

  • List
  • Dictionary
  • Set

Lists are collections of ordered objects with indexes. You can think of it as hotel rooms, in which every room has an index; the room number, and you can locate an item based on its index. Dictionaries are collections of objects where each item is associated with a particular key, and you always need that key to access the object. While sets are collections types which are usually used to logically handle a group of objects as a whole.

Generic Collection Types  

There are many collection types in C# you could use. All of them are direct descendants of IEnumerable class sitting at the top of the hierarchy. Every type is guaranteed to be able to enumerate their items. It sounds obvious because almost every single time you would want to access and interact with its item. Some of the basic collection types that implement IEnumerable are List<T>, Dictionary<T>, and HashSet<T>. There are also other classes such as SortedList<T> and SortedDictionary<T> that you could use for more complex purposes.

1. Array

Array represents an ordered collection of an object that can be indexed individually. It's the most basic form of collection types and a building block for the other collection type. It has the best performance due to its simplicity. However, this type is not dynamic. Once you declared it's length it will not be able to grow and shrink down. The C# primitive array uses this class.

int[] myIntArray = new int[5] { 1, 2, 3, 4, 5 };
// Prints the third item
Console.WriteLine("Third item : " + myIntArray[2] );
 
//This code produces the following output.
//Third item : 3

 

2. Collection<T>

Collection<T> represents a strongly typed and modifiable collection of objects. It provides the base class for a generic collection. Collection<T> makes it possible to add and remove items dynamically. Unlike the primitive array, Collection<T> length will grow and shrink automatically according to the number of its values. It will grow once the maximum capacity is exceeded and shrink once there are a lot of unoccupied indexes. Using Collection<T> instead of the primitive array provides a more manageable collection handling.

Collection<int> numbers= new Collection<int>() { "3", "12" , "7", "1" };
numbers.Add(-5);
Console.WriteLine(numbers.First());
Console.WriteLine(numbers.Last());

//This code produces the following output.
//3
//-5

 

3. List<T>

List<T> represents a strongly typed list of objects that can be accessed by index. Because the items are stored contiguously as an array, you can access items in the List<T> very quickly by index. List<T> provides additional methods to manipulate collection items which Collection<T> doesn't have such as Sort, Find, AddRange and so on.

List<T> has O(1) for lookup efficiency by index, O(n) for lookup efficiency by value, and O(n) for manipulation efficiency.

List<int> numbers= new List<int>() { "3", "12" , "7", "1" };
numbers.Sort();
numbers.Add(-5);
Console.WriteLine(numbers[1]);
Console.WriteLine(numbers.Last());

//This code produces the following output.
//3
//-5

 

4. Queue<T>

Queue<T> represents a first-in, first-out (FIFO) collection of objects. This collection only provides a single direction for an item to enter and out of the collection. It only exposes a single index for an item to be retrieved (head), and you can only add an item on the last index (tail).

Queue<T> has O(1) for lookup efficiency and O(1) for manipulation efficiency because it only exposes item on its head. 

 // Creates and initializes a new Queue.
Queue myQueue = new Queue();
myQueue.Enqueue("Hello");
myQueue.Enqueue("World");
myQueue.Enqueue("!");

// Displays the properties and values of the Queue.
Console.Write(myQueue.Dequeue() + " ");
Console.Write(myQueue.Dequeue() + " ");
Console.Write(myQueue.Dequeue());

// This code produces the following output.
// Hello World !

 

5. Stack<T>

Stack<T> represents a simple last-in-first-out (LIFO) non-generic collection of objects. This collection only provides a single index for an item to enter and out of the collection.

Stack<T> has O(1) for lookup efficiency and O(1) for manipulation efficiency because it only exposes item on the top of the stack. 

 // Creates and initializes a new Queue.
Stack<string> myStack = new Stack<string>();
myStack.Push("Hello");
myStack.Push("World");
myStack.Push("!");

// Displays the properties and values of the Queue.
Console.Write(myStack.Pop() + " ");
Console.Write(myStack.Pop() + " ");
Console.Write(myStack.Pop());

// This code produces the following output.
// ! World Hello

 

6. LinkedList<T>

LinkedList<T> represents the doubly linked list. Each node points forward to the Next node and backward to the Previous node. It is optimized for insertion and removal operations. Each node in a LinkedList<T> object is of the type LinkedListNode<T>. Unlike List<T>, LinkedList<T> can perform insertion and removal processes with O(1) complexity. This is possible because each node is independent to one another, and if an insertion or removal action occurs no list rearrangement is needed. The LinkedListNode<T> associated with the changes will update its Previous and Next property. However, keep in mind that List<T> is better than LinkedList<T> for operations that involve enumerating items such as sorting and searching. 

LinkedList<T> has O(n) for lookup efficiency, O(1) for manipulation efficiency. This type is best for lists where inserting/deleting in middle is common and no direct access required.

string[] words = { "a", "beautiful", "day" };
LinkedList<string> sentence = new LinkedList<string>(words);

sentence.AddFirst("what");
var beautifulNode = words.Find("beautiful");
sentence.AddBefore(beautifulNode, "very");
var lastNode = sentence.Last;
sentence.AddAfter(lastNode, "it is");

foreach (var word in words)
{
    Console.Write(word + " ");
}

// This code example produces the following output:
// what a very beautiful day it is 
 

 

7. Dictionary<TKey, TValue>

Dictionary<TKey, TValue> represents a generic collection of key/value pairs. Each element is a key/value pair stored in a KeyValuePair<TKey, TValue> object. Use this type if you are not interested in how the objects are ordered, and you are more concerned about how to quickly find the value of an object with a given key. Think of a list of citizens personal data in a particular country, you maybe don't really care how the citizens are ordered in the list, but if you need an information about someone you'd like to retrieve it quickly, for example, with a social security number. Note that duplicate keys are forbidden and will result in an ArgumentException.

Dictionary<TKey, TValue> has O(1) for lookup efficiency and O(1) for manipulation efficiency. This type has high-performance lookup and manipulation performance, but you should be aware that Dictionary<T> may consume more resource than Collection<T> or List<T>. 

// Create a new dictionary of strings, with string keys, 
// and access it through the IDictionary generic interface.
IDictionary<string, string> citizensPersonalData = 
new Dictionary<string, string>();

// Add some elements to the dictionary. There are no 
// duplicate keys, but some of the values are duplicates.
citizensPersonalData .Add("212384465", "William Oxford");
citizensPersonalData .Add("176389445", "John Doe");
citizensPersonalData .Add("567182930", "Peter Wong");
Console.WriteLine(citizensPersonalData["176389445"]);

foreach (var item in citizensPersonalData )
        {
            Console.WriteLine("{0} = {1}",
                p.Key,
                p.Value);
        }

// This code example produces the following output:
// 176389445 = John Doe
// 212384465 = William Oxford
// 567182930 = Peter Wong

 

8. SortedDictionary<T>

SortedDictionary<T> represents a collection of key/value pairs that are sorted by the key. Unlike Dictionary<TKey, TValue>, keys on SortedDictionary<T> are sorted. SortedDictionary<T> performs slower for insertion and removal operation compared to regular IDictionary<T>. However, it can be useful if you want the data to be sorted as well as could be accessed by keys. If compared to SortedList<T>, SortedDictionary<T> performs faster insertion and removal operations for unsorted data.

SortedDictionary<T> has O(log n) for lookup efficiency and O(log n) for manipulation efficiency. This type is best to use for a scenario where a collection of items need to remain sorted while still provides an ability to access its item with a key.

// Create a new dictionary of strings, with string keys, 
// and access it through the IDictionary generic interface.
SortedDictionary<string, string> citizensPersonalData = 
new SortedDictionary<string, string>();

// Add some elements to the dictionary. There are no 
// duplicate keys, but some of the values are duplicates.
citizensPersonalData .Add("176389445", "John Doe");
citizensPersonalData .Add("567182930", "Peter Wong");
Console.WriteLine(citizensPersonalData["176389445"]);

// This code example produces the following output:
// John Doe

 

9. SortedList<T>

SortedList<T> represents a collection of key/value pairs that are sorted by the keys and are accessible by key and by index. A SortedList element can be accessed by its key, or by its index. So basically it's like a mix of IList and IDictionary. The index sequence is based on the sort sequence. When an element is added, it is inserted into SortedList in the correct sort order, and the indexing adjusts accordingly. When an element is removed, the indexing also adjusts accordingly. Operations on a SortedList type tend to be slower than operations on a SortedDictionary type because of the sorting. However, the SortedList offers more flexibility by allowing access to the values either through the associated keys or through the indexes.

SortedList<T> has O(log n) for lookup efficiency and O(n) for manipulation efficiency. This type is best to use for a scenario where a collection of items need to remain sorted. Note that SortedList<T> may have slower load than a regular List<T>. 

 // Creates and initializes a new SortedList.
SortedList sortedList = new SortedList();
sortedList .Add("Second", "World");
sortedList .Add("Third", "!");
sortedList .Add("First", "Hello");

// Displays the properties and values of the SortedList.
Console.WriteLine( sortedList["First"]);
Console.WriteLine( sortedList[0]);
Console.WriteLine( sortedList["Third"]);
}

// This code example produces the following output:
// Hello
// World
// !

 

10. HashSet<T>

HashSet<T> represents a set of values. The HashSet<T> class provides high-performance set operations. If you still remember your high school mathematics subjects about sets on a Venn diagram, where you can do a union and intersect operation, this class is precisely designed for such thing. A set cannot contain duplicate elements, and the elements are in no particular order.

HashSet<T> provides many mathematical set operations, such as set addition (unions) and set subtraction. These are the provided HashSet<T> operations and their mathematical equivalents. 

 HashSet<int> evenNumbers = new HashSet<int>();
 HashSet<int> oddNumbers = new HashSet<int>();

 for (int i = 0; i < 5; i++)
 {
     // Populate numbers with just even numbers.
     evenNumbers.Add(i * 2);

     // Populate oddNumbers with just odd numbers.
      oddNumbers.Add((i * 2) + 1);
 }

// Create a new HashSet populated with even numbers.
HashSet<int> numbers = new HashSet<int>(evenNumbers);
Console.WriteLine("numbers UnionWith oddNumbers...");
numbers.UnionWith(oddNumbers);

foreach (var number in numbers)
{
Console.WriteLine(number);
}

 

Performance

I've read some interesting blog pages about C# Generic Collection Types performance comparison. One of them is written by Vladimir Bodurov, where he did a performance test for SortedList<T>, SortedDictionary<T>, Dictionary<T>, and HashTable. You can read his blog via this link

He performed a sequence of tests comparing the performance results for four different implementations of IDictionary and in particular generic Dictionary, generic SortedDictionary, the old non-generic Hashtable and generic SortedList. The test was performed in five stages, to observe the relationship between the number of entries and the performance. In the first stage, the collections had 50 items, in the second 500, in the third 5,000 in the fourth 50,000 items. The test was performed 8000 times for all the four implementations, and the order was random so each implementation has been tested at least 1000 times.

Another test was also performed by Dave Lozinski, where he compared string lookup speed for several C# Generic Collection Types. You can read more about his method of the testing in his blog post via this link. Various string length was tested from 100 strings, 5000 strings, 25.000 strings, and up to 100.000 strings. There was no much different to be seen at shorter length, but as soon the length is getting longer the difference is very significant.

Summary

Let's summarize what we've learned in a quick reference table.

Type Ordering Direct Access Lookup Efficiency Manipulation Efficiency
Array User has precise control over element ordering Via Index By Index : O(1) O(1)
Collection<T> User has precise control over element ordering Via Index By Index : O(1) O(1)
List<T> User has precise control over element ordering Via Index By Index : O(1)
By Value : O(n)
O(1)
Queue<T> First-in first-out Only Front Front : O(1) O(1)
Stack<T> Last-in first-out Only Top Top : O(1) O(1)
LinkedList<T> User has precise control over element ordering n/a By Value : O(n) O(1)
Dictionary<TKey, TValue> Unordered Via Key By Key : O(1) O(1)
SortedDictionary <TKey, TValue> Sorted Via Key By Key : O(log n)

O(log n)
SortedList<TKey, TValue> Sorted Via Key & Index By Key : O(log n)
By Index :
O(1)
O(n)
HashSet<T> Unordered Via Index O(1) O(1)