.NET Collections

Introduction

Sometimes, the proper choice of a collection can greatly impact the performance of your application. For example, there are collection types that are more appropriate for insertions, others that allow faster lookups, and so on. Plus, you must decide if you want indexed collections or not, and if you want to have generic collections, in order to have compile-time type checking. The .NET BCL comes with several general-purpose collection classes. Here is a list of all the collection classes as of .NET 9 and their intended use.

Namespaces

Namespace	Purpose
System.Collections	Basic types, non-generic collections and interfaces
System.Collections.Generic	Generic interfaces and collections
System.Collections.ObjectModel	Observable and read-only collections
System.Collections.Specialized	Specialised collections
System.Collections.Concurrent	Concurrent (thread-safe) collections (System.Collections.Concurrent Nuget package)
System.Collections.Immutable	Immutable collections (System.Collections.Immutable Nuget package)
System.Collections.Frozen	Frozen collections (System.Collections.Immutable Nuget package)

Concrete Types

Purpose	Types	Description
Fixed size	System.Array, System.Collections.Immutable.ImmutableArray<T>	Can have multiple dimensions
FIFOs (Queues)	System.Collections.Queue, System.Collections.Generic.Queue<T>, System.Collections.Concurrent.ConcurrentQueue<T>, System.Collections.Immutable.ImmutableQueue<T>	First in, first out
Priority Queue	System.Collections.Generic.PriorityQueue<TElement,TPriority>	A queue that respects the given priority. Does not implement any of the standard interfaces, but is similar to the queue interface, except that it requires a priority
LIFOs (Stacks)	System.Collections.Stack, System.Collections.Generic.Stack<T>, System.Collections.Concurrent.ConcurrentStack<T>, System.Collections.Immutable.ImmutableStack<T>	Last in, first out
Linked lists	System.Collections.Generic.LinkedList<T>	Random inserts and deletes at any point
Array-based	System.Collections.ArrayList, System.Collections.Generic.List<T>, System.Collections.Concurrent.ConcurrentBag<T>, System.Collections.Immutable.ImmutableList<T>
Customizable	System.Collections.ObjectModel.Collection<T>	Can override InsertItem, RemoveItem, SetItem and ClearItems to implement custom algorithms
Thread-safe	System.Collections.Generic.SynchronizedCollection<T>, System.Collections.Generic.SynchronizedReadOnlyCollection<T>	Thread-safe
Read-only	System.Collections.ObjectModel.ReadOnlyCollection<T>, System.Collections.Generic.SynchronizedReadOnlyCollection<T>, System.Collections.ObjectModel.ReadOnlyObservableCollection<T>, System.Collections.ObjectModel.ReadOnlySet<T>	Wrap existing (not read-only collections)
Sorted	System.Collections.SortedList, System.Collections.Generic.SortedList<K, V>, System.Collections.Generic.SortedDictionary<K, V>, System.Collections.Generic.SortedSet<T>, System.Collections.Generic.OrderedDictionary<K, V>	Sorted by key
Sets	System.Collections.Generic.HashSet<T>, System.Collections.SortedSet<T>, System.Collections.Immutable.ImmutableSortedSet<T>, System.Collections.Immutable.ImmutableHashSet<T>, System.Collections.Frozen.FrozenSet<T> System.Collections.ObjectModel.ReadOnlySet<T>	No repetition of elements
Keyed	System.Collections.Specialized.ListDictionary (for <=10 items), System.Collections.Generic.Dictionary<K, V>, System.Collections.Generic.OrderedDictionary<K, V>, System.Collections.Hashtable (index by hash), System.Collections.Generic.KeyedByTypeCollection<T> (index by type), System.Collections.Specialized.HybridDictionary (changes depending on number of elements, ListDictionary -> Hashtable), System.Collections.Specialized.OrderedDictionary (access by key or index), System.Collections.Immutable.ImmutableDictionary<K, V>, System.Collections.Concurrent.ConcurrentDictionary<K, V>, System.Collections.Immutable.ImmutableSortedDictionary<K, V>, System.Collections.Frozen.FrozenDictionary<K, V>	Single value per key
Multiple values for a single key	System.Collections.Specialized.NameValueCollection	Can store multiple values per key
Bits	System.Collections.BitArray, System.Collections.BitVector32 (up to 32 bits only)	Bit operations
Strings	System.Collections.Specialized.StringDictionary, System.Collections.Specialized.StringCollection	Strings
Observable	System.Collections.ObjectModel.ObservableCollection<T>, System.Collections.ObjectModel.ReadOnlyObservableCollection<T>	Identical to System.Collections.ObjectModel.Collection<T>, fires events upon adding, removing, modifying or clearing.
Concurrent	System.Collections.Concurrent.BlockingCollection<T>, System.Collections.Concurrent.ConcurrentBag<T>, System.Collections.Concurrent.ConcurrentDictionary<K, V>, System.Collections.Concurrent.ConcurrentQueue<T>, System.Collections.Concurrent.ConcurrentStack<T>	Thread-safe, lock-free
Immutable	System.Collections.Immutable.ImmutableDictionary<K, V>, System.Collections.Immutable.ImmutableHashSet<T>, System.Collections.Immutable.ImmutableList<T>, System.Collections.Immutable.ImmutableQueue<T>, System.Collections.Immutable.ImmutableSortedDictionary<K, V>, System.Collections.Immutable.ImmutableSortedSet<T>, System.Collections.Immutable.ImmutableStack<T>, System.Collections.Immutable.ImmutableArray<T>	Immutable collections (see http://msdn.microsoft.com/en-us/library/dn385366.aspx)
Frozen	System.Collections.Frozen.FrozenSet<T>, System.Collections.Frozen.FrozenDictionary<K, V>	Frozen collections

Interfaces

Of course, you should not expose a collection class directly because it couples you to a an implementation, instead you should use collection interfaces, all these classes implement (at least) one of them). These interfaces are:

