Revisiting C# Data Structures and Algorithms: From First Principles to Practice

If you are learning C# with me, this is the article I want you to keep open beside your editor.

Data structures and algorithms are our bread and butter. Frameworks change, cloud platforms add new services and fashionable architecture terms come and go, but every application still stores data, searches it, transforms it, orders it and moves it through memory. The choices you make at that level determine whether code remains clear and fast when ten records become ten million.

I am writing this as Faz Ahmed speaking to a junior developer, but I will not keep you at junior depth. We will begin with types and memory, move through the collections you use every day, learn the classic structures underneath them, analyse algorithms with Big O, and finish with the judgement expected from a strong senior engineer using C# 14 and .NET 10.

My first promise is that you do not need to memorise hundreds of algorithms. You need to understand a few models deeply enough to reason from them.

What data do I have?
Which operations dominate?
How large can it become?
What ordering or uniqueness rules exist?
What are the memory and concurrency constraints?
Which standard .NET collection already expresses those requirements?

Answer those questions and the structure often chooses itself.

How to use this course

Do not try to read this like a list of facts. Keep a console project open and type the examples yourself. Change the values, predict the output before running the code, and deliberately break things. That is how a definition becomes understanding.

The course has five connected stages:

1. Values and memory: what C# stores and what assignment means.
2. Complexity and collections: how data size changes performance and how .NET collections organise data.
3. Classic algorithms and structures: sorting, searching, recursion, trees, heaps and graphs.
4. Problem-solving patterns: reusable ways to reduce repeated work.
5. Production judgement: ownership, concurrency, measurement and choosing under real constraints.

Every later stage builds on the earlier ones. If a term feels unfamiliar, pause at that section and run its smallest example before continuing.

---

Part I — Values, types and memory

Before choosing a data structure, we must understand what the structure stores. That starts with C# types and assignment.

1. Start with the C# type system

C# is statically typed. The compiler knows the type of each expression and rejects many invalid operations before the program runs. var does not make a variable dynamically typed; it asks the compiler to infer the static type.

var orderCount = 12;       // int
var customer = new Customer("A102", "Maya"); // Customer

The fundamental division is between value types and reference types.

A variable of a value type contains its value. Assigning it copies that value. Built-in numbers, bool, char, enums, structs and record structs are value types.

int original = 10;
int copy = original;
copy++;

Console.WriteLine(original); // 10

A variable of a reference type contains a reference to an object. Assigning it copies the reference, so two variables can refer to the same object. Classes, records, arrays, delegates and strings are reference types.

var first = new List<int> { 10 };
var second = first;
second.Add(20);

Console.WriteLine(first.Count); // 2

Here is an important correction to a common beginner explanation: do not reduce this to “value types are on the stack and reference types are on the heap.” Storage depends on context and runtime optimisation. A value-type field inside a class lives as part of that heap object. A local reference may be tracked in a register. Boxing puts a value inside an object on the managed heap. The useful semantic distinction is copy-the-value versus copy-the-reference.

Walk through assignment slowly

Think of a value-type variable as a box containing a value. Copying the variable creates another box with its own copy:

int a = 10;
int b = a;  // Copy 10 into b.
b = 99;     // Replace only b's value.

Console.WriteLine(a); // 10
Console.WriteLine(b); // 99

Think of a reference-type variable as a label that tells the runtime where an object is. Copying the variable creates another label pointing to the same object:

public sealed class Counter
{
    public int Value { get; set; }
}

var first = new Counter { Value = 10 };
var second = first;       // Both references identify the same Counter.
second.Value = 99;

Console.WriteLine(first.Value); // 99

This distinction explains many beginner surprises. Passing a list to a method does not copy the whole list. The method receives a copy of the reference, so it can still mutate the shared list object.

static void AddExample(List<int> values)
{
    values.Add(42);
}

var numbers = new List<int>();
AddExample(numbers);
Console.WriteLine(numbers.Count); // 1

The reference itself was passed by value, but both references identify the same list. Later, when we discuss mutable collections and API ownership, this model will matter.

Equality is a separate question

Assignment asks, “what gets copied?” Equality asks, “when do two values count as the same?” Ordinary classes use reference identity by default; records use value-based equality by default.

public sealed class CustomerClass(string name)
{
    public string Name { get; } = name;
}

public sealed record CustomerRecord(string Name);

Console.WriteLine(new CustomerClass("Maya") == new CustomerClass("Maya")); // False
Console.WriteLine(new CustomerRecord("Maya") == new CustomerRecord("Maya")); // True

We will return to equality when studying dictionaries and sets because their correctness depends on it.

Check your understanding: if two variables refer to the same List, how many list objects exist? One. How many reference variables exist? Two.

object, dynamic, classes, interfaces and delegates

The source material introduces these C# building blocks because data structures are generic containers of values and often depend on abstractions. Let us connect the terms rather than leaving them as vocabulary.

object is the ultimate base type of ordinary C# types. A variable typed as object can refer to many different values, but you must inspect or convert it before using type-specific members:

object value = "hello";

if (value is string text)
    Console.WriteLine(text.Length);

Putting a value type such as int into an object variable causes boxing: the value is wrapped in an object representation. Unboxing extracts it with the correct type. Generic collections such as List avoid the boxing that older non-generic collections required.

object boxed = 42;
int number = (int)boxed;

dynamic postpones member checking until runtime:

dynamic unknown = "hello";
Console.WriteLine(unknown.Length); // Resolved at runtime.

This is useful at some interoperability boundaries, but it removes compile-time protection. It is not a faster or more flexible replacement for well-designed static types.

A class defines data and behaviour for objects. An interface defines a capability without committing callers to one implementation:

public interface IHasPriority
{
    int Priority { get; }
}

public sealed class SupportTicket : IHasPriority
{
    public required string Title { get; init; }
    public int Priority { get; init; }
}

Algorithms often accept interfaces such as IEnumerable, IComparer or IEqualityComparer so the same logic works with several concrete types and policies.

A delegate is a type-safe reference to a method. It lets us pass behaviour as data:

static bool IsUrgent(SupportTicket ticket) => ticket.Priority <= 2;

Predicate<SupportTicket> rule = IsUrgent;
bool urgent = rule(new SupportTicket { Title = "System down", Priority = 1 });

LINQ predicates, comparison functions, callbacks and graph neighbour functions all use this idea. A lambda such as ticket => ticket.Priority <= 2 is a concise way to create compatible delegate behaviour.

The progression is now connected: classes create values, interfaces describe capabilities, delegates pass behaviour, and generic structures use type parameters to remain reusable without abandoning compile-time safety.

2. Choosing numeric and domain types

Use int for ordinary whole-number counts and indexes unless the range requires long. Use decimal for base-10 financial calculations where its representation and rounding behaviour fit the business rule. Use double for general scientific and engineering floating-point work. Never compare floating-point calculations blindly for exact equality.

decimal net = 19.99m;
decimal taxRate = 0.20m;
decimal gross = decimal.Round(net * (1 + taxRate), 2, MidpointRounding.ToEven);

The rounding mode is a business decision, not a formatting detail.

Enums provide named integral constants, but validate values arriving from outside the process because any underlying integer can be cast to an enum.

public enum OrderStatus
{
    Draft,
    Submitted,
    Paid,
    Cancelled
}

if (!Enum.IsDefined(status))
    throw new ArgumentOutOfRangeException(nameof(status));

For important domain concepts, prefer a small validated type over repeated primitive strings:

public readonly record struct CustomerId
{
    public string Value { get; }

    public CustomerId(string value)
    {
        ArgumentException.ThrowIfNullOrWhiteSpace(value);
        Value = value.Trim().ToUpperInvariant();
    }

    public override string ToString() => Value;
}

The record struct has value semantics, and readonly prevents accidental mutation of its fields. Keep structs small and cohesive. Copying a huge struct repeatedly can cost more than passing a reference.

Choose a type from the meaning, not just the size

Start by asking what the value represents:

Floating-point values are approximations. This is not a C# bug; many decimal fractions cannot be represented exactly in binary:

double result = 0.1 + 0.2;
Console.WriteLine(result == 0.3); // Usually False

bool closeEnough = Math.Abs(result - 0.3) < 0.000_001;
Console.WriteLine(closeEnough); // True

For money, decimal avoids many base-10 representation surprises, but you still need an explicit rounding rule and must decide when rounding occurs.

Primitive obsession means representing every domain concept with string, int or decimal. The compiler cannot stop you from passing an OrderId where a CustomerId belongs if both are plain strings. Small domain types make such mistakes harder.

Try it: create separate CustomerId and OrderId record structs. Attempt to pass an OrderId to a method expecting CustomerId and observe the compiler protect you.

3. Nullability, records and modern properties

Nullable reference types let the compiler help distinguish “a value should exist” from “absence is allowed.” Turn them on and treat warnings as design feedback.

public sealed record Customer(
    CustomerId Id,
    string Name,
    string? MiddleName);

Records provide concise data-centric types with value-based equality. A record class remains a reference type; a record struct is a value type. Do not choose records simply for shorter syntax. Choose equality semantics that match the domain.

C# 14’s field keyword allows validation in a property accessor without declaring the backing field yourself:

public sealed class Product
{
    public required string Name
    {
        get;
        init => field = string.IsNullOrWhiteSpace(value)
            ? throw new ArgumentException("Name is required.", nameof(value))
            : value.Trim();
    }
}

required tells callers the member must be initialised. init prevents ordinary reassignment afterwards. Neither replaces domain validation, as the example demonstrates.

Absence must be part of the contract

With nullable reference types enabled, string means callers should supply text and string? means absence is allowed. The feature produces compiler warnings; it does not add a runtime wrapper around every reference.

static int GetDisplayLength(string? middleName)
{
    if (middleName is null)
        return 0;

    return middleName.Length; // Safe after the null check.
}

The null-forgiving operator, as in name!.Length, silences the compiler but performs no check. Use it only when you genuinely know something the compiler cannot prove. Habitually adding ! throws away the safety you enabled.

Class, record class or record struct?

• Use a class when identity and controlled changing state are central.
• Use a record class for reference-type data whose equality should come from its values.
• Use a record struct for a small value-like concept where copying is appropriate.

There is no universal winner. A customer entity can change its address while remaining the same customer, so identity may matter. A coordinate such as (x, y) is naturally a value.

Check your understanding: required ensures object initialiser participation; validation ensures the supplied value is acceptable. You usually need both.

4. Strings are immutable sequences

string is a reference type with value-like equality and immutability. Operations that appear to modify it produce a new string.

Repeated concatenation in a loop can create many temporary objects:

var builder = new StringBuilder(capacity: 256);

foreach (var item in items)
{
    builder.Append(item.Code).Append(':').AppendLine(item.Name);
}

string result = builder.ToString();

For a small interpolation, $"{first} {last}" is perfectly clear and efficiently handled. Reach for StringBuilder when the output grows through many operations, and reach for spans when parsing or slicing hot-path text without allocating substrings.

String comparison must express intent. User-facing culture-aware sorting differs from an identifier comparison:

bool sameKey = string.Equals(left, right, StringComparison.OrdinalIgnoreCase);

