10.0 Prologue

System.Collections.Generic provides type-safe, generic collection classes that replace the non-generic ArrayList and Hashtable from the early .NET era. Choosing the right collection for a task dramatically affects both correctness and performance.

10.1 Collection Interfaces

The collection hierarchy is built on a small set of interfaces:

• IEnumerable<T> — supports foreach and LINQ
• ICollection<T> — adds Count, Add, Remove, Contains
• IList<T> — adds index access and IndexOf
• IReadOnlyList<T> — read-only index access
• IDictionary<TKey, TValue> — key-value access
• ISet<T> — set operations (union, intersect, except)

Code to the interface rather than the concrete type where possible — this makes it easy to swap implementations later.

10.2 List<T>

List<T> is a dynamically resizing array. It provides O(1) indexed access, O(1) amortized append, and O(n) insert/remove at arbitrary positions. var words = new List<string> { "cat", "dog", "fox" }; words.Add("owl"); words.Insert(1, "bee"); // ["cat","bee","dog","fox","owl"] words.Remove("dog"); words.Sort(); foreach (string w in words) Console.WriteLine(w); // LINQ var long_ = words.Where(w => w.Length > 3).ToList(); Capacity vs Count: Count is the number of items; Capacity is the allocated backing array size. Pre-set capacity with new List<T>(expectedCount) to avoid reallocations when the final size is known.

10.3 Dictionary<TKey, TValue>

Dictionary<TKey, TValue> is a hash table that provides O(1) average lookup, insert, and remove by key. Keys must implement GetHashCode() and Equals(); the default comparer uses these automatically. var freq = new Dictionary<string, int>(); string[] tokens = "the cat sat on the mat".Split(); foreach (string t in tokens) freq[t] = freq.GetValueOrDefault(t) + 1; foreach (var (word, count) in freq.OrderByDescending(p => p.Value)) Console.WriteLine($"{word}: {count}"); // safe lookup if (freq.TryGetValue("cat", out int n)) Console.WriteLine($"cat appears {n} times"); SortedDictionary<TKey, TValue> keeps keys sorted (O(log n) operations via a red-black tree). Use it when you need ordered iteration over keys.

10.4 HashSet<T> and SortedSet<T>

HashSet<T> stores unique elements with O(1) average Contains/Add/Remove. SortedSet<T> does the same in sorted order (O(log n)): var a = new HashSet<int> { 1, 2, 3, 4 }; var b = new HashSet<int> { 3, 4, 5, 6 }; var union = new HashSet<int>(a); union.UnionWith(b); var intersect = new HashSet<int>(a); intersect.IntersectWith(b); var diff = new HashSet<int>(a); diff.ExceptWith(b); Console.WriteLine(string.Join(",", intersect)); // 3,4

10.5 Queue<T> and Stack<T>

Queue<T> is a FIFO container. Stack<T> is LIFO. Both provide O(1) operations: var q = new Queue<string>(); q.Enqueue("first"); q.Enqueue("second"); string head = q.Dequeue(); // "first" bool hasNext = q.TryPeek(out string? next); var s = new Stack<int>(); s.Push(1); s.Push(2); int top = s.Pop(); // 2 PriorityQueue<TElement, TPriority> (C# 10 / .NET 6) dequeues the element with the lowest priority value, providing a min-heap.

10.6 LinkedList<T>

LinkedList<T> is a doubly linked list. O(1) insert and remove at any node when you already hold the LinkedListNode<T>, but O(n) indexed access. Use it when you need frequent mid-sequence insertions and deletions: var list = new LinkedList<int>(new[] { 1, 2, 4, 5 }); var node3 = list.Find(4)!; list.AddBefore(node3, 3); // 1 → 2 → 3 → 4 → 5

10.7 Concurrent Collections

System.Collections.Concurrent provides thread-safe collections that avoid coarse-grained locking:

• ConcurrentDictionary<TKey, TValue> — lock-free reads, fine-grained writes
• ConcurrentQueue<T> — lock-free FIFO
• ConcurrentStack<T> — lock-free LIFO
• ConcurrentBag<T> — unordered, per-thread storage optimized for same-thread produce/consume
• BlockingCollection<T> — bounded producer-consumer with blocking Add/Take

var counts = new ConcurrentDictionary<string, int>(); Parallel.ForEach(tokens, t => counts.AddOrUpdate(t, 1, (_, c) => c + 1));

10.8 Immutable Collections

System.Collections.Immutable (NuGet: System.Collections.Immutable, included in .NET 5+) provides collections that return new instances on mutation rather than modifying in place — safe to share across threads without locks: var list = ImmutableList<int>.Empty .Add(1).Add(2).Add(3); // ImmutableList<int> var list2 = list.Add(4); // original unchanged

10.9 Comparison with C++ STL Containers

C# Type	C++ Equivalent	Notes
List<T>	std::vector<T>	Dynamic array; O(1) append
LinkedList<T>	std::list<T>	Doubly linked list
Dictionary<K,V>	std::unordered_map<K,V>	Hash map; O(1) average
SortedDictionary<K,V>	std::map<K,V>	Tree map; O(log n)
HashSet<T>	std::unordered_set<T>	Hash set; O(1) average
SortedSet<T>	std::set<T>	Tree set; O(log n)
Queue<T>	std::queue<T>	FIFO
Stack<T>	std::stack<T>	LIFO
PriorityQueue<E,P>	std::priority_queue<T>	Min-heap (.NET) vs max-heap (C++)

10.10 Epilogue

This chapter covered the generic collection types in System.Collections.Generic and the concurrent and immutable variants. The final chapter looks at several advanced and interesting language features.

10.11 References

Commonly used collection types
System.Collections.Generic — API docs
System.Collections.Concurrent — API docs
Thread-safe collections