03.1 - Collections, Generics, LINQ

Recap

In 02.1 - OOP 1 and 02.2 - OOP 2 we built classes, interfaces, records and delegates. This lecture is about groups of objects: how to store a board, a move history or a set of blocked cells, how to write code that works for any element type, and how to query those groups with LINQ.

By the end of this lecture you should be able to:

• Pick a board representation ([,] vs [][]) and explain the trade-off.
• Use List<T>, Dictionary<TKey, TValue>, HashSet<T>, Stack<T> and Queue<T> for the right job.
• Write a generic class or method with constraints and explain what T is.
• Implement IEnumerable<T> with yield return, write an indexer and an extension method.
• Query collections with LINQ method syntax and explain deferred execution.

Demo code

Lecture demos: csharp-2026-fall

Arrays

An array is a fixed-size block of elements of one type. Every array derives from System.Array, is a reference type and lives on the heap — the variable holds a reference, not the elements. Arrays cannot grow; Array.Resize creates a new one and copies.

int[] numbers = new int[5];                        // 0 0 0 0 0
int[] primes = [2, 3, 5, 7];                       // collection expression
string[] names = new string[3];                    // three nulls - a nullable warning waiting to happen
Console.WriteLine($"{primes.Length} {primes[^1]}"); // 4 7  (^1 = index from the end)

Array.Fill(numbers, -1);                           // set every element
Array.Sort(primes);                                // in place
var index = Array.IndexOf(primes, 5);              // 2, or -1
var hasBig = Array.Exists(primes, p => p > 6);     // takes a Predicate<T>
int[] copy = (int[])primes.Clone();                // shallow copy

Clone() is shallow. For value-type elements (int, an enum) shallow is a real copy; for reference-type elements you copy only the references.

Board representation: [,] vs [][]

C# has two kinds of two-dimensional arrays. In this course a board is always indexed row first, column second — pick a convention and stick to it, the row/col swap is the most common board bug.

Rectangular array EGamePiece[,] — one block of memory, always rectangular.

public enum EGamePiece { Empty, X, O }

var board = new EGamePiece[6, 7];                    // [rows, cols] = height x width
var height = board.GetLength(0);                     // 6
var width = board.GetLength(1);                      // 7
board[5, 3] = EGamePiece.X;                          // bottom row, middle column
Console.WriteLine($"{board.Rank} {board.Length}");   // 2 42

for (var row = 0; row < board.GetLength(0); row++)
{
    for (var col = 0; col < board.GetLength(1); col++)
    {
        Console.Write(board[row, col] == EGamePiece.Empty ? "." : board[row, col].ToString());
    }
    Console.WriteLine();
}

Jagged array EGamePiece[][] — an array of row arrays. Each row is a separate object and could, in theory, have its own length.

var board = new EGamePiece[6][];
for (var row = 0; row < board.Length; row++)
{
    board[row] = new EGamePiece[7];                  // every row created separately
}
board[5][3] = EGamePiece.X;

var height = board.Length;                           // 6
var width = board[0].Length;                         // 7 - assumes at least one row

foreach (var row in board)                           // each row is a real array
{
    Console.WriteLine(string.Join(" ", row.Select(p => p == EGamePiece.Empty ? "." : p.ToString())));
}

Copying. Your AI (A5) will simulate moves on a copy of the board and your tests will compare boards, so know what a copy really is:

// rectangular: Clone gives a complete copy, because the elements are value types
var copy2D = (EGamePiece[,])board2D.Clone();

// jagged: Clone copies only the OUTER array - both boards share the same row objects!
var shallow = (EGamePiece[][])board.Clone();

// deep copy: clone every row
public static EGamePiece[][] Copy(EGamePiece[][] board)
{
    var copy = new EGamePiece[board.Length][];
    for (var row = 0; row < board.Length; row++)
    {
        copy[row] = (EGamePiece[])board[row].Clone();
    }
    return copy;
}

Which one? [,] matches the mental model and cannot become non-rectangular by accident. [][] indexes slightly faster and — the deciding argument — System.Text.Json cannot serialise [,] at all, it throws NotSupportedException. A3 stores game states as JSON, so the course examples use EGamePiece[][] for GameState.Board. Details and the flat-array alternative are in 04.1 - JSON.

tip