Use an explicit comparer in dictionaries and sets as well. Hashing and equality must agree.

See immutability happen

string original = "hello";
string upper = original.ToUpperInvariant();

Console.WriteLine(original); // hello
Console.WriteLine(upper);    // HELLO

ToUpperInvariant did not modify the original string. It returned another string. Immutability makes strings safe to share, but repeated transformations can allocate many temporary objects.

string csv = string.Empty;

for (int i = 0; i < 1_000; i++)
    csv += i + ","; // Repeatedly creates growing strings.

StringBuilder owns a resizable character buffer, so repeated appends avoid copying the whole accumulated result on every iteration.

Comparison is also a correctness decision:

var usernames = new HashSet<string>(StringComparer.OrdinalIgnoreCase)
{
    "Faz"
};

Console.WriteLine(usernames.Contains("FAZ")); // True

Choose culture-aware comparison for human language and ordinal comparison for machine-facing identifiers unless the domain says otherwise.

---

Now that assignment, equality and immutability are clear, we can follow the values into the runtime and understand the cost of storing them.

5. What the runtime does with your code

C# source is compiled into Common Intermediate Language and metadata in an assembly. At runtime, the Common Language Runtime loads types, verifies and executes code, manages exceptions, threads and garbage collection. The just-in-time compiler turns methods into native machine code as they execute. Tiered compilation can begin quickly and later optimise frequently used code. Native AOT is another deployment option for suitable workloads, trading some dynamic capabilities for ahead-of-time native compilation and startup benefits.

.NET 10 improves JIT inlining, devirtualisation, stack allocation opportunities, loop optimisation and code generation. That is good news, but it does not excuse poor algorithmic choices. A brilliantly optimised O(n²) loop still loses to a suitable O(n log n) or O(n) approach as input grows.

From source code to running instructions

The journey is:

C# source code
    ↓ compiler
CIL instructions + metadata in a .dll or .exe
    ↓ CLR loads the assembly
JIT compiler produces native machine instructions
    ↓
CPU executes those instructions

Metadata describes types and members. CIL is a CPU-independent instruction format. The JIT compiles a method when the runtime needs it, allowing optimisation for the actual machine. Tiered compilation balances fast startup with better optimisation for hot methods.

Native AOT performs more compilation before deployment. That can improve startup and reduce some deployment overhead, but features relying heavily on runtime code generation or reflection may require extra work. Treat it as a deployment choice, not an automatic upgrade.

Why teach this in a data-structures course? Because the same source-level operation can have very different runtime effects. Iterating a contiguous array, following linked nodes, allocating temporary objects and invoking virtual methods all interact differently with the CPU and runtime.

6. Managed memory without myths

The CLR garbage collector is an automatic memory manager. New reference objects are normally allocated on the managed heap. The GC starts from roots such as active locals, static fields, registers and GC handles, follows reachable objects and reclaims those it cannot reach.

The managed heap uses generations based on the observation that most new objects die young:

• generation 0 holds new, short-lived objects;
• generation 1 is a buffer between short and long life;
• generation 2 holds longer-lived survivors;
• large objects, normally 85,000 bytes and above, use the large object heap and are collected with generation 2.

Collections can pause managed threads. Allocation itself is usually fast; allocation volume and object survival create GC work. Do not respond by avoiding every allocation. Measure first. Clear code allocating short-lived objects may be entirely healthy.

A managed memory leak is still possible. The GC cannot reclaim an object that remains reachable, even if your application no longer needs it. Common causes include static collections, event subscriptions, unbounded caches and timers.

IDisposable is not a mechanism for forcing GC. It represents deterministic release of resources such as file handles, sockets, database connections or pooled buffers.

await using var stream = File.OpenRead(path);
// The stream is disposed even if processing throws.

Avoid calling GC.Collect() in ordinary application code. The runtime generally has better information about collection timing.

Reachability, not usefulness

The garbage collector cannot know whether an object is useful to your business. It knows only whether the object is reachable from a root.

public static class CustomerCache
{
    public static readonly List<Customer> Customers = [];
}

If this static list grows forever, every customer in it remains reachable. The GC is working correctly when it keeps them. The application has an ownership and lifetime bug.

Allocation and collection are different events

Creating a small object usually advances a pointer in managed memory and is cheap. Later, collection requires the runtime to find live objects and reclaim or compact space. Objects that survive repeatedly may move to older generations because the runtime assumes they are likely to remain alive.

Do not turn generations into manual storage choices. You normally control lifetimes by releasing references, bounding caches, unsubscribing events and disposing external resources.

publisher.Changed += HandleChanged;

// When this subscriber's lifetime ends:
publisher.Changed -= HandleChanged;

Disposal answers a different problem

Memory is managed; an operating-system file handle is scarce external state. using ensures Dispose runs even when an exception occurs:

using FileStream stream = File.OpenRead("orders.json");
// Read the file here.
// Dispose runs when control leaves the scope.

Check your understanding: GC reclaims unreachable managed objects. Disposal releases a resource at a predictable time. One does not replace the other.

7. Stack allocation, spans and memory

Span and ReadOnlySpan are lightweight views over contiguous memory. They can refer to arrays, strings, stack-allocated buffers or unmanaged memory without copying the contents. Because they are stack-only ref struct types, their lifetime is restricted: they cannot be fields of ordinary classes or survive across an await.

static bool TryReadCoordinates(ReadOnlySpan<char> input, out int x, out int y)
{
    int comma = input.IndexOf(',');
    if (comma <= 0 || comma == input.Length - 1)
    {
        x = y = default;
        return false;
    }

    return int.TryParse(input[..comma], out x)
        && int.TryParse(input[(comma + 1)..], out y);
}

This parses slices without allocating two substring objects. C# 14 adds first-class span conversions that make arrays and spans compose more naturally with overload resolution and generics.

Use Memory or ReadOnlyMemory when a buffer must cross asynchronous boundaries or be stored. When renting from ArrayPool, always return the buffer, and clear sensitive content if required.

byte[] buffer = ArrayPool<byte>.Shared.Rent(16_384);
try
{
    int read = await stream.ReadAsync(buffer.AsMemory(0, 16_384), cancellationToken);
    Process(buffer.AsSpan(0, read));
}
finally
{
    ArrayPool<byte>.Shared.Return(buffer, clearArray: true);
}

Spans are a precision instrument for measured hot paths, parsers and pipelines. Do not make an entire codebase harder to understand to remove allocations that never mattered.

Start with the ordinary version

Suppose the input is "120,450". A beginner-friendly parser can split the string:

static (int X, int Y) ReadCoordinates(string input)
{
    string[] parts = input.Split(',');

    if (parts.Length != 2)
        throw new FormatException("Expected x,y.");

    return (int.Parse(parts[0]), int.Parse(parts[1]));
}

This is clear and should be the starting point. Split creates an array and two strings. If profiling shows that millions of calls make those allocations expensive, a span version can view the original characters instead.

That comparison gives us the right optimisation workflow:

1. write the clear correct version;
2. measure it in a representative workload;
3. identify the actual source of cost;
4. apply a more specialised API;
5. measure again and keep tests around the behaviour.

stackalloc creates a small temporary buffer whose lifetime is limited to the current method:

Span<int> recent = stackalloc int[4];
recent[0] = 10;
recent[1] = 20;

Do not stack-allocate large or input-controlled sizes; stack space is limited. Use an array, pooled buffer or another bounded strategy when the size can grow.

Revision checkpoint for Part I

• Assignment copies a value or copies a reference depending on the type.
• Equality semantics are a domain choice and later affect hashing.
• Strings are immutable, so transformations may allocate new strings.
• The CLR manages execution and reachable managed memory.
• Disposal releases resources deterministically.
• Spans are views over memory, useful after measurement shows copying or allocation matters.

With those foundations in place, we can now measure how work grows and select collections intelligently.

---

Part II — Complexity and everyday .NET collections

8. Big O: how growth behaves

Big O is a way to describe how an algorithm's work grows when its input grows. It does not tell us the exact number of milliseconds. It answers a more useful scaling question:

If the amount of data becomes 10, 100 or 1,000 times larger, how quickly will the work or memory requirement grow?

We normally use n to mean the number of input items. If an array contains 100 numbers, then n is 100. The O is read as "order of", so O(n) is read as "order of n" or simply "linear time".

Why a beginner should care

Two methods can return the same correct answer but behave very differently as the data grows. Imagine checking every product against every other product:

This is why code that feels instant in a small test can become painfully slow in production.

The common complexity families

The families appear from most scalable to least scalable in the table. Let us make each one concrete.

O(1): constant time

Constant time means the amount of work does not grow with the number of items. Reading an array element by index is the classic example:

int[] scores = [72, 91, 84, 67, 95];

int first = scores[0];
int fourth = scores[3];

The runtime calculates where the requested element lives and accesses it directly. Whether the array contains 5 items or 5 million, one valid index lookup is still one lookup.

O(1) does not mean "one instruction" or "instant". It means the work stays roughly constant as n grows.

O(n): linear time

Linear time means the work grows in direct proportion to the input. To find a value in an unsorted array, we may need to inspect every item:

static bool Contains(int[] numbers, int target)
{
    foreach (int number in numbers)
    {
        if (number == target)
            return true;
    }

    return false;
}

If the array doubles in size, the worst-case work roughly doubles. The early return gives us different cases:

• best case — O(1): the target is the first item;
• average case — O(n): we inspect part of the array;
• worst case — O(n): the target is last or is not present.

Unless somebody says otherwise, Big O discussions commonly focus on the worst case because it gives us an upper-bound expectation.

O(log n): logarithmic time

Logarithmic algorithms repeatedly discard a large part of the remaining problem. Binary search checks the middle of sorted data, then throws away the half that cannot contain the target:

static int BinarySearch(int[] sortedNumbers, int target)
{
    int left = 0;
    int right = sortedNumbers.Length - 1;

    while (left <= right)
    {
        int middle = left + ((right - left) / 2);
        int value = sortedNumbers[middle];

        if (value == target)
            return middle;

        if (value < target)
            left = middle + 1;
        else
            right = middle - 1;
    }

    return -1;
}

For roughly 1,000 sorted items, binary search needs at most about 10 checks. For roughly 1 million items, it needs about 20. Doubling the input adds only one more step. The important precondition is that the data must already be sorted; sorting it solely to perform one search may cost more than a linear scan.

O(n log n): efficient general sorting

Algorithms such as merge sort repeatedly divide the data and do linear work at each level. That produces O(n log n). In production C#, use the platform sorting APIs rather than writing your own general-purpose sort:

int[] numbers = [8, 3, 6, 1, 9, 2];
Array.Sort(numbers);

List<string> names = ["Maya", "Amir", "Zoe"];
names.Sort(StringComparer.Ordinal);

Sorting is more expensive than one linear scan, but far better than a quadratic sorting approach on large input.

O(n²): quadratic time

Quadratic behaviour often appears when, for every item, we inspect every item again:

static void PrintEveryPair(int[] numbers)
{
    foreach (int left in numbers)       // Runs n times
    {
        foreach (int right in numbers)  // Runs n times for each left
        {
            Console.WriteLine($"{left}, {right}");
        }
    }
}