Purpose	Types
Enumerate only	System.Collections.IEnumerable, System.Collections.IEnumerable<T>, System.Linq.IOrderedEnumerable<T>, System.Linq.ILookup<K, E> (multiple values per key)
Enumerate, count	System.Collections.ICollection, System.Collections.Generic.ICollection<T>
Indexed access, add/remove (where not read-only or immutable)	System.Collections.IList, System.Collections.Generic.IList<T>, System.Collections.Immutable.IImmutableList<T>, System.Collections.Generic.IReadOnlyList<T>, System.Collections.Generic.IReadOnlyCollection<T>
Keyed	System.Collections.IDictionary, System.Collections.Specialized.IOrderedDictionary, System.Collections.Generic.IDictionary<K, V>, System.Collections.Generic.IReadOnlyDictionary<K, V>, System.Collections.Immutable.IImmutableDictionary<K, V>
FIFOs (Queues)	System.Collections.Immutable.IImmutableQueue<T>
LIFOs (Stacks)	System.Collections.Immutable.IImmutableStack<T>
Sets	System.Collections.Generic.ISet<T>, System.Collections.Immutable.IImmutableSet<T>, System.Collections.Generic.IReadOnlySet<T>

Frozen vs Immutable vs Read Only Collections

The difference between frozen and immutable is: frozen collections start as mutable, allowing you to add content to them, and once you are done adding or modifying elements, you can freeze the collection, thus making it immutable. Frozen collections are faster than the others. Read only are just that, read only. Read more here and here.

Best Practices

Some recommendations for using collections:

• Always prefer generic collections (should be obvious by now!);
• Always expose collections in properties, not arrays, and always collections with the less access possible (enumerate only, or read-only access to elements);
• All collections except synchronized and concurrent are not thread-safe;
• When using a collection where you need random inserts/removes at specific positions, prefer a linked list over an array-based implementation, as the latter requires constant allocations and copies;
• Choose a collection that better suits your intent (no repetition of items, indexed, always sorted, ...);
• Collections that rely on object identity (hashed/keyed collections) may need proper implementation of Equals or GetHashCode methods; the implementation of the two should be consistent;
• For customized object equality comparison, a custom implementation of System.Collections.Generic.IEqualityComparer<T> or System.Collections.IEqualityComparer may be passed on the constructor;
• For sorted collections, a custom implementation of System.Collections.Generic.IComparer<T> or System.Collections.IComparer may be passed on the constructor (System.Collections.Comparer, System.Collections.CaseInsensitiveComparer are default implementations);
• Indexed and sorted collections rely on a proper, consistent and stable implementation of GetHashCode. It cannot ever change for the same object, or things may go wrong with the collection - object may not be found, for example;
• If number of elements is known beforehand, use the constructor that specifies the initial capacity; if it can decrease in size, choose an linked-list based one;
• Immutable collections always return new objects when adding or removing from an existing one;
• Cannot add or remove from a frozen collection;
• Avoid using value types for elements, except for keys, because they need to be copied bit by bit, unlike with reference types, where only their pointer is copied.

Performance

Some tips regarding performance:

• For iterating, array-based collections are faster;
• Prefer using foreach to iterate through a array, or, in general, any collection, unless it's an indexed one (List<T>, Dictionary<K, V>, etc);
• In a for loop, do not cache the Length or Count values, no need, and can in fact be worse;
• Fastest way to loop over a List<T> is by using CollectionsMarshal.AsSpan.