Whatever you choose, hide it. If only GameBrain touches the array and everybody else calls GetPiece(row, col), you can change the representation later without touching the UI or the tests.

Collections

Collections grow and shrink and come with behaviour. Five of them cover most everyday code:

• List<T> (Estonian: nimekiri) — ordered, indexed
• Dictionary<TKey, TValue> (sõnastik) — lookup by unique key
• HashSet<T> (hulk) — unique items, fast membership test
• Stack<T> (magasin, pinu) — last in, first out
• Queue<T> (järjekord) — first in, first out

All live in System.Collections.Generic (imported by implicit usings) and implement IEnumerable<T>, so foreach and LINQ work on every one of them. A List<T> is an array that gets replaced by a bigger one when full; Dictionary and HashSet are hash tables.

List<T> — the move history

List<(int Row, int Col)> moves = [];        // empty list, typed by the declaration
moves.Add((5, 3));                          // append
moves.Add((5, 4));
var last = moves[^1];                       // (5, 4)
var count = moves.Count;                    // Count, not Length
moves.RemoveAt(moves.Count - 1);            // undo the last move
var has = moves.Contains((5, 3));           // linear search
moves.Insert(0, (0, 0));                    // everything shifts right

foreach (var (row, col) in moves)           // deconstruct the tuple in the loop
{
    Console.WriteLine($"{row},{col}");
}

Index access is O(1); Contains, IndexOf and Remove scan the whole list. Fine for a move history, wrong for lookup tables.

Dictionary<TKey, TValue> — presets by name

public record GameConfiguration(string Name, int BoardWidth, int BoardHeight, int WinLength);

var presets = new Dictionary<string, GameConfiguration>
{
    ["Classic"] = new("Classic", 7, 6, 4),
    ["Connect3"] = new("Connect3", 5, 4, 3),
};

var classic = presets["Classic"];                 // KeyNotFoundException if missing
if (presets.TryGetValue("Mini", out var mini))    // safe lookup - mini is non-null inside the if
{
    Console.WriteLine(mini.Name);
}
presets["Mini"] = new("Mini", 4, 4, 3);           // add or overwrite
presets.Remove("Connect3");

foreach (var (name, config) in presets)           // KeyValuePair deconstructs
{
    Console.WriteLine($"{name}: {config.BoardWidth}x{config.BoardHeight}");
}

Keys are unique and must not be null. Lookup is O(1). Do not rely on iteration order — sort when order matters.

HashSet<T> — blocked cells

var walls = new HashSet<(int Row, int Col)> { (3, 3), (3, 4), (4, 3), (4, 4) };
var added = walls.Add((3, 3));               // false - already there
Console.WriteLine(walls.Contains((4, 4)));   // true, O(1)

var corners = new HashSet<(int Row, int Col)> { (0, 0), (0, 7), (7, 0), (7, 7) };
walls.UnionWith(corners);                    // also: IntersectWith, ExceptWith, IsSubsetOf, SetEquals

Equality decides what "already there" means. Tuples and records compare by value, so they just work. A class you wrote compares by reference until you override Equals and GetHashCode — see IEquatable<T> below.

Stack<T> and Queue<T>

var undo = new Stack<EGamePiece[][]>();
undo.Push(Copy(board));                      // before every move
if (undo.TryPop(out var previous))           // false when empty; Pop/Peek throw when empty
{
    board = previous;
}

var toVisit = new Queue<(int Row, int Col)>();
toVisit.Enqueue((0, 0));
while (toVisit.TryDequeue(out var cell))     // breadth-first search over neighbouring cells
{
    // handle the cell, enqueue its unvisited neighbours
}

Collection expressions and copies

int[] b = [.. moves.Select(m => m.Row), 4, 5];          // spread: copy, then append
var movesCopy1 = new List<(int Row, int Col)>(moves);   // new list, copied elements
var movesCopy2 = moves.ToList();                        // same via LINQ
List<(int Row, int Col)> movesCopy3 = [.. moves];       // same via spread

warning

Copying a List<Player> gives a new list holding the same Player objects. Change a player through one list and the other list sees it. A deep copy means copying the elements too — exactly the jagged-board problem from above.