The inner statement runs n × n, giving O(n²). Nested loops are not automatically quadratic, however. Judge how many times the inner work really runs. A two-pointer algorithm may contain a nested-looking loop while each pointer moves through the input only once, making the total O(n).

Here is a common accidental O(n²) pattern:

List<int> allowedIds = [10, 20, 30];
List<int> requestedIds = [20, 40, 10];

foreach (int id in requestedIds)       // O(n)
{
    if (allowedIds.Contains(id))        // O(n) list scan
        Console.WriteLine(id);
}

If membership testing dominates, a set changes the average lookup cost:

HashSet<int> allowedIds = [10, 20, 30];

foreach (int id in requestedIds)       // O(n)
{
    if (allowedIds.Contains(id))        // O(1) average
        Console.WriteLine(id);
}

Building the set costs O(n) time and O(n) extra memory, but repeated membership checks are then O(1) average. This is a time-space trade-off.

O(2ⁿ): exponential time

An exponential algorithm may explore every subset of n items. Each item has two choices — include it or exclude it — so the number of possibilities doubles whenever one item is added:

static void PrintSubsets(int[] numbers, int index, List<int> chosen)
{
    if (index == numbers.Length)
    {
        Console.WriteLine(string.Join(", ", chosen));
        return;
    }

    // Choice 1: do not include this number.
    PrintSubsets(numbers, index + 1, chosen);

    // Choice 2: include this number.
    chosen.Add(numbers[index]);
    PrintSubsets(numbers, index + 1, chosen);
    chosen.RemoveAt(chosen.Count - 1);
}

Ten items have 1,024 subsets. Twenty items have more than 1 million. Forty items have more than 1 trillion. Exponential algorithms become impractical surprisingly quickly, so we look for pruning, memoisation, dynamic programming or a different formulation.

O(n!): factorial time

Factorial behaviour appears when an algorithm generates every possible ordering. Three items have 3 × 2 × 1 = 6 permutations. Ten items have 3,628,800. A brute-force travelling salesperson solution is the classic warning example. Factorial algorithms are normally suitable only for very small inputs or heavily pruned searches.

How to calculate Big O from code

Use this beginner-friendly process:

1. Decide what n represents.
2. Identify the operation that repeats as n grows.
3. Count how loops or recursive branches repeat that operation.
4. Combine consecutive work by adding and nested work by multiplying.
5. Keep only the fastest-growing term and remove constant multipliers.

#### Rule 1: remove constants

for (int i = 0; i < numbers.Length; i++)
{
    Console.WriteLine(numbers[i]);
    Console.WriteLine(numbers[i] * 2);
    Console.WriteLine(numbers[i] * 3);
}

The loop performs three constant-time actions for each item: 3n. Big O removes the constant multiplier, so this is O(n), not O(3n).

#### Rule 2: consecutive loops are added

foreach (int number in numbers)
    Console.WriteLine(number);

foreach (int number in numbers)
    Console.WriteLine(number * 2);

This is n + n = 2n, which simplifies to O(n). The loops are consecutive, not nested.

#### Rule 3: nested full loops are multiplied

foreach (int left in numbers)
{
    foreach (int right in numbers)
        Console.WriteLine(left + right);
}

This is n × n, which is O(n²).

#### Rule 4: keep the dominant term

If a method does one linear pass and then compares every pair, its work is n + n². As n becomes large, the quadratic part dominates, so we describe the whole method as O(n²). Likewise, 3n + 20 simplifies to O(n).

#### Rule 5: different inputs need different letters

foreach (Customer customer in customers)
{
    foreach (Order order in orders)
        Check(customer, order);
}

If there are c customers and o orders, the honest complexity is O(c × o), not automatically O(n²). They may grow independently.

Best, average and worst case

The same algorithm can have more than one complexity depending on the input:

• a linear search is O(1) in the best case and O(n) in the worst case;
• a hash-table lookup is O(1) on average but may degrade towards O(n) when many keys collide;
• a well-implemented quicksort is O(n log n) on average but its theoretical worst case is O(n²).

State which case you mean. For capacity planning or untrusted input, worst-case behaviour may matter most. For ordinary dictionary use with a correct comparer, average behaviour is usually the practical model.

Amortised complexity: why List.Add is usually O(1)

A List stores items in an internal array. Most calls to Add place an item into the next free slot, which is O(1). When the array is full, the list allocates a larger array and copies its existing items, which is O(n).

var names = new List<string>();

for (int i = 0; i < 1_000; i++)
    names.Add($"Name {i}");

The occasional expensive resize is spread across many cheap additions. Averaged over the complete sequence, each addition is O(1) amortised. If you know the likely size, supplying a capacity can avoid some resizing:

var names = new List<string>(capacity: 1_000);

Space complexity

We analyse memory growth as well as execution time. This method creates a second array proportional to the input, so its additional space is O(n):

static int[] DoubleAll(int[] numbers)
{
    var result = new int[numbers.Length];

    for (int i = 0; i < numbers.Length; i++)
        result[i] = numbers[i] * 2;

    return result;
}

This method changes the existing array and uses only a fixed amount of extra memory, so its additional space is O(1):

static void DoubleAllInPlace(int[] numbers)
{
    for (int i = 0; i < numbers.Length; i++)
        numbers[i] *= 2;
}

The in-place version saves memory but mutates its input. That may or may not be acceptable. Complexity does not make the product decision for us.

Big O is not a stopwatch

An O(1) hash lookup may be slower than scanning eight contiguous elements. Memory layout, cache locality, allocations and branch prediction matter. Big O tells me what happens as scale changes; benchmarks tell me what happens on a real runtime and machine.

For example, building a dictionary to perform one lookup in eight items is probably unnecessary. But performing thousands of lookups in millions of items is a different problem. Use Big O to reason about growth, then use representative benchmarks and profiling to measure real behaviour.

A practical decision example

Suppose we repeatedly need to find a customer by ID.

List<Customer> customers = LoadCustomers();

Customer? found = customers.FirstOrDefault(c => c.Id == requestedId);

One list search is O(n) and may be completely reasonable. If we perform that search many times, we can build an index:

Dictionary<int, Customer> customersById =
    customers.ToDictionary(customer => customer.Id);

if (customersById.TryGetValue(requestedId, out Customer? customer))
{
    Console.WriteLine(customer.Name);
}

Building the dictionary costs O(n) time and O(n) additional memory. Each later lookup is O(1) average. The correct choice depends on collection size, lookup frequency, memory constraints and how often the data changes.

Big O checklist

When reviewing code, ask:

• What does n represent?
• What operation dominates as n grows?
• Are loops consecutive or truly nested?
• Does recursion create one branch or several branches per call?
• Am I discussing the best, average or worst case?
• What additional memory grows with the input?
• Can a suitable collection replace repeated work?
• Are the expected inputs large enough for this difference to matter?

The goal is not to label every line of code. The goal is to spot growth that will become dangerous, explain the trade-off clearly and select a design that fits the real workload.

9. Arrays: the foundation

An array is a fixed-length contiguous sequence of one element type. Index access is O(1) because the address can be calculated directly.

int[] scores = [91, 75, 88, 64];
scores[2] = 90;

C# collection expressions such as [91, 75, 88, 64] provide modern concise initialisation. Arrays offer excellent locality and low overhead. Their fixed size is both strength and limitation.

Searching an unsorted array is O(n). Inserting in the middle requires shifting elements: O(n). A rectangular multidimensional array T[,] represents a rectangular grid; a jagged array T[][] is an array of arrays whose rows may differ in length.

Choose an array when size is known or controlled, indexed access dominates and you want compact contiguous storage. Expose ReadOnlySpan or IReadOnlyList when callers should not mutate your internal array.

An index is a zero-based position: the first item is at 0 and the final item is at Length - 1. An invalid index throws IndexOutOfRangeException. Fixed length does not mean immutable—you can replace an element, but that array object cannot gain more slots.

string[] names = new string[3];
names[0] = "Maya";
names[1] = "Amir";
names[2] = "Zoe";

for (int index = 0; index < names.Length; index++)
    Console.WriteLine($"{index}: {names[index]}");

Contiguous storage explains both O(1) indexing and good sequential memory locality. If the number of elements naturally changes, move to List rather than manually resizing arrays.

Single-dimensional, rectangular and jagged arrays

A single-dimensional array represents one sequence. A rectangular array uses a fixed number of rows and columns and is useful when every row has the same shape:

int[,] multiplicationTable = new int[3, 3];

for (int row = 0; row < multiplicationTable.GetLength(0); row++)
{
    for (int column = 0; column < multiplicationTable.GetLength(1); column++)
        multiplicationTable[row, column] = (row + 1) * (column + 1);
}

GetLength(0) returns the number of rows and GetLength(1) the number of columns. A grid, board or fixed game map can fit this model.

A jagged array is an array whose elements are themselves arrays. Each inner array may have a different length:

int[][] seatsPerCoach =
[
    [1, 2, 3, 4],
    [1, 2],
    [1, 2, 3]
];

for (int coach = 0; coach < seatsPerCoach.Length; coach++)
{
    for (int seat = 0; seat < seatsPerCoach[coach].Length; seat++)
        Console.WriteLine($"Coach {coach}, seat {seatsPerCoach[coach][seat]}");
}

Choose rectangular storage when the domain is a true rectangle. Choose jagged storage when rows naturally differ or are managed independently. The syntax looks similar, but the shape and memory model are different.

10. List: the everyday dynamic array

List stores elements in an internal array and grows capacity when required.

var orders = new List<Order>(capacity: expectedCount);
orders.Add(order);

Key costs:

• index: O(1);
• append: O(1) amortised;
• search: O(n);
• insert or remove in the middle: O(n);
• Contains: O(n).

Providing a reasonable initial capacity can reduce resizing for known large batches. Do not confuse Count with Capacity: count is the number of logical elements; capacity is the allocated slots.

The classic performance bug is repeated membership testing:

// Potentially O(n * m)
var selected = orders.Where(order => allowedIds.Contains(order.Id)).ToList();

// Build once, then average O(1) membership checks
HashSet<Guid> allowed = allowedIds.ToHashSet();
var selectedFast = orders.Where(order => allowed.Contains(order.Id)).ToList();

The algorithm changed more than the syntax.

Count is the number of current items; Capacity is the number of slots available before the internal array must grow:

var names = new List<string>(capacity: 4);
names.Add("Maya");
names.Add("Amir");

Console.WriteLine(names.Count);    // 2
Console.WriteLine(names.Capacity); // At least 4

Position explains cost. Adding at the end normally fills the next slot. Inserting at index zero shifts every existing item right. Removing near the front shifts later items left. Start with List for an ordered resizable sequence, then change only when another operation clearly dominates.

11. LinkedList: understand it, rarely default to it

A linked list stores nodes connected by references. A doubly linked node has previous and next links. Inserting or removing a known node is O(1), but finding that node is O(n), and indexing is O(n).

Why is it often slower than beginners expect? Every node is a separate object with allocation overhead and poor cache locality. Modern CPUs love contiguous arrays. List is usually the better general-purpose choice.

