Collections and Generics

1Why Generics Exist

Before generics (.NET 1.x), collections stored everything as object:

var list = new System.Collections.ArrayList();
list.Add(42);        // int boxed into an object on the heap
list.Add("oops");    // compiles fine — no type safety
int x = (int)list[0]; // cast + unbox on every read

Generics let a type or method be parameterized by another type, checked at compile time:

var list = new List<int>();
list.Add(42);
// list.Add("oops"); // compile error
int x = list[0];     // no cast, no unboxing

Two wins at once: type safety (wrong types don't compile) and performance (no boxing for value types — see Under the Hood).

2The Core Collections

var ages = new Dictionary<string, int> { ["ana"] = 31, ["bo"] = 27 };

if (ages.TryGetValue("ana", out int age))   // one lookup, no exception
    Console.WriteLine(age);

ages["cy"] = 40;          // insert or overwrite
// ages.Add("cy", 41);    // throws: key already exists

var seen = new HashSet<string>();
bool isNew = seen.Add("x"); // true first time, false on duplicate

3The Interface Hierarchy

IEnumerable<T>                 // can be iterated (foreach, LINQ)
  └─ IReadOnlyCollection<T>    // + Count
       └─ IReadOnlyList<T>     // + indexer (read-only)
  └─ ICollection<T>            // + Add/Remove/Clear/Count
       └─ IList<T>             // + indexer, Insert, RemoveAt

Accept the narrowest interface you need, return the most useful honest one:

// accepts arrays, lists, sets, LINQ queries...
static int Total(IEnumerable<int> values) => values.Sum();

// callers can index and count, but can't mutate your internal list
public IReadOnlyList<Order> Orders => _orders;

4Writing Generic Types and Methods

public class Box<T>
{
    public T Value { get; }
    public Box(T value) => Value = value;
}

public static T Max<T>(T a, T b) where T : IComparable<T>
    => a.CompareTo(b) >= 0 ? a : b;

Max(3, 7);         // T inferred as int
Max("a", "b");     // T inferred as string

5Constraints

Constraints are what let you call members on T — without IComparable<T> above, a.CompareTo(b) wouldn't compile, because the compiler only knows T is "some object."

6Variance: out and in

IEnumerable<string> names = new List<string> { "a" };
IEnumerable<object> objs = names;    // OK: IEnumerable<out T> is covariant

Action<object> printAny = o => Console.WriteLine(o);
Action<string> printStr = printAny;  // OK: Action<in T> is contravariant

List<object> bad = new List<string>(); // compile error: List<T> is invariant

List<T> must be invariant: if a List<string> could be treated as List<object>, you could Add(42) into a list of strings. IEnumerable<T> only produces T (out), so widening it is safe.

Under the HoodReified Generics and Code Sharing▾

Unlike Java's type erasure, .NET generics are reified: List<int> and List<string> are distinct runtime types, and typeof(T) works inside generic code.

The JIT compiles generic code differently depending on the type argument:

• Value types get their own specialized native code per type. List<int> stores a raw int[] — 4 bytes per element, no boxing, no pointer chasing. List<double> gets separate machine code with 8-byte slots.
• Reference types share one copy of native code (compiled for __Canon), since every reference is the same pointer size. A hidden "generic dictionary" passes the exact type when it's needed (e.g. for typeof(T) or new T()).

Dictionary<TKey,TValue> itself is an array of int buckets plus an array of entries (hashCode, next, key, value). A key's hash picks a bucket; the bucket stores the index of the first entry, and collisions chain through next. When Count exceeds capacity the table resizes to the next prime and every entry is re-bucketed — which is why passing a capacity (new Dictionary<,>(10_000)) avoids repeated rehashing when you know the size up front.

⚠️ Common Pitfalls

1. Mutating a collection while iterating it — foreach over a List<T> then calling Remove throws InvalidOperationException ("Collection was modified"). Iterate a copy, use RemoveAll, or loop backwards with an index.
2. Mutable keys in a Dictionary/HashSet. Changing a field that participates in GetHashCode after insertion strands the entry in the wrong bucket — it becomes unfindable.
3. Overriding Equals without GetHashCode (or vice versa). Hash collections call GetHashCode first; inconsistent pairs break lookups. Records generate both correctly.
4. dict[key] for a key that may be missing — throws KeyNotFoundException. Use TryGetValue.
5. Exposing List<T> publicly — callers can mutate your internal state. Expose IReadOnlyList<T> instead.
6. Using List<T>.Contains in a loop — O(n) each time, O(n²) overall. Build a HashSet<T> once.

📋 Quick Reference

🎤 Interview Q&A

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

Source: cs_collections_and_generics_theory.md · generated by tools/build_lessons.py