Collection	Fast at	Good for	Watch out
List<T>	index access	move history, ordered data	search is linear, Insert/Remove shift elements
Dictionary<TKey, TValue>	lookup by key	presets by name, lookup tables	unique non-null keys; indexer throws on a missing key
HashSet<T>	membership test	blocked cells, visited cells	custom classes need Equals + GetHashCode
Stack<T>	push/pop at the top	undo, back navigation	Pop/Peek on empty throw — use TryPop
Queue<T>	enqueue/dequeue	BFS, jobs in arrival order	Dequeue on empty throws — use TryDequeue

Generics

List<int> and List<string> are the same code with a different element type. Generics let you write that code once: a type parameter T is a placeholder the caller fills in.

Generic class

public class History<T>
{
    private readonly List<T> _items = [];

    public int Count => _items.Count;
    public void Push(T item) => _items.Add(item);

    public T? Undo()
    {
        if (_items.Count == 0) return default;   // null for classes, zero-ish for structs
        var last = _items[^1];
        _items.RemoveAt(_items.Count - 1);
        return last;
    }
}

var moveHistory = new History<(int Row, int Col)>();
var boardHistory = new History<EGamePiece[][]>();

default is the "empty" value of T: null for reference types, 0/false/Empty for value types. Inside generic code you often do not know which — hence T?.

Generic method

public static class ArrayHelpers
{
    public static T[][] CreateJagged<T>(int rows, int cols)
    {
        var result = new T[rows][];
        for (var row = 0; row < rows; row++)
        {
            result[row] = new T[cols];
        }
        return result;
    }

    public static void Swap<T>(ref T a, ref T b) => (a, b) = (b, a);
}

var board = ArrayHelpers.CreateJagged<EGamePiece>(6, 7);   // explicit type argument
var x = EGamePiece.X;
var o = EGamePiece.O;
ArrayHelpers.Swap(ref x, ref o);                            // T inferred from the arguments

The compiler infers T from the arguments when it can. It cannot infer from a return type alone, so CreateJagged needs the explicit <EGamePiece>.

Generic interface

public interface IRepository<TKey, TEntity>
{
    List<TKey> List();
    TEntity Get(TKey id);
    void Save(TEntity entity);
    void Delete(TKey id);
}

public class ConfigRepositoryInMemory : IRepository<string, GameConfiguration> { /* closes both parameters */ }

The implementing class closes the type parameters; callers program against the interface. The course repositories in 04.2 - Files and Persistence are two non-generic interfaces because config and game lists return different things — the idea is the same.

Constraints

Without constraints T can be anything, so you can only call object members on it. A where clause promises more:

public static T Max<T>(T a, T b) where T : IComparable<T>      // T can be compared with itself
    => a.CompareTo(b) >= 0 ? a : b;

public static T[] AllValues<T>() where T : struct, Enum        // T is an enum
    => Enum.GetValues<T>();

var bigger = Max(3, 7);                      // 7
var pieces = AllValues<EGamePiece>();        // [Empty, X, O]

Constraint	Meaning
where T : class / struct	reference type / value type
where T : notnull	anything but null — needed for dictionary keys
where T : new()	has a public parameterless constructor
where T : SomeBase / where T : ISomething	derives from / implements

info

Naming: a single T when there is one parameter, descriptive TKey, TValue, TEntity when there are several.

Iterators and extension methods

IEnumerable<T> and yield return

foreach works on anything implementing IEnumerable<T>: the compiler calls GetEnumerator(), then MoveNext() and Current in a loop. Writing an enumerator class by hand is tedious, so an iterator method returns IEnumerable<T> and produces elements with yield return; the compiler builds the state machine.

public static IEnumerable<(int Row, int Col)> AllCells(EGamePiece[][] board)
{
    for (var row = 0; row < board.Length; row++)
    {
        for (var col = 0; col < board[row].Length; col++)
        {
            yield return (row, col);
        }
    }
}

var legalMoves = AllCells(board).Where(c => board[c.Row][c.Col] == EGamePiece.Empty).ToList();

Nothing inside an iterator runs until somebody enumerates it, and it stops as soon as the consumer stops — First() does not walk the whole board. yield break ends the sequence early.

warning

Adding to or removing from a List<T> while you foreach over it throws InvalidOperationException. Collect what to remove first, iterate over a copy ([.. list]), or use list.RemoveAll(predicate).

Indexers

An indexer lets your own class be used with [] — the natural API for a board wrapper:

public class Grid<T>(int height, int width)
{
    private readonly T[][] _cells = ArrayHelpers.CreateJagged<T>(height, width);

    public int Height => height;
    public int Width => width;

    public T this[int row, int col]
    {
        get => _cells[row][col];
        set => _cells[row][col] = value;
    }
}

var grid = new Grid<EGamePiece>(6, 7);
grid[5, 3] = EGamePiece.X;

IEquatable<T> and IComparable<T>

Records, record structs and tuples already compare by value. A class compares by reference until you say otherwise — and HashSet<T>, dictionary keys, Contains and Distinct all rely on it:

public class Cell(int row, int col) : IEquatable<Cell>
{
    public int Row => row;
    public int Col => col;

    public bool Equals(Cell? other) => other is not null && Row == other.Row && Col == other.Col;
    public override bool Equals(object? obj) => Equals(obj as Cell);
    public override int GetHashCode() => HashCode.Combine(Row, Col);
}

public record Player(string Name, int Wins) : IComparable<Player>
{
    public int CompareTo(Player? other) => other is null ? 1 : other.Wins.CompareTo(Wins); // most wins first
}

IComparable<T> defines the natural order used by Sort() and OrderBy() without a key.

tip

public readonly record struct Cell(int Row, int Col); gives value equality, a hash code, ToString and deconstruction in one line. Write the class version only to learn how it works.

Extension methods

An extension method is a static method that looks like an instance method on a type you cannot change — EGamePiece[][], string, IEnumerable<T>:

public static class BoardExtensions
{
    public static bool IsInside(this EGamePiece[][] board, int row, int col)
        => row >= 0 && row < board.Length && col >= 0 && col < board[row].Length;

    public static bool IsEmpty(this EGamePiece[][] board, int row, int col)
        => board.IsInside(row, col) && board[row][col] == EGamePiece.Empty;
}

if (board.IsInside(row, col) && board.IsEmpty(row, col)) { /* legal */ }   // reads like an instance method

Rules: a static class, a static method, the first parameter marked this, and a using for the namespace at the call site. All of LINQ is extension methods on IEnumerable<T> — that is why moves.Where(...) works on a list, an array and your iterator alike.

info

C# 14 adds extension members: an extension(EGamePiece[][] board) { ... } block inside a static class can declare methods and properties. Both forms are fine in this course; the classic this parameter is what most code uses.

LINQ

Language Integrated Query: extension methods on IEnumerable<T> (namespace System.Linq, imported by implicit usings) plus an optional SQL-like query syntax. The same code queries a list, an array, a dictionary, your iterator — and, in A4, a database table. LINQ is learning outcome L03 of this course.

Method syntax — the ones you will use

List<(int Row, int Col)> moves = [(5, 3), (5, 4), (4, 3), (5, 0), (3, 3)];

var leftColumn = moves.Where(m => m.Col == 0).ToList();          // filter
var rows = moves.Select(m => m.Row).ToList();                      // project -> List<int>
var anyTopRow = moves.Any(m => m.Row == 0);                        // false
var allInside = moves.All(m => board.IsInside(m.Row, m.Col));      // true
var inColumn3 = moves.Count(m => m.Col == 3);                      // 3
var first = moves.First();                                         // (5,3) - throws on empty
var firstLeft = moves.FirstOrDefault(m => m.Col == 0);             // (5,0) - or default (0,0)!
var sorted = moves.OrderBy(m => m.Row).ThenBy(m => m.Col).ToList();
foreach (var group in moves.GroupBy(m => m.Col))                   // IGrouping<int, (int Row, int Col)>
{
    Console.WriteLine($"column {group.Key}: {group.Count()} moves");
}
var rowSum = moves.Aggregate(0, (sum, m) => sum + m.Row);          // fold; Sum(m => m.Row) is the same
var pairs = moves.Zip(moves.Skip(1)).ToList();                     // (previous, next) pairs
var byIndex = moves.Select((m, i) => (Move: m, Index: i))
                   .ToDictionary(x => x.Index, x => x.Move);       // Dictionary<int, (int Row, int Col)>
var xCount = board.SelectMany(row => row).Count(p => p == EGamePiece.X);   // flatten rows, then count