Use LinkedList when you genuinely need frequent insertion or removal through existing node handles, stable nodes and bidirectional traversal. LRU caches are a common example: a dictionary finds a linked-list node in O(1), and the list moves it to the front in O(1).

Picture the nodes as [A] ↔ [B] ↔ [C]. They need not sit together in memory. If you already hold node B, changing nearby links is O(1):

var route = new LinkedList<string>();
LinkedListNode<string> london = route.AddLast("London");
LinkedListNode<string> bristol = route.AddLast("Bristol");

route.AddAfter(london, "Reading");
route.Remove(bristol);

The phrase “frequent insertion” is not enough to justify a linked list. Ask whether you already hold the node. Finding it first is O(n), and every node adds allocation and pointer-following cost.

Circular linked lists: when the end returns to the beginning

In an ordinary linked list, traversal eventually reaches null. In a circular linked list, the final node links back to the first node. This models repeating turns, round-robin scheduling, looping playlists and “spin the wheel” behaviour.

Alice → Ben → Chloe
  ↑             ↓
  └─────────────┘

.NET does not provide a dedicated generic circular-linked-list class, but we can build the behaviour safely on top of LinkedList:

public sealed class RoundRobin<T>
{
    private readonly LinkedList<T> _items = [];
    private LinkedListNode<T>? _current;

    public void Add(T item)
    {
        LinkedListNode<T> added = _items.AddLast(item);
        _current ??= added;
    }

    public T Next()
    {
        if (_current is null)
            throw new InvalidOperationException("No items are registered.");

        T result = _current.Value;
        _current = _current.Next ?? _items.First;
        return result;
    }
}

var turns = new RoundRobin<string>();
turns.Add("Alice");
turns.Add("Ben");
turns.Add("Chloe");

Console.WriteLine(turns.Next()); // Alice
Console.WriteLine(turns.Next()); // Ben
Console.WriteLine(turns.Next()); // Chloe
Console.WriteLine(turns.Next()); // Alice again

The danger is termination. A traversal that waits for null will never finish in a circular structure. Stop after a known count, return to the starting node, or use another explicit condition.

12. Stack: last in, first out

A stack supports push, pop and peek at one end, normally O(1).

Use it for nested scopes, undo operations, expression parsing, depth-first traversal and replacing recursion when call depth may be unsafe.

static bool AreBracketsBalanced(ReadOnlySpan<char> text)
{
    var stack = new Stack<char>();

    foreach (char character in text)
    {
        if (character is '(' or '[' or '{')
            stack.Push(character);
        else if (character is ')' or ']' or '}')
        {
            if (!stack.TryPop(out char opening) || !Matches(opening, character))
                return false;
        }
    }

    return stack.Count == 0;
}

Notice TryPop: expected absence need not throw. Exceptions should describe exceptional failure, not routine control flow.

Trace the rule with a simpler example:

var history = new Stack<string>();
history.Push("Open document");
history.Push("Type heading");
history.Push("Delete paragraph");

Console.WriteLine(history.Pop());  // Delete paragraph
Console.WriteLine(history.Peek()); // Type heading; Peek does not remove it.

Last in, first out makes a stack suitable for undo and for returning from nested work. Push, Pop and Peek are O(1).

Demo: Tower of Hanoi connects stacks and recursion

The Tower of Hanoi has three pegs and disks of different sizes. Move every disk from the source peg to the destination under two rules: move one disk at a time, and never place a larger disk on a smaller one.

The recursive insight is to move a smaller tower out of the way, move the largest disk, then move the smaller tower back on top:

static void MoveTower(int disks, char from, char to, char spare)
{
    if (disks <= 0)
        return;

    MoveTower(disks - 1, from, spare, to);
    Console.WriteLine($"Move disk {disks} from {from} to {to}");
    MoveTower(disks - 1, spare, to, from);
}

MoveTower(3, 'A', 'C', 'B');

For three disks, the method makes seven moves. In general it requires 2ⁿ - 1, so its time complexity is O(2ⁿ). The recursion depth is O(n). Each peg can be represented by Stack because only its top disk is accessible. This exercise connects a physical rule, a stack constraint, a recursive decomposition and exponential growth.

13. Queue and concurrent channels

A queue is first in, first out. Enqueue at the tail and dequeue at the head are normally O(1). Use queues for breadth-first traversal and local work ordering.

Queue is not thread-safe. For simple multi-thread access there is ConcurrentQueue, but producer-consumer workflows often need waiting, completion and backpressure. System.Threading.Channels provides stronger asynchronous coordination.

var channel = Channel.CreateBounded<Job>(new BoundedChannelOptions(500)
{
    FullMode = BoundedChannelFullMode.Wait,
    SingleReader = false,
    SingleWriter = false
});

The bounded capacity is a production decision. Without backpressure, a fast producer can turn your queue into an unbounded memory leak.

First in, first out is easy to see:

var tickets = new Queue<string>();
tickets.Enqueue("Ticket A");
tickets.Enqueue("Ticket B");

Console.WriteLine(tickets.Dequeue()); // Ticket A
Console.WriteLine(tickets.Peek());    // Ticket B remains queued.

Queue stores work; it does not automatically coordinate threads or asynchronous waiting. A channel adds that coordination. Use a queue inside one synchronised context and a channel when producers and consumers must wait, signal completion or apply backpressure.

14. PriorityQueue

.NET provides a built-in generic priority queue implemented as a quaternary min-heap. The element with the lowest priority value is dequeued first.

var work = new PriorityQueue<Job, (int Severity, DateTime CreatedAt)>();
work.Enqueue(new Job("Normal"), (3, DateTime.UtcNow));
work.Enqueue(new Job("Critical"), (1, DateTime.UtcNow));

Job next = work.Dequeue();

Enqueue and dequeue are O(log n); peek is O(1). Do not assume enumeration returns priority order—the UnorderedItems view explicitly makes no ordering guarantee. Also remember that equal priorities are not automatically stable. Include a sequence value if FIFO order within a priority matters.

A normal queue answers “who arrived first?” A priority queue answers “who is most urgent?” Because the built-in queue is a min-heap, smaller priority values leave first:

var patients = new PriorityQueue<string, int>();
patients.Enqueue("Routine check-up", 3);
patients.Enqueue("Broken arm", 2);
patients.Enqueue("Chest pain", 1);

while (patients.TryDequeue(out string? patient, out int priority))
    Console.WriteLine($"{priority}: {patient}");

The heap keeps only enough order to find the minimum efficiently. It is not a fully sorted collection.

15. Dictionary: fast lookup through hashing

A dictionary maps unique keys to values. It uses a key’s hash code to choose a bucket and equality to identify the correct key within collisions. Average lookup, insertion and removal are O(1), though worst-case behaviour can degrade.

var customers = new Dictionary<CustomerId, Customer>();
customers[customer.Id] = customer;

if (customers.TryGetValue(id, out Customer? found))
{
    Process(found);
}

Prefer TryGetValue when absence is expected. Indexing a missing key throws. Avoid ContainsKey followed by indexing because that performs two lookups.

Hash keys require stable equality. If a key changes after insertion so its hash changes, the dictionary may no longer find it. Immutable keys are safest. Custom equality comparers must obey this rule:

if Equals(a, b) is true,
GetHashCode(a) must equal GetHashCode(b).

The reverse is not required; different values may share a hash. That is a collision, not a bug.

For string keys, state your intent:

var headers = new Dictionary<string, string>(StringComparer.OrdinalIgnoreCase);

Do not rely on dictionary enumeration order as a sorting guarantee. If ordering is part of the contract, use a structure that declares it or sort explicitly.

Think of hashing as a filing system. The hash code chooses a likely drawer, then equality finds the exact key inside it. Two different keys can choose the same drawer; that is a collision, which affects the amount of checking but does not automatically lose data.

var prices = new Dictionary<string, decimal>(StringComparer.OrdinalIgnoreCase)
{
    ["BOOK"] = 12.99m,
    ["PEN"] = 1.50m
};

if (prices.TryGetValue("book", out decimal price))
    Console.WriteLine(price); // 12.99

Choose a dictionary when your question is naturally: “given this unique key, what value belongs to it?”

16. Frozen and immutable lookup structures

FrozenDictionary and FrozenSet are optimised for data constructed infrequently and queried frequently. Creation costs more, but repeated lookup and enumeration can be excellent.

using System.Collections.Frozen;

FrozenDictionary<string, Country> countries = source
    .ToFrozenDictionary(country => country.Code, StringComparer.OrdinalIgnoreCase);

This suits static reference data built at application startup. “Frozen” describes an optimised read-only structure, not a general replacement for Dictionary.

Immutable collections model snapshots where an update produces a new logical collection while sharing internal structure. Read-only interfaces merely prevent mutation through that reference; the underlying object might still change elsewhere. These are different guarantees.

.NET 10 collection APIs continue to improve alternate lookup and span-based creation scenarios, reducing temporary allocations when, for example, a string-keyed frozen dictionary is queried by ReadOnlySpan. Use such features after profiling a hot lookup path, not as beginner decoration.

Frozen and immutable sound similar but model different lifecycles:

Dictionary<string, int> source = new() { ["admin"] = 10 };

FrozenDictionary<string, int> frozen = source.ToFrozenDictionary();
ImmutableDictionary<string, int> first = source.ToImmutableDictionary();
ImmutableDictionary<string, int> second = first.SetItem("viewer", 1);

The frozen collection is finished and optimised for reads. second is a new logical version while first remains unchanged. Use frozen for build-once/read-many tables and immutable for state represented by successive snapshots.

17. HashSet: uniqueness and set algebra

A hash set stores unique values with average O(1) add, remove and membership testing.

HashSet<string> roles = userRoles.ToHashSet(StringComparer.OrdinalIgnoreCase);

if (roles.Contains("administrator"))
{
    // Membership is the main operation.
}

Set operations express intent directly:

• union: values in either set;
• intersection: values in both;
• except: values in the first but not the second;
• symmetric difference: values in exactly one set;
• subset and superset checks.

Use HashSet for membership and uniqueness, not a List plus repeated Contains. Use SortedSet when you need unique values maintained in sorted order and accept O(log n) operations.

Let the collection enforce the rule:

var attendees = new HashSet<string>(StringComparer.OrdinalIgnoreCase);

Console.WriteLine(attendees.Add("Maya")); // True: inserted
Console.WriteLine(attendees.Add("MAYA")); // False: duplicate

var requested = new HashSet<string> { "Read", "Write" };
var granted = new HashSet<string> { "Read", "Export" };
requested.IntersectWith(granted);

Console.WriteLine(string.Join(", ", requested)); // Read

Use a set when uniqueness or membership is the domain rule. Use a list when order and duplicate occurrences carry meaning.

SortedSet: uniqueness plus sort order

HashSet uses hashing and offers average O(1) membership without sorted order. SortedSet uses a balanced tree, keeps unique values ordered, and performs lookup, addition and removal in O(log n).

var scores = new SortedSet<int> { 90, 70, 90, 85, 70 };

Console.WriteLine(string.Join(", ", scores)); // 70, 85, 90
Console.WriteLine(scores.Min);                // 70
Console.WriteLine(scores.Max);                // 90

