# Collections and Generics

## 1. Why Generics Exist

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

```csharp
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:

```csharp
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).

## 2. The Core Collections

| Type | Shape | Lookup | Insert | Notes |
|---|---|---|---|---|
| `List<T>` | dynamic array | O(1) by index | O(1) amortized at end, O(n) in middle | default choice for ordered data |
| `Dictionary<TKey,TValue>` | hash table | O(1) avg by key | O(1) avg | key needs good `GetHashCode`/`Equals` |
| `HashSet<T>` | hash table, keys only | O(1) avg `Contains` | O(1) avg | uniqueness, set algebra |
| `Queue<T>` | circular buffer | — | O(1) `Enqueue`/`Dequeue` | FIFO |
| `Stack<T>` | array | — | O(1) `Push`/`Pop` | LIFO |
| `LinkedList<T>` | doubly linked | O(n) | O(1) given a node | rarely the right answer |
| `SortedDictionary<TKey,TValue>` | red-black tree | O(log n) | O(log n) | keys iterate in order |

```csharp
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
```

## 3. The 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:

```csharp
// 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;
```

## 4. Writing Generic Types and Methods

```csharp
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
```

## 5. Constraints

| Constraint | Meaning |
|---|---|
| `where T : class` | reference type |
| `where T : struct` | non-nullable value type |
| `where T : new()` | has a public parameterless constructor |
| `where T : SomeBase` | derives from `SomeBase` |
| `where T : IFoo` | implements `IFoo` |
| `where T : notnull` | non-nullable (value or reference) |

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."

## 6. Variance: `out` and `in`

```csharp
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 Hood: Reified 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()`).

![List<int> stores raw 4-byte ints inline in its backing array, while ArrayList stores pointers to separately boxed int objects on the heap](diagrams/01-boxing-vs-generic-storage.svg)

`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

| Need | Use |
|---|---|
| ordered, indexed | `List<T>` |
| key → value | `Dictionary<TKey,TValue>` |
| uniqueness / membership | `HashSet<T>` |
| FIFO / LIFO | `Queue<T>` / `Stack<T>` |
| sorted by key | `SortedDictionary<TKey,TValue>` |
| expose read-only | `IReadOnlyList<T>` / `IReadOnlyDictionary<TKey,TValue>` |
| safe lookup | `TryGetValue` |
| generic method | `T Foo<T>(T x) where T : ...` |