var columns = Enumerable.Range(0, width);                          // 0 .. width-1
var emptyCells = Enumerable.Range(0, height)
    .SelectMany(row => Enumerable.Range(0, width).Select(col => (Row: row, Col: col)))
    .Where(c => board[c.Row][c.Col] == EGamePiece.Empty)
    .ToList();

FirstOrDefault on a list of value types returns (0, 0), not null — indistinguishable from a real move at the top-left corner. Check Any() first, or use a nullable element type.

Deferred execution

warning

Where, Select, OrderBy, GroupBy and friends do not run when you call them. They build a query that runs every time it is enumerated. ToList(), ToArray(), ToDictionary(), Count(), First(), Any(), Sum() run it.

var empties = AllCells(board).Where(c => board[c.Row][c.Col] == EGamePiece.Empty);
board[0][0] = EGamePiece.X;          // the query sees the board as it is when enumerated
var count1 = empties.Count();        // runs the query
var count2 = empties.Count();        // runs it AGAIN
var snapshot = empties.ToList();     // materialise once, reuse the list

Two classic bugs: a query captured before the board changed, and a query enumerated many times because it was stored in an IEnumerable<T> variable.

Query syntax

The same query with keywords. It compiles to the same method calls; it reads better for joins and multiple from clauses, otherwise most C# code uses method syntax.

var query =
    from move in moves
    where move.Col == 3
    orderby move.Row descending
    select (move.Row, move.Col);

var result = query.ToList();

Scanning board lines — LINQ vs a plain loop

Is there a line of length pieces of player starting at (row, col) in direction (dRow, dCol)?

public static bool IsLine(EGamePiece[][] board, int row, int col, int dRow, int dCol, int length, EGamePiece player)
    => Enumerable.Range(0, length)
        .Select(i => (Row: row + i * dRow, Col: col + i * dCol))
        .All(c => board.IsInside(c.Row, c.Col) && board[c.Row][c.Col] == player);

public static bool IsLineLoop(EGamePiece[][] board, int row, int col, int dRow, int dCol, int length, EGamePiece player)
{
    for (var i = 0; i < length; i++)
    {
        var r = row + i * dRow;
        var c = col + i * dCol;
        if (!board.IsInside(r, c) || board[r][c] != player) return false;
    }
    return true;
}

Both are correct. The LINQ version reads as the sentence "all cells of the line belong to the player". The loop allocates nothing — no enumerator, no delegate, no tuples. In the UI, in tests and in repositories that difference is irrelevant; inside a minimax search that calls this a million times per move it is measurable (Week 10 has the profiler). Rule of thumb: LINQ everywhere by default, plain loops in the code that runs millions of times.

info

LINQ over collections is "LINQ to Objects". In 07.1 - EF Core relationships & querying the same Where/Select/OrderBy is translated to SQL and run by the database — same syntax, different execution.

Self preparation QA

1. Why does the course use EGamePiece[][] instead of EGamePiece[,] for the board? — System.Text.Json cannot serialise multidimensional arrays; jagged arrays serialise as nested JSON arrays. Otherwise the two are interchangeable, and the choice should be hidden behind the engine's API.
2. What is the difference between a shallow and a deep copy of a jagged board? — Clone() copies the outer array only, so both boards share the same row arrays; a deep copy clones every row, and that is what an AI simulating moves needs.
3. When do you pick Dictionary<TKey, TValue> over List<T>? — When you look things up by a unique key (preset by name, game by id); a list is for ordered data you access by index or enumerate.
4. What must a custom class implement to behave correctly in a HashSet<T>? — Override Equals and GetHashCode consistently (typically via IEquatable<T>); or use a record / record struct, which gets value equality for free.
5. What does where T : IComparable<T> give you inside a generic method? — Permission to call CompareTo on values of type T; without a constraint only object members are available.
6. What happens when you call an iterator method that uses yield return? — Nothing yet; the compiler-generated state machine produces elements lazily, one per MoveNext, when the result is enumerated.
7. What is deferred execution and how does it bite you? — LINQ operators build a query that runs at enumeration time; it sees the data as it is then and reruns on every enumeration, so materialise with ToList() when you need a snapshot or reuse a result.
8. When is a plain loop better than LINQ? — In hot paths such as a minimax search, where LINQ's enumerators and delegates allocate on every call; everywhere else readability wins.