Duplicates disappear because this is a set; enumeration is sorted because this is a sorted set. Choose it when both guarantees are required. If you only need uniqueness and membership, HashSet is usually the simpler and faster starting point.

18. SortedDictionary, SortedList and OrderedDictionary

Names can be misleading, so focus on guarantees.

SortedDictionary is tree-based and maintains keys in sort order with O(log n) insertion and lookup. SortedList uses sorted arrays: lookups are O(log n), indexed access is possible, but insertion may shift elements in O(n). It can be memory efficient when data is mostly built once.

.NET 10 includes generic OrderedDictionary, preserving insertion order while allowing access by key or index. Insertion order is not sort order.

Choose by the operation:

Fast general key lookup          -> Dictionary
Fast fixed lookup                -> FrozenDictionary
Key-sorted mutation              -> SortedDictionary
Mostly static, compact sorted    -> SortedList
Preserve insertion sequence      -> OrderedDictionary

Write the guarantee before choosing. “Display keys alphabetically while values change” suggests SortedDictionary. “Load once, enumerate often in key order” may suit SortedList. “Preserve the exact sequence the user added items” requires insertion order.

var sorted = new SortedDictionary<string, decimal>(StringComparer.Ordinal)
{
    ["Zebra"] = 9.99m,
    ["Apple"] = 1.25m
};

foreach ((string name, decimal price) in sorted)
    Console.WriteLine(name); // Apple, then Zebra

Revision checkpoint for Part II

• Arrays are fixed contiguous sequences; lists add dynamic capacity.
• Linked lists make operations on known nodes cheap but sacrifice locality and indexing.
• Stacks are LIFO; queues are FIFO; priority queues choose by urgency.
• Dictionaries map unique keys to values; sets enforce uniqueness.
• Frozen, immutable, sorted and insertion-ordered collections solve different lifecycle and ordering problems.

---

Part III — Classic algorithms and structures

The library collections remain your production defaults. We now study the algorithms underneath them so you can predict behaviour, debug problems and recognise requirements confidently.

19. Sorting: know the classics, use the library

Sorting teaches algorithm design, but production code should normally use Array.Sort, List.Sort, Span.Sort or LINQ ordering. The runtime implementations are highly engineered and handle edge cases you do not want to rediscover.

Bubble sort

Bubble sort repeatedly swaps adjacent out-of-order elements. Its typical and worst time is O(n²), with O(1) auxiliary space. It is valuable for teaching and rarely for production.

static void BubbleSort<T>(Span<T> values, IComparer<T>? comparer = null)
{
    comparer ??= Comparer<T>.Default;

    for (int end = values.Length - 1; end > 0; end--)
    {
        bool swapped = false;
        for (int i = 0; i < end; i++)
        {
            if (comparer.Compare(values[i], values[i + 1]) <= 0)
                continue;

            (values[i], values[i + 1]) = (values[i + 1], values[i]);
            swapped = true;
        }

        if (!swapped) return;
    }
}

The early exit makes already sorted input O(n), but the general weakness remains.

Trace [3, 1, 2]: compare 3 and 1, swap to get [1, 3, 2]; compare 3 and 2, swap to get [1, 2, 3]. The largest value has “bubbled” to the end. Another pass confirms the remaining prefix. This trace is more valuable than memorising the code.

Selection sort

Selection sort finds the minimum remaining value and puts it next. It performs O(n²) comparisons but only O(n) swaps. That trade-off historically mattered where writes were unusually expensive.

For [3, 1, 2], find the minimum value 1 and swap it into position zero, producing [1, 3, 2]. Then find the minimum of the remaining suffix and place 2 next. The sorted prefix grows from the left.

Insertion sort

Insertion sort takes each value and inserts it into the sorted prefix. It is O(n²) worst case but fast for small or nearly sorted inputs. Efficient general sort implementations often use it for tiny partitions.

Think of arranging playing cards in your hand. With [3, 1, 2], treat 3 as sorted, insert 1 before it, then insert 2 between them. The algorithm shifts larger values to make a gap.

Merge sort

Merge sort divides the input, recursively sorts halves and merges them. It provides O(n log n) worst-case time and can be stable, but conventional array implementations need O(n) extra space.

The divide step continues until every piece contains one item; a one-item sequence is already sorted. The merge step repeatedly takes the smaller front item from two sorted halves. For [4, 1, 3, 2], split to [4, 1] and [3, 2], sort them to [1, 4] and [2, 3], then merge to [1, 2, 3, 4].

Quicksort

Quicksort partitions values around a pivot and recursively sorts partitions. Average time is O(n log n), worst case O(n²). Good pivot selection and introspective fallbacks manage that risk. Its locality and low additional storage make it effective.

A pivot is a chosen reference value. Partitioning moves smaller values to one side and larger values to the other; the sides need not yet be internally sorted. Recursion repeats the process. Pivot choice matters because severely uneven partitions create deep quadratic work.

Stability

A stable sort preserves the original order of values that compare equal. That matters when applying several sort keys. LINQ’s OrderBy is stable; do not assume every in-place sort is.

var ordered = employees
    .OrderBy(employee => employee.Department)
    .ThenBy(employee => employee.JoinedOn)
    .ToArray();

Always define comparers consistently. A comparer should be reflexive, antisymmetric and transitive. Broken comparison rules can produce incorrect sorting and tree behaviour.

For application code, the lesson is not “implement every sort.” It is: know the preconditions, expected complexity, stability and memory behaviour, then use Array.Sort, List.Sort or LINQ ordering with an explicit comparer.

20. Searching: linear, binary and indexed

Linear search checks elements in turn: O(n). It is correct for unsorted data and often best for very small collections.

Binary search repeatedly halves a sorted search interval: O(log n).

static int BinarySearch<T>(ReadOnlySpan<T> values, T target, IComparer<T>? comparer = null)
{
    comparer ??= Comparer<T>.Default;
    int low = 0;
    int high = values.Length - 1;

    while (low <= high)
    {
        int middle = low + ((high - low) / 2);
        int comparison = comparer.Compare(values[middle], target);

        if (comparison == 0) return middle;
        if (comparison < 0) low = middle + 1;
        else high = middle - 1;
    }

    return -1;
}

The precondition—sorted using a compatible comparer—is part of the algorithm. Binary search over unsorted data is fast nonsense.

If you repeatedly search changing unsorted data, maintaining a dictionary or tree may be better than sorting for every query. Include index construction and update cost in the decision.

Choose search by the state of the data

One search over small unsorted data       -> linear search
Many searches over already sorted data   -> binary search
Many exact key lookups                    -> dictionary
Ordered lookup plus ongoing updates       -> balanced sorted structure

Walk through binary search for target 23 in [5, 11, 17, 23, 31]. The middle is 17. Because 23 is larger, discard 5, 11 and 17. The new middle is 23, so the search stops. The discarded half is the source of O(log n).

Try it: run the method with a missing target and print low, middle and high on each iteration. Seeing the search interval shrink makes the algorithm memorable.

21. Recursion and the call stack

Recursion describes a solution in terms of smaller instances. It needs a base case and progress toward it.

static long Factorial(int n) => n switch
{
    < 0 => throw new ArgumentOutOfRangeException(nameof(n)),
    0 or 1 => 1,
    _ => checked(n * Factorial(n - 1))
};

This is clear but limited by long overflow and call-stack depth. C# does not promise tail-call optimisation. Deep or attacker-controlled recursion can cause StackOverflowException, which ordinary application code cannot safely recover from. Use an explicit Stack for deep tree or graph traversal.

For Factorial(3), the calls expand before they return:

Factorial(3)
  3 × Factorial(2)
      2 × Factorial(1)
          1                 <- base case
      2 × 1 = 2
  3 × 2 = 6

The base case stops recursion. The recursive case must move toward it. Missing either rule causes infinite recursion until stack space is exhausted. Recursion is a description technique, not automatically the fastest implementation.

22. Trees: hierarchical data

A tree contains nodes connected by parent-child relationships, with no cycles in the tree itself. File structures, organisation charts, syntax trees and UI components are familiar examples.

Terms to know:

• root: the top node;
• leaf: a node with no children;
• depth: distance from root to node;
• height: longest path from node to a leaf;
• subtree: a node and descendants.

A general tree node can hold a collection of children:

public sealed class TreeNode<T>(T value)
{
    public T Value { get; } = value;
    public List<TreeNode<T>> Children { get; } = [];
}

Be careful exposing a mutable list. A production domain type may offer controlled AddChild behaviour and an IReadOnlyList> view so it can enforce no cycles, ownership and invariants.

Build a tiny tree before learning traversal names:

Products
├── Books
│   ├── Fiction
│   └── Computing
└── Stationery

Products is the root. Fiction, Computing and Stationery are leaves. Books and everything below it form a subtree. Depth counts how far a node is from the root; height measures the longest route down to a leaf.

A tree differs from a general graph because every non-root node has one parent and there are no cycles. Those guarantees allow simpler reasoning.

23. Binary search trees and balance

A binary tree has at most two children per node. A binary search tree adds ordering: smaller keys go left, larger keys go right according to a comparer.

Lookup, insertion and removal are O(h), where h is tree height. In a balanced tree, height is O(log n). Insert sorted data into a naive BST and it can become a chain with O(n) operations.

AVL and red-black trees use rotations and balance rules to keep height logarithmic. You should understand why balance matters, but you rarely implement these yourself in application code. .NET’s SortedDictionary and SortedSet use balanced tree structures.

Tree traversals:

• preorder: node, left, right—useful for copying structure;
• inorder: left, node, right—produces sorted order in a BST;
• postorder: left, right, node—useful when children must be processed before a parent;
• level order: breadth-first using a queue.

For a BST containing 2 at the root, 1 on the left and 3 on the right, inorder traversal produces 1, 2, 3. Balance matters because it keeps the number of decisions small. A chain of 1, then 2, then 3 behaves like a linked list rather than a logarithmic search tree.

Rotations rearrange a small part of a self-balancing tree while preserving key order. You need to understand their purpose—keeping height logarithmic—before you need to study their implementation.

Lookup, insertion and removal in a BST

Lookup begins at the root. Compare the target with the current key: equality finishes, a smaller target moves left, and a larger target moves right. Insertion follows the same route until it finds an empty child position.

Removal has three cases:

1. A leaf has no children, so detach it.
2. A node with one child can be replaced by that child.
3. A node with two children can be replaced by its inorder successor—the smallest key in its right subtree—and that successor is then removed from its former position.

The third case is where beginner implementations often break links or duplicate keys. Draw the affected nodes before changing references.

public sealed class BstNode<T>(T value)
{
    public T Value { get; set; } = value;
    public BstNode<T>? Left { get; set; }
    public BstNode<T>? Right { get; set; }
}

static bool Contains<T>(BstNode<T>? node, T target, IComparer<T> comparer)
{
    while (node is not null)
    {
        int comparison = comparer.Compare(target, node.Value);
        if (comparison == 0) return true;
        node = comparison < 0 ? node.Left : node.Right;
    }

    return false;
}

AVL and red-black trees

Both are self-balancing binary search trees, but they enforce different balance rules.

An AVL tree keeps the heights of a node's left and right subtrees within one. Its tighter balance makes lookup excellent, but updates may require more rebalancing. A red-black tree assigns each node a colour and enforces rules that prevent paths becoming excessively uneven. Its balance is looser, often reducing update work while still guaranteeing O(log n) operations.

A rotation changes local parent-child relationships without changing inorder key order. A left rotation lifts a right child; a right rotation lifts a left child. Single and double rotations repair different imbalance shapes.

You rarely implement these structures in business code. Use SortedDictionary and SortedSet when their guarantees fit. Study AVL and red-black trees to understand why those logarithmic guarantees survive awkward insertion orders.

24. Heaps: efficient access to an extreme

A binary heap is a complete binary tree commonly stored in an array. In a min-heap, each parent is no greater than its children; therefore the minimum is at the root.

For index i in a zero-based array:

left child  = 2i + 1
right child = 2i + 2
parent      = (i - 1) / 2

Enqueue adds at the end then “bubbles up”; dequeue moves the last element to the root then “bubbles down.” Both are O(log n), while peek is O(1).

A heap is not fully sorted. It guarantees only the parent-child priority relationship. Use PriorityQueue unless implementing a heap is itself the learning goal.

Heapsort builds a heap and repeatedly extracts the extreme. It gives O(n log n) time and O(1) auxiliary array space but is not stable and often has poorer locality than quicksort variants.

For a min-heap, the root is guaranteed to be the smallest value, but siblings and distant nodes are not fully ordered. That is why PriorityQueue can reveal the next minimum efficiently but cannot offer sorted enumeration for free.

Try storing [2, 5, 3, 9, 7] in the array layout. The children of index zero are indexes one and two: 5 and 3, both no smaller than their parent 2. That local rule is the heap invariant.

Binomial and Fibonacci heaps

The source material also introduces two advanced heap families. They matter mainly when algorithms frequently merge heaps or decrease existing priorities.

A binomial heap is a collection of binomial trees. A binomial tree of order zero is one node. A tree of the next order is formed by linking two equal-order trees, making one root the other's child. This structure resembles binary carrying: at most one tree of each order remains after consolidation. Merging two heaps can therefore combine their tree collections systematically.

A Fibonacci heap delays much of that consolidation. It keeps a collection of heap-ordered trees, links roots mainly when the minimum is removed, and can cut a node from its parent when decreasing its key. This lazy strategy gives strong amortised theoretical bounds, including O(1) amortised insertion and decrease-key.

Why are they not everyday defaults? They require more pointers, have larger constants, are harder to implement and verify, and often interact less favourably with CPU caches than an array-backed binary heap. Theoretical advantage matters only when the workload performs enough of the operations they optimise.

Binary heap:     simple, compact, excellent general priority queue
Binomial heap:   designed to support efficient heap merging
Fibonacci heap:  strong amortised decrease-key and merge bounds

In ordinary .NET application code, begin with PriorityQueue. Treat advanced heaps as specialised algorithmic tools, not status symbols.

25. Tries for prefix-oriented text

A trie stores keys by characters or segments along paths. Search cost depends on key length, O(k), rather than the number of stored keys. Tries support prefix lookup and autocomplete naturally.

Their downside is memory: nodes and child maps can be expensive. Compressed tries and specialised representations reduce overhead. Before writing one, check whether a sorted array plus binary search, a database index or an existing search component is sufficient.

If a trie stores car, card and care, the path c → a → r is shared. From that prefix, branches lead to d and e, while a marker records that car is also a complete word. Lookup time depends primarily on the searched key's length k.

This is ideal for prefix questions such as “which words begin with car?” It may be wasteful for a small fixed list where ordinary sorting and binary search are simpler.

26. Graphs: relationships beyond hierarchy

A graph contains vertices and edges. Edges may be directed or undirected, weighted or unweighted. Graphs model routes, dependencies, social connections, workflows and service topology.

Two main representations are:

Adjacency matrix

An n × n matrix records whether each pair is connected. Edge lookup is O(1), but space is O(n²). It suits dense graphs.

Adjacency list

Each vertex stores its outgoing neighbours. Space is O(V + E), making it suitable for sparse graphs, which are common in applications.

public sealed class Graph<T>(IEqualityComparer<T>? comparer = null)
    where T : notnull
{
    private readonly Dictionary<T, HashSet<T>> _edges = new(comparer);

    public void AddDirectedEdge(T from, T to)
    {
        if (!_edges.TryGetValue(from, out HashSet<T>? neighbours))
        {
            neighbours = new HashSet<T>(_edges.Comparer);
            _edges.Add(from, neighbours);
        }

        neighbours.Add(to);
        _edges.TryAdd(to, new HashSet<T>(_edges.Comparer));
    }

    public IReadOnlySet<T> Neighbours(T vertex) =>
        _edges.TryGetValue(vertex, out HashSet<T>? values)
            ? values
            : throw new KeyNotFoundException($"Unknown vertex: {vertex}");
}

The notnull constraint matches dictionary key requirements. In a real API I would avoid leaking a mutable HashSet through a read-only interface if other internal code could still mutate it unexpectedly during enumeration.

Translate a real problem into a graph

Suppose London has routes to Reading and Oxford, and Reading has a route to Bristol. Cities are vertices; routes are edges. If travel is possible both ways, edges are undirected. If each route has a distance, the graph is weighted.

An adjacency matrix allocates a cell for every possible pair, including pairs with no route. An adjacency list stores only existing neighbours. Most application graphs are sparse—each vertex connects to a small fraction of all vertices—so adjacency lists are common.

Before choosing an algorithm, classify the graph: directed or undirected, weighted or unweighted, cyclic or acyclic, sparse or dense. These properties decide which algorithms are correct.

27. Breadth-first and depth-first search

Breadth-first search explores vertices level by level using a queue. In an unweighted graph it finds a path with the fewest edges. Depth-first search follows a branch using recursion or an explicit stack, then backtracks.

Both traverse O(V + E) with an adjacency list because each vertex and edge is processed a bounded number of times.

static Dictionary<T, T?> BreadthFirst<T>(
    T start,
    Func<T, IEnumerable<T>> neighbours,
    IEqualityComparer<T>? comparer = null)
    where T : notnull
{
    var previous = new Dictionary<T, T?>(comparer) { [start] = default };
    var queue = new Queue<T>();
    queue.Enqueue(start);

    while (queue.TryDequeue(out T? current))
    {
        foreach (T next in neighbours(current))
        {
            if (previous.ContainsKey(next)) continue;
            previous[next] = current;
            queue.Enqueue(next);
        }
    }

    return previous;
}

The previous dictionary acts as both visited set and path reconstruction map. Without visited tracking, a cycle can make traversal loop forever.

Use BFS for shortest unweighted paths and levels. Use DFS for reachability, cycle detection, topological algorithms and exhaustive exploration. Neither name tells you whether recursion is safe; that depends on graph depth and input trust.

Starting from London, BFS first visits every city one edge away, then every city two edges away. A queue preserves that layer order. DFS might follow London → Reading → Bristol before returning to explore Oxford. A stack preserves unfinished branches.

The visited set is essential. In a graph where A connects to B and B connects back to A, traversal without visited tracking never ends.

28. Topological sort for dependencies

A directed acyclic graph can be ordered so every dependency appears before its consumer. Build systems, course prerequisites and deployment plans use this.

Kahn’s algorithm calculates each vertex’s incoming-edge count, queues all zero-indegree vertices, removes them and reduces their neighbours’ counts. Complexity is O(V + E). If fewer than V vertices are emitted, a cycle exists.

This is a perfect example of data-structure cooperation: a dictionary stores indegrees, a queue stores ready work and adjacency lists expose dependants.

Do not return a partial ordering silently when a cycle exists. Report the dependency problem with enough context to fix it.

Example: Compile depends on Restore, and Test depends on Compile. A valid order is Restore, Compile, Test. If Restore also depends on Test, every task waits for another task and no valid order exists. Topological sorting both produces an order and detects that cycle.

29. Dijkstra’s shortest path

Dijkstra finds shortest paths from a source when edge weights are non-negative. The modern .NET implementation naturally uses PriorityQueue.

static Dictionary<T, double> Dijkstra<T>(
    T source,
    Func<T, IEnumerable<(T Node, double Cost)>> edges,
    IEqualityComparer<T>? comparer = null)
    where T : notnull
{
    var distance = new Dictionary<T, double>(comparer) { [source] = 0 };
    var frontier = new PriorityQueue<T, double>();
    frontier.Enqueue(source, 0);

    while (frontier.TryDequeue(out T? current, out double queuedDistance))
    {
        if (queuedDistance > distance[current]) continue; // stale queue entry

        foreach ((T next, double cost) in edges(current))
        {
            if (cost < 0) throw new ArgumentOutOfRangeException(nameof(edges), "Weights must be non-negative.");

            double candidate = queuedDistance + cost;
            if (distance.TryGetValue(next, out double known) && candidate >= known)
                continue;

            distance[next] = candidate;
            frontier.Enqueue(next, candidate);
        }
    }

    return distance;
}

Instead of decreasing an existing queue priority, this version enqueues the improved distance and skips stale entries later. With a binary-style heap the common complexity is O((V + E) log V), often written O(E log V) for connected sparse graphs.

Negative weights invalidate Dijkstra’s greedy assumption. Use Bellman-Ford or another appropriate algorithm. A fast algorithm with violated preconditions is an incorrect algorithm.

The word relax means “try to improve the best known distance.” If London to Reading costs 40 and Reading to Bristol costs 80, discovering Reading gives Bristol a candidate distance of 120. If another route later offers 100, relaxation replaces 120 with 100 and queues the improved candidate.

Use BFS instead when every edge has equal cost. Use Dijkstra only when weights are non-negative. State that precondition beside the implementation.

30. Minimum spanning trees

A minimum spanning tree connects all vertices of an undirected weighted graph with minimum total edge weight and no cycles.

Kruskal sorts edges by weight and adds an edge if it joins different components. A disjoint-set union structure provides near-constant amortised component checks through path compression and union by rank or size.

Prim grows one tree outward using a priority queue of candidate edges. Both are classic and useful for network layout and clustering-style problems.

Do not confuse minimum spanning tree with shortest paths. An MST minimises the total weight of the connecting tree; it does not guarantee the shortest route from one chosen vertex to every other.

Imagine connecting offices with cable. The goal is to connect every office while minimising total cable, not to minimise the journey from headquarters to each office. That is an MST problem. Kruskal grows a forest by taking safe cheap edges; Prim grows one connected tree outward.

Graph colouring: separate neighbours with limited labels

Graph colouring assigns colours to vertices so adjacent vertices receive different colours. The colours are abstract labels; they may represent exam time slots, radio frequencies, register assignments or colours on a map.

Suppose courses are connected when at least one student attends both. Connected courses cannot use the same exam slot. A valid vertex colouring becomes a conflict-free timetable.

Finding the minimum possible number of colours is difficult for general graphs, but a greedy algorithm quickly creates a valid colouring: process each vertex and give it the first colour not used by an already-coloured neighbour.

static Dictionary<T, int> GreedyColour<T>(
    IEnumerable<T> vertices,
    Func<T, IEnumerable<T>> neighbours,
    IEqualityComparer<T>? comparer = null)
    where T : notnull
{
    var colours = new Dictionary<T, int>(comparer);

    foreach (T vertex in vertices)
    {
        var unavailable = new HashSet<int>();

        foreach (T neighbour in neighbours(vertex))
        {
            if (colours.TryGetValue(neighbour, out int colour))
                unavailable.Add(colour);
        }

        int chosen = 0;
        while (unavailable.Contains(chosen))
            chosen++;

        colours[vertex] = chosen;
    }

    return colours;
}

This demonstrates several structures cooperating: an adjacency list supplies neighbours, a dictionary records each assignment, and a set tracks unavailable colours. The result is valid, but the number of colours can depend on vertex order and is not guaranteed minimal. “Greedy produces a solution” and “greedy produces the optimum” are separate claims.

31. Two pointers, sliding windows and prefix sums

Not every interview or production algorithm needs an exotic structure. A few patterns solve many array and string problems.

Two pointers move indexes through ordered or bounded data. In a sorted array, a left and right pointer can find a pair sum in O(n) rather than checking every pair in O(n²).

static bool HasPairWithSum(int[] sorted, int target)
{
    int left = 0;
    int right = sorted.Length - 1;

    while (left < right)
    {
        int sum = sorted[left] + sorted[right];
        if (sum == target) return true;

        if (sum < target)
            left++;   // We need a larger sum.
        else
            right--;  // We need a smaller sum.
    }

    return false;
}

For [1, 3, 4, 7, 9] and target 10, start with 1 and 9 and finish immediately. Each pointer moves only inward, so at most n total moves occur.

Sliding window maintains information about a contiguous range. A fixed-size moving average updates by removing the outgoing value and adding the incoming one, making each step O(1).

static int MaximumThreeItemTotal(int[] values)
{
    if (values.Length < 3)
        throw new ArgumentException("At least three values are required.");

    int window = values[0] + values[1] + values[2];
    int maximum = window;

    for (int right = 3; right < values.Length; right++)
    {
        window += values[right];     // Add the item entering the window.
        window -= values[right - 3]; // Remove the item leaving it.
        maximum = Math.Max(maximum, window);
    }

    return maximum;
}

Recalculating every three-item sum would repeat additions. The window remembers just enough state to update the answer.

Prefix sums precompute cumulative totals in O(n), then answer range-sum queries in O(1):

static long[] BuildPrefixSums(ReadOnlySpan<int> values)
{
    var prefix = new long[values.Length + 1];
    for (int i = 0; i < values.Length; i++)
        prefix[i + 1] = checked(prefix[i] + values[i]);
    return prefix;
}

static long RangeSum(long[] prefix, int startInclusive, int endExclusive) =>
    prefix[endExclusive] - prefix[startInclusive];

I used long because many int values can overflow an int total. Overflow is part of correctness.

For values [2, 4, 3], the prefix array is [0, 2, 6, 9]. The sum from indexes one inclusive to three exclusive is 9 - 2 = 7. Preprocessing costs O(n), but each later range query is O(1). This is worthwhile when queries are repeated.

Pattern-recognition questions: Is the answer about a pair of positions? Is it about one contiguous range? Are many range totals being requested? Those clues suggest two pointers, a sliding window or prefix sums.

32. Dynamic programming and memoisation

Dynamic programming applies when a problem has overlapping subproblems and an optimal solution can be built from smaller solutions. Memoisation caches top-down recursive results; tabulation builds bottom-up.

The naive Fibonacci recurrence is O(2ⁿ) because it repeats work. A bottom-up version is O(n) time and O(1) space:

static long Fibonacci(int n)
{
    ArgumentOutOfRangeException.ThrowIfNegative(n);
    if (n < 2) return n;

    long previous = 0;
    long current = 1;

    for (int i = 2; i <= n; i++)
        (previous, current) = (current, checked(previous + current));

    return current;
}

Dynamic programming is not “use a dictionary.” First define the state, transition, base cases and evaluation order. Then choose storage: array for dense integer states, dictionary for sparse composite states, or a few variables when only recent states matter.

Learn the four design questions

For Fibonacci:

1. State: F(i) means the Fibonacci value at position i.
2. Transition: F(i) = F(i - 1) + F(i - 2).
3. Base cases: F(0) = 0 and F(1) = 1.
4. Evaluation order: calculate smaller indexes before larger ones.

The naive recursive version calculates the same states repeatedly. For example, both F(5) and F(4) need F(3). Memoisation caches each result the first time. Tabulation starts at the base cases and builds upward. Because only two previous values are needed, the final implementation compresses O(n) table space to O(1).

Do not force dynamic programming onto every recursive problem. It helps specifically when subproblems overlap and cached smaller answers can construct the larger answer.

33. Greedy algorithms and backtracking

A greedy algorithm chooses the locally best next step. It is efficient only when the problem has a property proving those choices lead to a global optimum. Dijkstra and Kruskal are greedy with specific preconditions. “Pick what looks best” is not proof.

Backtracking explores a choice, recurses, and undoes it when the path cannot work. It solves constraint problems such as combinations, scheduling and puzzles, but worst-case search can be exponential. Pruning invalid partial solutions early is the main performance tool.

When an algorithm can explode exponentially, place limits around externally supplied input. Complexity can become a denial-of-service vulnerability.

Greedy and backtracking make opposite commitments. Greedy chooses and moves forward because a proof says reconsideration is unnecessary. Backtracking chooses tentatively, explores, then undoes the choice if it blocks a solution.

static void ChooseTwo(string[] names, int start, List<string> chosen)
{
    if (chosen.Count == 2)
    {
        Console.WriteLine(string.Join(" + ", chosen));
        return;
    }

    for (int i = start; i < names.Length; i++)
    {
        chosen.Add(names[i]);              // Choose
        ChooseTwo(names, i + 1, chosen);   // Explore
        chosen.RemoveAt(chosen.Count - 1); // Undo
    }
}

The choose–explore–undo rhythm is the heart of backtracking. Add pruning as soon as a partial choice cannot lead to a valid result.

Revision checkpoint for Part III

• Sorting organises data; searching exploits what is known about that organisation.
• Recursion needs a base case and measurable progress.
• Trees model hierarchy; heaps expose an extreme; tries share prefixes.
• Graph properties determine which traversal or path algorithm is valid.
• Two pointers, windows and prefix sums remove repeated work.
• Dynamic programming reuses overlapping subproblem results.
• Greedy requires proof; backtracking explores and undoes choices.

---

Part IV — Expressive and safe production code

Knowing an algorithm is only half of engineering. We must also understand when work executes, who owns data, what concurrency permits and how evidence changes our design.

34. LINQ: expressive, deferred and easy to misuse

LINQ is one of C#’s strengths. It describes transformations clearly, but you must understand execution.

Most IEnumerable operators are deferred. The query runs when enumerated, and repeated enumeration can repeat database calls or expensive computation.

IEnumerable<Order> query = orders.Where(order => order.Total > 100m);
Order[] snapshot = query.ToArray(); // Execute once and materialise intentionally.

Common mistakes include:

• calling Count() then iterating a non-collection sequence;
• using Any() and then First() when one operation can serve;
• nesting Contains over lists and creating O(nm);
• sorting before filtering when filtering first reduces work;
• accidental client evaluation around database queries;
• using LINQ allocation in a measured inner loop where a simple loop is clearer and faster.

Do not replace LINQ reflexively. Its clarity is valuable. Read execution plans and benchmark hot paths.

Separate the query from its execution

var numbers = new List<int> { 1, 2, 3 };
IEnumerable<int> evens = numbers.Where(number => number % 2 == 0);

numbers.Add(4);
Console.WriteLine(string.Join(", ", evens)); // 2, 4

Where created a recipe, not a frozen result. Enumeration happened after 4 was added. Materialising earlier changes the meaning:

int[] snapshot = numbers.Where(number => number % 2 == 0).ToArray();
numbers.Add(6);

Console.WriteLine(string.Join(", ", snapshot)); // The earlier snapshot has not changed.

Learn the operator families:

• Where filters;
• Select transforms each item;
• OrderBy and ThenBy order;
• GroupBy forms groups by a key;
• Any, All and Contains answer questions;
• FirstOrDefault selects one possible item;
• ToArray, ToList and ToDictionary execute and materialise.

For IQueryable from a database provider, the expression may be translated to SQL. Inspect generated queries and avoid assuming that ordinary-looking C# executes locally or cheaply.

Mentor's rule: be able to say when the query executes, how many times it executes, and whether it is in memory or translated by a provider.

35. Collection ownership and API design

The correct structure inside a method is only half the design. Decide who owns and may mutate it.

Returning IEnumerable promises enumeration, not immutability or repeatability. IReadOnlyList promises indexed reading through that reference, not that nobody else can mutate the underlying list. ImmutableArray provides a stronger immutable value-like snapshot. An array copy provides isolation at allocation cost.

public sealed class Basket
{
    private readonly List<BasketItem> _items = [];
    public IReadOnlyList<BasketItem> Items => _items;

    public void Add(BasketItem item)
    {
        ArgumentNullException.ThrowIfNull(item);
        _items.Add(item);
    }
}

This prevents callers from directly mutating the list through the property, but objects inside may still be mutable. Immutability is a design across the object graph.

A read-only view is not an immutable object

var source = new List<string> { "A" };
IReadOnlyList<string> view = source;

source.Add("B");
Console.WriteLine(view.Count); // 2

The view reference cannot call Add, but it observes changes made through source. If the caller requires a stable snapshot, copy or use a genuinely immutable value:

ImmutableArray<string> snapshot = source.ToImmutableArray();
source.Add("C");

Console.WriteLine(snapshot.Length); // Still 2

Ownership asks who may change data and for how long references remain valid. Good APIs make this visible. Accept IEnumerable when enumeration is enough, IReadOnlyList when indexed reading matters, and a mutable collection only when caller mutation is part of the contract.

36. Concurrency changes the choice

Ordinary generic collections are not safe for unsynchronised concurrent mutation. Options include locking, concurrent collections, immutable snapshots and channels.

ConcurrentDictionary supports atomic operations, but compound business decisions still need care. GetOrAdd may invoke a value factory more than once under contention even though one value wins; the factory should be safe accordingly.

Avoid holding a lock while awaiting. Protect small synchronous state changes or use an async coordination primitive where appropriate. Thread safety is not achieved by changing Dictionary to ConcurrentDictionary if several operations together form one invariant.

Understand the race before choosing the tool

if (!balances.ContainsKey(accountId))
    balances[accountId] = 0m;

Two threads can both observe that the key is absent and both attempt the update. The check and change form one logical operation but are written as separate steps. A concurrent collection offers atomic methods such as TryAdd, AddOrUpdate and GetOrAdd, but business invariants spanning several keys or systems may still require a lock, transaction or redesigned ownership model.

Concurrency concepts:

• race condition: the result depends on unpredictable timing;
• atomic operation: observers cannot see a partially completed operation;
• contention: multiple workers compete for the same protected resource;
• backpressure: producers slow down when consumers cannot keep up;
• cancellation: work can stop cooperatively when no longer needed.

Prefer simple ownership. One consumer processing messages from a channel can sometimes remove shared mutation entirely, which is easier to reason about than adding locks around everything.

37. Measure with the right tools

Use BenchmarkDotNet for microbenchmarks rather than a single Stopwatch run. It handles warm-up, multiple iterations, runtime effects and statistical reporting. Measure allocations as well as elapsed time.

Production diagnosis includes dotnet-counters, dotnet-trace, dotnet-gcdump, profilers and application telemetry. Useful signals include allocation rate, GC counts and pause time, heap size, lock contention and request percentiles.

Benchmark representative data sizes and distributions. A dictionary test with random keys may not represent your case-insensitive product codes. Include setup fairly: if one approach builds an index, decide whether construction belongs inside the measured operation based on the real lifecycle.

Form a hypothesis before opening a profiler

Use this loop:

1. Observe a user-visible or operational problem.
2. Record a baseline with representative data.
3. Use profiling evidence to locate the dominant cost.
4. Change one relevant design choice.
5. Measure again and compare correctness as well as speed.

[MemoryDiagnoser]
public class MembershipBenchmarks
{
    private readonly List<int> _list = Enumerable.Range(0, 10_000).ToList();
    private readonly HashSet<int> _set = Enumerable.Range(0, 10_000).ToHashSet();

    [Benchmark(Baseline = true)]
    public bool ListLookup() => _list.Contains(9_999);

    [Benchmark]
    public bool SetLookup() => _set.Contains(9_999);
}

This benchmark isolates repeated membership lookup. It does not prove a set is always better; it excludes set construction and memory because the intended lifecycle builds once and queries many times. Document such assumptions.

38. Where C# 14 and .NET 10 fit

C# 14 adds useful expressiveness, but algorithms remain recognisable.

• first-class span conversions make allocation-conscious APIs easier to call;
• extension blocks can add extension properties and methods to collection-oriented APIs;
• field simplifies validated properties;
• null-conditional assignment can update when a receiver exists;
• lambda parameter modifiers are more concise;
• nameof(List<>) supports unbound generic types.

For example, an extension property can express a reusable collection observation:

public static class CollectionExtensions
{
    extension<T>(IReadOnlyCollection<T> source)
    {
        public bool IsEmpty => source.Count == 0;
    }
}

Use extension members to improve a coherent API, not to hide expensive work behind property syntax. A property named IsEmpty should not enumerate a remote stream.

.NET 10 is an LTS release with runtime improvements in JIT optimisation and stack-allocation opportunities, plus library improvements across collections, numerics, diagnostics and serialisation. Let the platform improvements help, but retain version-independent reasoning about complexity, allocation and correctness.

Read new language and runtime features in layers. First ask what problem the feature solves. Then write the ordinary version. Finally compare the modern form. For example, an extension property can make a repeated concept discoverable, but hiding enumeration or I/O behind property syntax would mislead callers.

The durable lesson is that versions improve expression and implementation; they do not change what FIFO means, why hash equality must agree, or how quadratic growth behaves.

39. How I choose a structure in production

Here is the decision table I use with junior developers:

This is a starting point, not a law. Verify scale, mutation patterns, concurrency and memory.

Work through one production decision

Requirement: an API loads 50,000 country records at startup, then serves millions of case-insensitive lookups by code without changing the data.

1. Dominant operation: lookup by unique string key.
2. Ordering: none required.
3. Mutation: build once, then read only.
4. Concurrency: many readers.
5. Starting choice: build a Dictionary with OrdinalIgnoreCase.
6. Refined choice: convert it to FrozenDictionary after construction.
7. Evidence: benchmark lookup and startup cost using representative codes before accepting extra complexity.

Now change one fact: administrators edit countries every minute. Frozen data no longer fits the lifecycle. A normal dictionary behind controlled synchronisation or immutable snapshots may be more appropriate. One changed requirement changes the structure.

The repeatable decision template is:

Data shape:
Dominant operations:
Maximum scale:
Ordering and uniqueness:
Mutation and ownership:
Concurrency:
Expected time and space complexity:
Simplest standard .NET choice:
Evidence needed before specialising:

40. The production mistakes I want you to avoid

1. Saying value types always live on the stack.
2. Choosing List for repeated membership checks.
3. Using mutable objects as dictionary keys.
4. Forgetting an explicit string comparer.
5. Depending on incidental dictionary enumeration order.
6. Writing your own sort when the framework implementation fits.
7. Running binary search over incompatibly sorted data.
8. Recursing through unbounded external input.
9. Ignoring integer overflow in counts, distances and sums.
10. Calling GC.Collect() to solve an unmeasured problem.
11. Forgetting to dispose resource owners or return pooled arrays.
12. Holding pooled memory after it has been returned.
13. Using Span where an async lifetime requires Memory.
14. Assuming IReadOnlyList makes the object graph immutable.
15. Enumerating a deferred LINQ query several times unknowingly.
16. Using concurrent collections without protecting multi-step invariants.
17. Treating average O(1) as a universal guarantee.
18. Optimising constants while retaining the wrong complexity class.
19. Benchmarking unrealistic tiny inputs only.
20. Selecting an advanced structure because it sounds senior.

Do not memorise this as a fear list. Each mistake violates one of four principles:

• model correctly: understand assignment, equality, ordering and algorithm preconditions;
• bound growth: consider time, memory, recursion, queues and input size;
• make ownership explicit: control mutation, disposal and concurrency;
• measure honestly: use real data and include the correct lifecycle costs.

When reviewing code, explain the consequence and the safer model. “This is bad” teaches little. “This list membership check sits inside a loop, so 100,000 by 100,000 inputs can create ten billion comparisons; building a set once changes repeated membership to average constant time” teaches engineering.

41. A learning route from junior to master

Write the structures yourself once, then use the platform types professionally.

Beginner

Implement linear search, binary search, stack and queue exercises. Trace each operation on paper. State time and space complexity before running code.

Build a console-based support desk. Enqueue three tickets, process them FIFO, push processed actions onto an undo stack, and store tickets by ID in a dictionary. Explain why each collection fits.

Developing

Build a hash table with collision handling, a binary search tree and heap. The objective is not replacing .NET; it is understanding resizing, equality, balance and invariants.

Add measurements for 10, 1,000 and 100,000 items. Compare list membership with set membership. Record construction time separately from lookup time so you learn when an index pays for itself.

Proficient

Implement BFS, DFS, topological sort and Dijkstra. Add invalid-input tests, cycle tests, overflow handling and cancellation for long operations.

Model a delivery network. Begin unweighted and use BFS, add non-negative distances and use Dijkstra, then model build dependencies and use topological sorting. Write the graph preconditions above each algorithm.

Advanced

Profile a real service. Replace one proven bottleneck through a better structure or reduced allocation. Benchmark the change, document the trade-off and keep the simpler design when improvement is insignificant.

Review collection ownership and concurrency at the same time. Add a bounded channel to a producer-consumer demo, deliberately make the producer faster, and observe how bounded capacity prevents uncontrolled growth.

Master level

Teach the reasoning. A master does not recite that dictionary lookup is O(1). They ask about comparer cost, key stability, collision behaviour, build frequency, memory, concurrency, data distribution and whether a database index belongs on the other side of the boundary.

Take one design from your own work and write a one-page decision record using the template in Section 39. Ask another developer to challenge your assumptions. Mastery includes changing your mind when evidence changes.

Final revision questions

Answer these without looking back, then revisit the relevant section for anything uncertain:

1. What is copied when a value type is assigned? What is copied for a reference type?
2. Why can a managed application still leak memory?
3. When is a span useful, and why can it not cross an await?
4. Why is List.Add O(1) amortised rather than O(1) for every call?
5. What is the difference between a dictionary and a set?
6. Why does binary search require sorted data with a compatible comparer?
7. What base conditions make recursion safe?
8. Why does BFS use a queue while iterative DFS uses a stack?
9. Why do negative edge weights invalidate Dijkstra's algorithm?
10. What makes a dynamic-programming problem different from ordinary recursion?
11. When does a deferred LINQ query execute?
12. Why is IReadOnlyList not the same as immutable data?
13. What does a concurrent collection make atomic, and what can still race?
14. When should index-construction cost be included in a benchmark?
15. Which requirements would make you replace a List with another structure?

Capstone exercise: build a small delivery planner

Create a console application with these steps:

1. Store depots by unique code in a case-insensitive dictionary.
2. Represent directed routes as an adjacency list.
3. Use a hash set to reject duplicate route IDs.
4. Use BFS to find the fewest-hop route.
5. Add non-negative distances and use Dijkstra for the lowest-distance route.
6. Queue delivery requests and use a priority queue for urgent jobs.
7. Return results through read-only or immutable contracts.
8. Add tests for a missing depot, a cycle, a disconnected destination and an invalid negative distance.
9. State the time and additional space complexity of each important operation.
10. Benchmark one realistic repeated lookup and explain whether the result changes your design.

This one project revises types, equality, dictionaries, sets, queues, priority queues, graphs, traversal, shortest paths, ownership, validation, complexity and measurement. Build it in stages; do not attempt everything in one sitting.

Final advice from Faz

Data structures and algorithms are not interview theatre. They are vocabulary for making software decisions.

When a page is slow, you should recognise the nested scan. When memory grows, you should inspect ownership and reachability. When a background queue expands, you should see missing backpressure. When a graph traversal loops, you should look for visited state. When an API allocates heavily, you should know when spans or pooling might help—and when they would only make the code harder.

Do not chase cleverness. Choose the simplest structure that preserves the required invariants and meets measured constraints. Use the mature .NET collection whenever it fits. Write a custom structure only when the domain or evidence justifies owning its bugs and maintenance.

The progression I want you to remember is:

Correctness first.
Choose by dominant operations.
State the complexity.
Protect memory and ownership.
Measure realistic workloads.
Optimise only with evidence.
Explain the trade-off clearly.

If you can do that consistently in C# 14 and .NET 10, you are no longer merely solving algorithm exercises. You are engineering dependable software.

The one-minute collection revision map

Need positions and a fixed size?             Array
Need positions and a changing size?          List
Need unique membership?                      HashSet
Need a value by unique key?                  Dictionary
Need sorted unique values or sorted keys?    SortedSet / SortedDictionary
Need last-in-first-out behaviour?             Stack
Need first-in-first-out behaviour?            Queue
Need the most urgent item next?               PriorityQueue
Need asynchronous bounded work?               Channel
Need a finished read-heavy lookup?            Frozen collection
Need snapshot-style state changes?             Immutable collection
Need arbitrary relationships?                 Graph representation

When uncertain, return to the six opening questions. Describe the data, dominant operations, scale, rules, memory and concurrency. You are not expected to remember a magic answer; you are expected to reason toward one.

References used to modernise these notes

• Marcin Jamro, *C# Data Structures and Algorithms: Explore the possibilities of C# for developing a variety of efficient applications*, Packt Publishing, 2018. This book supplied the original learning scope; the explanations and examples in this article have been rewritten and modernised for C# 14 and .NET 10.
• What’s new in C# 14
• What’s new in .NET 10
• .NET garbage-collection fundamentals
• Memory- and span-related types
• FrozenDictionary
• .NET 10 generic collections