Free Handbook · Every example compiled & verified

Data Structures & Algorithms

Build stacks, queues, linked lists, trees, heaps and graphs by hand in C#, then use List, Dictionary, PriorityQueue and SortedSet like a pro.

0 / 142 lessons🔥 0 day streak

ShareX LinkedIn

Module 13 · what you'll be able to do

Pick a .NET collection from its Big-O cost instead of defaulting to List for everything
Build a generic stack, ring-buffer queue, linked list, binary search tree and min-heap by hand
Use Dictionary, HashSet, Stack, Queue, LinkedList, SortedSet and PriorityQueue correctly
Traverse a graph with BFS and DFS, and find shortest paths with Dijkstra
Write binary search, merge sort and bottom-up dynamic programming, and know what Array.Sort and OrderBy do differently

The cost table: pick a structure by what it costs

A data structure is a trade-off: it makes some operations cheap by making others expensive. Big-O describes how the work grows as the input grows — O(1) means "the same work no matter how big", O(n) means "work grows in step with the size", O(log n) means "doubling the input adds one step". Choosing the right collection is usually the single biggest performance decision in everyday C# code, far bigger than any micro-optimisation.

Memorise the shape of this table, not the exact cells: hash structures for "have I seen this?", trees for "keep it sorted", heaps for "give me the smallest next".
.NET type	Index / lookup	Search	Add	Remove	Built on
`T[]`	O(1)	O(n)	— fixed size	—	contiguous memory
`List<T>`	O(1)	O(n)	O(1) amortised at end, O(n) Insert	O(1) at end, O(n) elsewhere	resizable array
`Dictionary<K,V>`	O(1) avg by key	O(1) avg by key	O(1) avg	O(1) avg	hash table
`HashSet<T>`	—	O(1) avg Contains	O(1) avg	O(1) avg	hash table
`Stack<T>`	O(1) top only	O(n)	O(1) Push	O(1) Pop	array
`Queue<T>`	O(1) front only	O(n)	O(1) Enqueue	O(1) Dequeue	circular array
`LinkedList<T>`	O(n)	O(n)	O(1) at a known node	O(1) at a known node	doubly linked nodes
`SortedSet<T>` / `SortedDictionary<K,V>`	O(log n)	O(log n)	O(log n)	O(log n)	red-black tree
`PriorityQueue<TElement,TPriority>`	O(1) Peek min	O(n)	O(log n)	O(log n) Dequeue	array-backed 4-ary min-heap

C#Program.cs

int[] data = Enumerable.Range(0, 1_000_000).ToArray();
int target = 999_999;

int linearSteps = 0;
foreach (int x in data)
{
    linearSteps++;
    if (x == target) break;
}

int binarySteps = 0, lo = 0, hi = data.Length - 1;
while (lo <= hi)
{
    binarySteps++;
    int mid = lo + (hi - lo) / 2;
    if (data[mid] == target) break;
    if (data[mid] < target) lo = mid + 1;
    else hi = mid - 1;
}

Console.WriteLine($"Linear search: {linearSteps} steps");
Console.WriteLine($"Binary search: {binarySteps} steps");

Outputcompiled & run with real C#

Linear search: 1000000 steps
Binary search: 20 steps

The same question — "where is 999,999?" — answered by O(n) and O(log n) algorithms over one million sorted numbers.

Your turn

Change target to 0. Linear search now wins. Why does Big-O still say binary search is the better algorithm?

Arrays and List<T>: amortised O(1) append

An array (int[]) is a fixed block of memory: reading a[i] is O(1) because the address is computed, not searched. List<T> wraps an array and doubles it when it fills up. Copying on growth is O(n), but it happens so rarely that Add is O(1) on average — "amortised O(1)". Insert(0, x) and RemoveAt(0) are O(n): every later element shifts one slot.

C#Program.cs

var list = new List<int>();
int lastCapacity = -1;
for (int i = 0; i < 20; i++)
{
    list.Add(i);
    if (list.Capacity != lastCapacity)
    {
        Console.WriteLine($"Count {list.Count,2} -> Capacity {list.Capacity}");
        lastCapacity = list.Capacity;
    }
}

var sized = new List<int>(capacity: 1000);
Console.WriteLine($"Pre-sized: Count {sized.Count}, Capacity {sized.Capacity}");

Outputcompiled & run with real C#

Count  1 -> Capacity 4
Count  5 -> Capacity 8
Count  9 -> Capacity 16
Count 17 -> Capacity 32
Pre-sized: Count 0, Capacity 1000

Your turn

Time 1,000,000 Add calls with System.Diagnostics.Stopwatch, once with an empty list and once with new List<int>(1_000_000). The pre-sized list skips every resize.

In real code

Expose IReadOnlyList<T> or IEnumerable<T> from a method, and keep the concrete List<T> private. Callers then cannot mutate your internal state, and you are free to change the implementation later.

Dictionary<TKey, TValue> and HashSet<T>

A hash table turns a key into a number (GetHashCode()), uses that number to pick a bucket, then confirms the match with Equals(). That is why lookups are O(1) on average. Use TryGetValue instead of ContainsKey followed by the indexer — one lookup instead of two — and never rely on the order a Dictionary enumerates in: it is not part of the contract. Sort explicitly when order matters.

C#Program.cs

string text = "the cat and the hat and the bat";
var counts = new Dictionary<string, int>();
foreach (string word in text.Split(' '))
{
    counts[word] = counts.GetValueOrDefault(word) + 1;
}

foreach (var (word, n) in counts.OrderByDescending(p => p.Value).ThenBy(p => p.Key))
{
    Console.WriteLine($"{word}: {n}");
}

if (counts.TryGetValue("cat", out int cats))
{
    Console.WriteLine($"cat appears {cats} time(s)");
}
Console.WriteLine(counts.ContainsKey("dog"));

Outputcompiled & run with real C#

the: 3
and: 2
bat: 1
cat: 1
hat: 1
cat appears 1 time(s)
False

Your turn

Make the count case-insensitive by passing StringComparer.OrdinalIgnoreCase to the Dictionary constructor, then add "The" to the text.

C#Program.cs

var backend = new HashSet<string> { "csharp", "sql", "docker", "azure" };
var frontend = new HashSet<string> { "typescript", "css", "docker", "sql" };

Console.WriteLine(backend.Add("sql")); // already present

var both = new HashSet<string>(backend);
both.IntersectWith(frontend);
Console.WriteLine(string.Join(", ", both.Order()));

var all = new HashSet<string>(backend);
all.UnionWith(frontend);
Console.WriteLine(all.Count);

var onlyBackend = new HashSet<string>(backend);
onlyBackend.ExceptWith(frontend);
Console.WriteLine(string.Join(", ", onlyBackend.Order()));

Outputcompiled & run with real C#

False
docker, sql
6
azure, csharp

Keys must have a stable hash and a matching Equals. A record gets value-based equality generated for it; a plain class compares by reference, so two objects with the same data are different keys.

C#Program.cs

var records = new HashSet<Point> { new Point(1, 2) };
Console.WriteLine(records.Contains(new Point(1, 2)));

var classes = new HashSet<PointClass> { new PointClass(1, 2) };
Console.WriteLine(classes.Contains(new PointClass(1, 2)));

record Point(int X, int Y);

class PointClass(int x, int y)
{
    public int X { get; } = x;
    public int Y { get; } = y;
}

Outputcompiled & run with real C#

True
False

Your turn

Make PointClass work as a key by overriding Equals(object?) and GetHashCode() (use HashCode.Combine(X, Y)).

Stack<T>: last in, first out

A stack is a pile of plates: push onto the top, pop from the top. Undo history, the call stack itself, bracket matching and depth-first search all use one. Building it by hand shows why both operations are O(1): the stack only ever touches the last slot of an array.

C#Program.cs

var numbers = new ArrayStack<int>();
numbers.Push(10);
numbers.Push(20);
numbers.Push(30);
Console.WriteLine($"{numbers.Pop()} {numbers.Count} {numbers.Peek()}");

var words = new ArrayStack<string>();
words.Push("a");
words.Push("b");
Console.WriteLine($"{words.Pop()} {words.Pop()} {words.Count}");

class ArrayStack<T>
{
    private T[] _items = new T[4];
    public int Count { get; private set; }

    public void Push(T item)
    {
        if (Count == _items.Length) Array.Resize(ref _items, _items.Length * 2);
        _items[Count++] = item;
    }

    public T Pop()
    {
        if (Count == 0) throw new InvalidOperationException("Stack is empty");
        T item = _items[--Count];
        _items[Count] = default!; // let the GC collect it
        return item;
    }

    public T Peek() =>
        Count == 0 ? throw new InvalidOperationException("Stack is empty") : _items[Count - 1];
}

Outputcompiled & run with real C#

30 2 20
b a 0

Your turn

Push 10 items and print _items.Length via a new property. It should have grown 4 → 8 → 16.

The built-in Stack<T> has the same shape plus TryPop and TryPeek, which return false instead of throwing. The classic interview use is checking balanced brackets:

C#Program.cs

Console.WriteLine(IsBalanced("{[()]}"));
Console.WriteLine(IsBalanced("([)]"));
Console.WriteLine(IsBalanced("(("));

static bool IsBalanced(string s)
{
    var pairs = new Dictionary<char, char> { [')'] = '(', [']'] = '[', ['}'] = '{' };
    var stack = new Stack<char>();
    foreach (char c in s)
    {
        if (c is '(' or '[' or '{') stack.Push(c);
        else if (pairs.TryGetValue(c, out char open))
        {
            if (!stack.TryPop(out char top) || top != open) return false;
        }
    }
    return stack.Count == 0;
}

Outputcompiled & run with real C#

True
False
False

Queue<T>: a ring buffer, and deques

A queue is first in, first out — a line at a counter. The naive version, a List<T> with RemoveAt(0), is O(n) per dequeue because every element shifts. .NET's Queue<T> avoids that with a ring buffer: a head index and a tail index that wrap around the end of the array.

C#Program.cs

var q = new RingQueue<string>(capacity: 3);
q.Enqueue("ada");
q.Enqueue("bob");
q.Enqueue("cy");
Console.WriteLine($"{q.Dequeue()} {q.Dequeue()} {q.Count}");

q.Enqueue("dee"); // tail wraps to index 0
q.Enqueue("eve");
var rest = new List<string>();
while (q.Count > 0) rest.Add(q.Dequeue());
Console.WriteLine(string.Join(" ", rest));

class RingQueue<T>(int capacity)
{
    private readonly T[] _items = new T[capacity];
    private int _head, _tail;
    public int Count { get; private set; }

    public void Enqueue(T item)
    {
        if (Count == _items.Length) throw new InvalidOperationException("Queue is full");
        _items[_tail] = item;
        _tail = (_tail + 1) % _items.Length;
        Count++;
    }

    public T Dequeue()
    {
        if (Count == 0) throw new InvalidOperationException("Queue is empty");
        T item = _items[_head];
        _head = (_head + 1) % _items.Length;
        Count--;
        return item;
    }
}

Outputcompiled & run with real C#

ada bob 1
cy dee eve

Your turn

Instead of throwing when full, grow the array: copy the items in order starting from _head into a new array twice the size, then reset _head = 0 and _tail = Count.

.NET has no dedicated deque type. When you need to add and remove at both ends, use LinkedList<T> (AddFirst, AddLast, RemoveFirst, RemoveLast are all O(1)).

C#Program.cs

var tickets = new Queue<string>();
tickets.Enqueue("T1");
tickets.Enqueue("T2");
tickets.Enqueue("T3");
Console.WriteLine(tickets.Peek());
Console.WriteLine(tickets.Dequeue());
Console.WriteLine(tickets.TryDequeue(out string? next) ? next : "none");
Console.WriteLine(tickets.Count);

var deque = new LinkedList<int>();
deque.AddLast(2);
deque.AddLast(3);
deque.AddFirst(1);
Console.WriteLine(string.Join(" ", deque));
deque.RemoveFirst();
deque.RemoveLast();
Console.WriteLine(string.Join(" ", deque));

Outputcompiled & run with real C#

Linked lists: by hand, then LinkedList<T>

A linked list is a chain of nodes, each holding a value and a reference to the next node. There is no index: reaching item 500 means walking 500 links, O(n). What it buys you is O(1) insert and remove once you hold a node — no shifting. With nullable reference types on, Node<T>? Next makes the compiler force a null check before you follow a link.

C#Program.cs

var list = new SinglyLinkedList<int>();
foreach (int n in new[] { 1, 2, 3, 4 }) list.AddLast(n);
Console.WriteLine(list);
list.Reverse();
Console.WriteLine(list);
list.AddFirst(0);
Console.WriteLine($"{list} (count {list.Count})");

class Node<T>(T value)
{
    public T Value { get; } = value;
    public Node<T>? Next { get; set; }
}

class SinglyLinkedList<T>
{
    private Node<T>? _head, _tail;
    public int Count { get; private set; }

    public void AddFirst(T value)
    {
        var node = new Node<T>(value) { Next = _head };
        _head = node;
        _tail ??= node;
        Count++;
    }

    public void AddLast(T value)
    {
        var node = new Node<T>(value);
        if (_tail is null) _head = _tail = node;
        else { _tail.Next = node; _tail = node; }
        Count++;
    }

    public void Reverse()
    {
        Node<T>? prev = null, current = _head;
        _tail = _head;
        while (current is not null)
        {
            Node<T>? next = current.Next;
            current.Next = prev;
            prev = current;
            current = next;
        }
        _head = prev;
    }

    public override string ToString()
    {
        var parts = new List<string>();
        for (var n = _head; n is not null; n = n.Next) parts.Add(n.Value?.ToString() ?? "null");
        return string.Join(" -> ", parts);
    }
}

Outputcompiled & run with real C#

1 -> 2 -> 3 -> 4
4 -> 3 -> 2 -> 1
0 -> 4 -> 3 -> 2 -> 1 (count 5)

Your turn

Add bool Remove(T value). The hard cases are removing the head, removing the tail (update _tail), and a value that is not there.

VisualizeReversing 1 -> 2 -> 3 in placeStep 1 / 9

1Node? prev = null, current = head; // head is 1
2while (current is not null)
3{
4    Node? next = current.Next;
5    current.Next = prev;
6    prev = current;
7    current = next;
8}
9head = prev;

Line 1

Start with nothing behind us and the head in hand.

Variables now

`prev`	`null`
`current`	`1`

All 9 steps as a table

Step	Line	What happened	Variables now
1	1	Start with nothing behind us and the head in hand.	`prev = null` `current = 1`
2	4	Save the rest of the list before cutting the link.	`next = 2`
3	5	Point node 1 backwards. It is now the tail.	`1.Next = null`
4	7	Step forward: prev = 1, current = 2.	`prev = 1` `current = 2`
5	5	Second pass: next = 3, then node 2 points back at 1.	`next = 3` `2.Next = 1`
6	7	prev = 2, current = 3.	`prev = 2` `current = 3`
7	5	Third pass: next = null, node 3 points back at 2.	`next = null` `3.Next = 2`
8	7	prev = 3, current = null, so the loop ends.	`prev = 3` `current = null`
9	9	The last node we touched is the new head: 3 -> 2 -> 1. O(n) time, O(1) extra memory.	`head = 3`

The built-in LinkedList<T> is doubly linked and hands you LinkedListNode<T> objects, so you can insert before or after a node you already found without walking the list again.

C#Program.cs

var playlist = new LinkedList<string>(new[] { "intro", "verse", "outro" });
LinkedListNode<string> verse = playlist.Find("verse")!;
playlist.AddAfter(verse, "chorus");
playlist.AddBefore(verse, "hook");
Console.WriteLine(string.Join(" > ", playlist));

playlist.Remove(verse); // O(1): we already hold the node
Console.WriteLine(string.Join(" > ", playlist));
Console.WriteLine($"{playlist.First!.Value} ... {playlist.Last!.Value}");

Outputcompiled & run with real C#

intro > hook > verse > chorus > outro
intro > hook > chorus > outro
intro ... outro

LinkedList<T> is rarely the fastest choice

Each node is a separate heap object, so walking the list jumps around memory and misses the CPU cache. For most workloads List<T> beats it even for middle inserts up to thousands of items. Reach for LinkedList<T> when you genuinely hold node references — an LRU cache (Module 15) is the textbook case.

Recursion and the call stack

A recursive method calls itself on a smaller input until it reaches a base case it can answer directly. Every call pushes a frame onto the thread's call stack (about 1 MB by default). Recurse too deep and the process dies with a StackOverflowException — which, unlike other exceptions, cannot be caught in .NET. For deep inputs, convert the recursion to a loop with an explicit Stack<T>.

C#Program.cs

Console.WriteLine(Factorial(5));
Console.WriteLine(SumDigits(98765));
Console.WriteLine(Power(2, 10));

static long Factorial(int n) => n <= 1 ? 1 : n * Factorial(n - 1);

static int SumDigits(int n) => n < 10 ? n : n % 10 + SumDigits(n / 10);

// O(log e): halve the exponent each call instead of multiplying e times
static long Power(long b, int e)
{
    if (e == 0) return 1;
    long half = Power(b, e / 2);
    return e % 2 == 0 ? half * half : half * half * b;
}

Outputcompiled & run with real C#

120
35
1024

Your turn

Write static int CountDown(int n) recursively and call it with 1,000,000. Then rewrite it as a loop. Notice the first version crashes the whole process.

VisualizeFactorial(3) winding down and back upStep 1 / 7

1Console.WriteLine(Factorial(3));
2 
3static long Factorial(int n)
4{
5    if (n <= 1) return 1;
6    return n * Factorial(n - 1);
7}

Line 1

Call Factorial(3). A frame for n = 3 goes on the stack.

Variables now

n 3

All 7 steps as a table

Step	Line	What happened	Variables now
1	1	Call Factorial(3). A frame for n = 3 goes on the stack.	`n = 3`
2	6	n is not 1, so it needs Factorial(2) first. A second frame goes on top.	`n = 2`
3	6	Still not the base case: push a third frame for Factorial(1).	`n = 1`
4	5	Base case. Factorial(1) returns 1 and its frame is popped.	`returns = 1`
5	6	Back in the n = 2 frame: 2 * 1 = 2.	`n = 2` `returns = 2`
6	6	Back in the n = 3 frame: 3 * 2 = 6.	`n = 3` `returns = 6`
7	1	The stack is empty again and 6 is printed.

Binary search trees, and SortedSet<T>

A binary search tree keeps every value smaller than a node in its left subtree and every larger value in its right subtree. Search, insert and delete follow one path from the root, so they cost O(height). A balanced tree has height about log n; a tree fed already-sorted data degenerates into a linked list with height n. The generic constraint where T : IComparable<T> is what lets the tree call CompareTo.

C#Program.cs

var tree = new Bst<int>();
foreach (int n in new[] { 50, 30, 70, 20, 40, 60, 80 }) tree.Insert(n);
Console.WriteLine(string.Join(" ", tree.InOrder()));
Console.WriteLine($"{tree.Contains(60)} {tree.Contains(65)}");
Console.WriteLine($"height {tree.Height()}");

class Bst<T> where T : IComparable<T>
{
    private sealed class Node(T value)
    {
        public T Value { get; } = value;
        public Node? Left { get; set; }
        public Node? Right { get; set; }
    }

    private Node? _root;

    public void Insert(T value) => _root = Insert(_root, value);

    private static Node Insert(Node? node, T value)
    {
        if (node is null) return new Node(value);
        int cmp = value.CompareTo(node.Value);
        if (cmp < 0) node.Left = Insert(node.Left, value);
        else if (cmp > 0) node.Right = Insert(node.Right, value);
        return node;
    }

    public bool Contains(T value)
    {
        Node? n = _root;
        while (n is not null)
        {
            int cmp = value.CompareTo(n.Value);
            if (cmp == 0) return true;
            n = cmp < 0 ? n.Left : n.Right;
        }
        return false;
    }

    public IEnumerable<T> InOrder() => Walk(_root);

    private static IEnumerable<T> Walk(Node? n)
    {
        if (n is null) yield break;
        foreach (T v in Walk(n.Left)) yield return v;
        yield return n.Value;
        foreach (T v in Walk(n.Right)) yield return v;
    }

    public int Height() => Height(_root);

    private static int Height(Node? n) => n is null ? 0 : 1 + Math.Max(Height(n.Left), Height(n.Right));
}

Outputcompiled & run with real C#

20 30 40 50 60 70 80
True False
height 3

Your turn

Insert 10, 20, 30, 40, 50, 60, 70 in that order into a fresh tree and print the height. That is the degenerate case a self-balancing tree prevents.

You will almost never ship a hand-written tree. SortedSet<T> and SortedDictionary<TKey,TValue> are red-black trees that rebalance themselves, so every operation stays O(log n). They enumerate in sorted order and support range queries.

C#Program.cs

var scores = new SortedSet<int> { 72, 95, 60, 88, 95, 41 };
Console.WriteLine(string.Join(" ", scores));
Console.WriteLine($"min {scores.Min}, max {scores.Max}");
Console.WriteLine(string.Join(" ", scores.GetViewBetween(60, 90)));

var lengths = new SortedDictionary<string, int> { ["pear"] = 4, ["fig"] = 3, ["banana"] = 6 };
foreach (var (fruit, len) in lengths)
{
    Console.WriteLine($"{fruit}={len}");
}

Outputcompiled & run with real C#

41 60 72 88 95
min 41, max 95
60 72 88
banana=6
fig=3
pear=4

Heaps and PriorityQueue<TElement, TPriority>

A min-heap is a binary tree stored in an array where every parent is smaller than its children. The smallest item is always at index 0 (O(1) to peek); adding or removing moves an item up or down one path (O(log n)). For index i, the children live at 2i + 1 and 2i + 2 and the parent at (i - 1) / 2 — no node objects needed.

C#Program.cs

var heap = new MinHeap<int>();
foreach (int n in new[] { 5, 3, 8, 1, 9, 2 }) heap.Push(n);
var drained = new List<int>();
while (heap.Count > 0) drained.Add(heap.Pop());
Console.WriteLine(string.Join(" ", drained));

class MinHeap<T> where T : IComparable<T>
{
    private readonly List<T> _items = new();
    public int Count => _items.Count;

    public void Push(T value)
    {
        _items.Add(value);
        int i = _items.Count - 1;
        while (i > 0)
        {
            int parent = (i - 1) / 2;
            if (_items[i].CompareTo(_items[parent]) >= 0) break;
            (_items[i], _items[parent]) = (_items[parent], _items[i]);
            i = parent;
        }
    }

    public T Pop()
    {
        if (_items.Count == 0) throw new InvalidOperationException("Heap is empty");
        T top = _items[0];
        _items[0] = _items[^1];
        _items.RemoveAt(_items.Count - 1);
        int i = 0;
        while (true)
        {
            int left = 2 * i + 1, right = left + 1, smallest = i;
            if (left < _items.Count && _items[left].CompareTo(_items[smallest]) < 0) smallest = left;
            if (right < _items.Count && _items[right].CompareTo(_items[smallest]) < 0) smallest = right;
            if (smallest == i) break;
            (_items[i], _items[smallest]) = (_items[smallest], _items[i]);
            i = smallest;
        }
        return top;
    }
}

Outputcompiled & run with real C#

1 2 3 5 8 9

Pushing n items and popping them all is heapsort: O(n log n).

.NET 6 added PriorityQueue<TElement, TPriority>. The element and its priority are separate, so you can queue a job by a number without the job type implementing anything. Lowest priority value comes out first; pass a reversed comparer for a max-heap. Two things it does not do: it is not stable (equal priorities come out in no guaranteed order) and it cannot change an item's priority in place — enqueue it again and skip stale entries when they surface.

C#Program.cs

var jobs = new PriorityQueue<string, int>();
jobs.Enqueue("send newsletter", 3);
jobs.Enqueue("fix outage", 0);
jobs.Enqueue("review PR", 2);
jobs.Enqueue("reply to support", 1);
Console.WriteLine($"{jobs.Count} jobs, next: {jobs.Peek()}");

while (jobs.TryDequeue(out string? job, out int priority))
{
    Console.WriteLine($"[{priority}] {job}");
}

// Max-heap: reverse the priority comparer
var maxFirst = new PriorityQueue<string, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
maxFirst.EnqueueRange(new[] { ("low", 1), ("high", 9), ("mid", 5) });
Console.WriteLine(maxFirst.Dequeue());

Outputcompiled & run with real C#

4 jobs, next: fix outage
[0] fix outage
[1] reply to support
[2] review PR
[3] send newsletter
high

Your turn

Find the 3 largest numbers in [7, 2, 9, 4, 11, 5, 8] with a min-heap of size 3: enqueue each number, and when Count > 3, dequeue. That is O(n log k) instead of sorting everything.

Graphs: BFS, DFS and shortest paths

A graph is nodes plus edges. The usual C# representation is an adjacency list: Dictionary<TNode, List<TNode>>. Breadth-first search explores level by level with a Queue<T>, so the first time it reaches a node is along the fewest edges. Depth-first search goes as deep as possible first, with recursion or a Stack<T>. Both are O(V + E), and both need a HashSet of visited nodes or a cycle loops forever.

C#Program.cs

var graph = new Dictionary<string, List<string>>
{
    ["A"] = ["B", "C"],
    ["B"] = ["A", "D"],
    ["C"] = ["A", "D"],
    ["D"] = ["B", "C", "E"],
    ["E"] = ["D"],
};
Console.WriteLine("BFS: " + string.Join(" ", Bfs(graph, "A")));
Console.WriteLine("DFS: " + string.Join(" ", Dfs(graph, "A")));

static List<string> Bfs(Dictionary<string, List<string>> g, string start)
{
    var order = new List<string>();
    var seen = new HashSet<string> { start };
    var queue = new Queue<string>();
    queue.Enqueue(start);
    while (queue.Count > 0)
    {
        string node = queue.Dequeue();
        order.Add(node);
        foreach (string next in g[node])
        {
            if (seen.Add(next)) queue.Enqueue(next); // Add returns false if already seen
        }
    }
    return order;
}

static List<string> Dfs(Dictionary<string, List<string>> g, string start)
{
    var order = new List<string>();
    var seen = new HashSet<string>();
    Visit(start);
    return order;

    void Visit(string node)
    {
        if (!seen.Add(node)) return;
        order.Add(node);
        foreach (string next in g[node]) Visit(next);
    }
}

Outputcompiled & run with real C#

BFS: A B C D E
DFS: A B D C E

Your turn

Change BFS to also record each node's parent in a Dictionary<string, string>, then walk the parents back from "E" to print the shortest path A -> B -> D -> E.

VisualizeBFS from A, queue by queueStep 1 / 7

1var seen = new HashSet<string> { "A" };
2var queue = new Queue<string>();
3queue.Enqueue("A");
4while (queue.Count > 0)
5{
6    string node = queue.Dequeue();
7    foreach (string next in g[node])
8        if (seen.Add(next)) queue.Enqueue(next);
9}

Line 3

Start: A is seen and waiting.

Variables now

`queue`	`[A]`
`seen`	`{A}`

All 7 steps as a table

Step	Line	What happened	Variables now
1	3	Start: A is seen and waiting.	`queue = [A]` `seen = {A}`
2	6	Visit A.	`node = A` `queue = []`
3	8	A's neighbours B and C are new: both join the back of the queue.	`queue = [B, C]` `seen = {A, B, C}`
4	6	Visit B. Its neighbour A is already seen; D is new.	`node = B` `queue = [C, D]`
5	6	Visit C. A and D are both seen, nothing added.	`node = C` `queue = [D]`
6	6	Visit D. E is new.	`node = D` `queue = [E]`
7	6	Visit E. The queue is empty and the loop ends: A B C D E, level by level.	`node = E` `queue = []`

When edges have weights (kilometres, milliseconds, cost), BFS is no longer enough. Dijkstra's algorithm always expands the cheapest known node next — exactly what a PriorityQueue gives you. Because PriorityQueue cannot lower a priority in place, we enqueue again and skip stale entries.

C#Program.cs

var roads = new Dictionary<string, List<(string To, int Km)>>
{
    ["Home"] = [("Cafe", 4), ("Park", 1)],
    ["Park"] = [("Cafe", 2), ("Office", 7)],
    ["Cafe"] = [("Office", 3)],
    ["Office"] = [],
};
var dist = Dijkstra(roads, "Home");
foreach (string place in new[] { "Home", "Park", "Cafe", "Office" })
{
    Console.WriteLine($"{place}: {dist[place]} km");
}

static Dictionary<string, int> Dijkstra(Dictionary<string, List<(string To, int Km)>> g, string start)
{
    var dist = new Dictionary<string, int> { [start] = 0 };
    var pq = new PriorityQueue<string, int>();
    pq.Enqueue(start, 0);
    while (pq.TryDequeue(out string? node, out int d))
    {
        if (d > dist[node]) continue; // stale entry: a shorter path was found later
        foreach (var (to, km) in g[node])
        {
            int candidate = d + km;
            if (candidate < dist.GetValueOrDefault(to, int.MaxValue))
            {
                dist[to] = candidate;
                pq.Enqueue(to, candidate);
            }
        }
    }
    return dist;
}

Outputcompiled & run with real C#

Home: 0 km
Park: 1 km
Cafe: 3 km
Office: 6 km

Home to Cafe directly is 4 km, but via the Park it is 1 + 2 = 3. Dijkstra finds it because it settles the cheapest node first.

Binary search: by hand and built in

Binary search finds a value in sorted data by repeatedly halving the range: O(log n). Two details matter. Compute the midpoint as lo + (hi - lo) / 2, not (lo + hi) / 2, because lo + hi can overflow int on large arrays. And be exact about the loop condition: lo <= hi with hi = mid - 1 belong together.

C#Program.cs

int[] sorted = [3, 8, 15, 23, 42, 57, 91];
Console.WriteLine(BinarySearch(sorted, 42));
Console.WriteLine(BinarySearch(sorted, 5));

static int BinarySearch(int[] a, int target)
{
    int lo = 0, hi = a.Length - 1;
    while (lo <= hi)
    {
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Outputcompiled & run with real C#

4
-1

VisualizeSearching for 42 in [3, 8, 15, 23, 42, 57, 91]Step 1 / 7

1int lo = 0, hi = a.Length - 1;
2while (lo <= hi)
3{
4    int mid = lo + (hi - lo) / 2;
5    if (a[mid] == target) return mid;
6    if (a[mid] < target) lo = mid + 1;
7    else hi = mid - 1;
8}
9return -1;

Line 1

The whole array is in range.

Variables now

`lo`	`0`
`hi`	`6`

All 7 steps as a table

Step	Line	What happened	Variables now
1	1	The whole array is in range.	`lo = 0` `hi = 6`
2	4	mid = 3, a[3] = 23.	`mid = 3`
3	6	23 < 42, so 42 must be to the right. Discard the left half.	`lo = 4` `hi = 6`
4	4	mid = 4 + (6 - 4) / 2 = 5, a[5] = 57.	`mid = 5`
5	7	57 > 42: discard the right half.	`lo = 4` `hi = 4`
6	4	mid = 4, a[4] = 42.	`mid = 4`
7	5	Found in 3 comparisons instead of 5. Return 4.

Array.BinarySearch and List<T>.BinarySearch do the same job with one clever twist: when the value is missing they return the bitwise complement of where it would go. ~result gives the insertion index, which keeps a list sorted as you add to it.

C#Program.cs

int[] sorted = [3, 8, 15, 23, 42, 57, 91];
Console.WriteLine(Array.BinarySearch(sorted, 42));

int miss = Array.BinarySearch(sorted, 20);
Console.WriteLine(miss);
Console.WriteLine($"20 would go at index {~miss}");

var names = new List<string> { "ada", "bob", "cy" };
int at = names.BinarySearch("bea");
names.Insert(~at, "bea");
Console.WriteLine(string.Join(", ", names));

Outputcompiled & run with real C#

4
-4
20 would go at index 3
ada, bea, bob, cy

Sorting: insertion, merge, and what .NET uses

Insertion sort grows a sorted prefix one element at a time: O(n²) in general, but very fast on small or nearly-sorted arrays (which is why real libraries switch to it for tiny ranges). Merge sort splits in half, sorts each half, and merges: O(n log n) always, and stable — equal items keep their original order.

C#Program.cs

int[] a = [5, 2, 4, 1];
for (int i = 1; i < a.Length; i++)
{
    int key = a[i];
    int j = i - 1;
    while (j >= 0 && a[j] > key)
    {
        a[j + 1] = a[j]; // shift the bigger item right
        j--;
    }
    a[j + 1] = key;
}
Console.WriteLine(string.Join(" ", a));

Outputcompiled & run with real C#

1 2 4 5

VisualizeInsertion sort on [5, 2, 4, 1]Step 1 / 7

1for (int i = 1; i < a.Length; i++)
2{
3    int key = a[i];
4    int j = i - 1;
5    while (j >= 0 && a[j] > key)
6    {
7        a[j + 1] = a[j];
8        j--;
9    }
10    a[j + 1] = key;
11}

Line 3

i = 1: pick up 2.

Variables now

`key`	`2`
`a`	`[5, 2, 4, 1]`

All 7 steps as a table

Step	Line	What happened	Variables now
1	3	i = 1: pick up 2.	`key = 2` `a = [5, 2, 4, 1]`
2	7	5 > 2, so 5 slides right.	`a = [5, 5, 4, 1]`
3	10	Drop 2 into the gap at index 0.	`a = [2, 5, 4, 1]`
4	3	i = 2: pick up 4. Only 5 is bigger.	`key = 4`
5	10	5 slides right, 4 lands at index 1.	`a = [2, 4, 5, 1]`
6	3	i = 3: pick up 1. Everything before it is bigger.	`key = 1`
7	10	5, 4 and 2 each slide right, and 1 lands at index 0.	`a = [1, 2, 4, 5]`

C#Program.cs

int[] data = [38, 27, 43, 3, 9, 82, 10];
Console.WriteLine(string.Join(" ", MergeSort(data)));

static int[] MergeSort(int[] a)
{
    if (a.Length <= 1) return a;
    int mid = a.Length / 2;
    int[] left = MergeSort(a[..mid]);   // range slices copy into new arrays
    int[] right = MergeSort(a[mid..]);

    var merged = new int[a.Length];
    int i = 0, j = 0, k = 0;
    while (i < left.Length && j < right.Length)
        merged[k++] = left[i] <= right[j] ? left[i++] : right[j++]; // <= keeps it stable
    while (i < left.Length) merged[k++] = left[i++];
    while (j < right.Length) merged[k++] = right[j++];
    return merged;
}

Outputcompiled & run with real C#

3 9 10 27 38 43 82

In production you call the library. Array.Sort and List<T>.Sort use introsort (quicksort that falls back to heapsort and insertion sort): O(n log n), in place, but unstable. LINQ's OrderBy is stable and returns a new sequence, and ThenBy adds tie-breakers. Pick OrderBy when the order of equal items matters.

C#Program.cs

var people = new List<(string Name, int Age)>
{
    ("Ada", 36), ("Bob", 25), ("Cy", 36), ("Dee", 25),
};

var byAge = people.OrderBy(p => p.Age); // stable: ties keep input order
Console.WriteLine(string.Join(", ", byAge.Select(p => p.Name)));

var oldestFirst = people.OrderByDescending(p => p.Age).ThenBy(p => p.Name);
Console.WriteLine(string.Join(", ", oldestFirst.Select(p => p.Name)));

// In-place sort with a Comparison<T>: shortest name first, then alphabetical
people.Sort((x, y) => x.Name.Length != y.Name.Length
    ? x.Name.Length.CompareTo(y.Name.Length)
    : string.CompareOrdinal(x.Name, y.Name));
Console.WriteLine(string.Join(", ", people.Select(p => p.Name)));

int[] nums = [5, 1, 4];
Array.Sort(nums);
Array.Reverse(nums);
Console.WriteLine(string.Join(" ", nums));

Outputcompiled & run with real C#

Bob, Dee, Ada, Cy
Ada, Cy, Bob, Dee
Cy, Ada, Bob, Dee
5 4 1

Dynamic programming: memoise, then tabulate

Dynamic programming applies when a problem breaks into overlapping sub-problems: the naive recursion solves the same sub-problem again and again. Memoisation (top-down) caches each answer in a Dictionary the first time it is computed. Tabulation (bottom-up) fills an array from the smallest case upward with a plain loop — no recursion, so no stack overflow.

C#Program.cs

int calls = 0;
long Naive(int n)
{
    calls++;
    return n < 2 ? n : Naive(n - 1) + Naive(n - 2);
}
Console.WriteLine($"naive fib(30) = {Naive(30)} after {calls} calls");

var memo = new Dictionary<int, long>();
calls = 0;
long Memo(int n)
{
    calls++;
    if (n < 2) return n;
    if (memo.TryGetValue(n, out long cached)) return cached;
    return memo[n] = Memo(n - 1) + Memo(n - 2);
}
Console.WriteLine($"memo  fib(30) = {Memo(30)} after {calls} calls");

Outputcompiled & run with real C#

naive fib(30) = 832040 after 2692537 calls
memo  fib(30) = 832040 after 59 calls

Same answer, 45,000 times less work. O(2ⁿ) became O(n).

Tabulation on two coin problems. best[a] holds the fewest coins that make amount a; ways[a] counts combinations. Each entry is built only from entries already filled in.

C#Program.cs

Console.WriteLine(MinCoins([1, 5, 10, 25], 63));
Console.WriteLine(MinCoins([2], 3));
Console.WriteLine(CountWays([1, 2, 5], 5));

static int MinCoins(int[] coins, int amount)
{
    var best = new int[amount + 1];
    Array.Fill(best, int.MaxValue);
    best[0] = 0;
    for (int a = 1; a <= amount; a++)
        foreach (int c in coins)
            if (c <= a && best[a - c] != int.MaxValue)
                best[a] = Math.Min(best[a], best[a - c] + 1);
    return best[amount] == int.MaxValue ? -1 : best[amount];
}

static long CountWays(int[] coins, int amount)
{
    var ways = new long[amount + 1];
    ways[0] = 1;
    foreach (int c in coins)          // coins outer: counts combinations, not orderings
        for (int a = c; a <= amount; a++)
            ways[a] += ways[a - c];
    return ways[amount];
}

Outputcompiled & run with real C#

6
-1
4

Your turn

Swap the two loops in CountWays (amount outer, coins inner) and run it again. The answer becomes 9, because now 1+2+2 and 2+1+2 count as different ways.

Cheat sheet: which structure for which job

When you need to…	Use	Cost
Store items and read by position	`List<T>` / `T[]`	O(1) index
Look something up by key	`Dictionary<K,V>`	O(1) avg
Ask "have I seen this?" or remove duplicates	`HashSet<T>`	O(1) avg
Undo, bracket matching, DFS	`Stack<T>`	O(1) push/pop
Process in arrival order, BFS	`Queue<T>`	O(1) enqueue/dequeue
Add/remove at both ends, LRU cache	`LinkedList<T>`	O(1) at a node
Keep items sorted with range queries	`SortedSet<T>` / `SortedDictionary<K,V>`	O(log n)
Always take the smallest (or most urgent) next, top-k, Dijkstra	`PriorityQueue<TElement,TPriority>`	O(log n)
Find in sorted data	`Array.BinarySearch` / `List<T>.BinarySearch`	O(log n)
Sort, order of ties irrelevant	`Array.Sort` / `List<T>.Sort`	O(n log n), unstable
Sort, keep ties in order	`OrderBy` / `ThenBy`	O(n log n), stable
Many threads writing a map	`ConcurrentDictionary<K,V>`	O(1) avg, thread-safe

Big-O: How an algorithm's work grows as the input grows, ignoring constant factors.
Amortised O(1): Usually O(1), occasionally O(n) (a resize), averaging O(1) per operation — List.Add.
Hash table: Array of buckets indexed by a key's hash code; the structure behind Dictionary and HashSet.
Ring buffer: An array used as a queue with head and tail indexes that wrap around; how Queue gets O(1) dequeue.
Red-black tree: A self-balancing binary search tree; SortedSet and SortedDictionary are built on one.
Min-heap: A tree in an array where each parent is smaller than its children; the smallest item is always at the root.
BFS / DFS: Breadth-first (level by level, a queue) and depth-first (deep first, a stack or recursion) graph traversal.
Stable sort: A sort that keeps equal items in their original order. OrderBy is stable; Array.Sort is not.
Memoisation: Caching a function's result for each input so repeated calls cost O(1).
Tabulation: Bottom-up dynamic programming: fill a table from the smallest sub-problem up with a loop.

Quick check

You need to process support tickets so the most urgent one is always handled next, with new tickets arriving all the time. Which .NET type fits best?

Quick check

Array.BinarySearch(sorted, 20) returns -4. What does that mean?

A negative result is the bitwise complement of the insertion point. ~(-4) is 3, so inserting 20 at index 3 keeps the array sorted.

← Module 12C# + Tools Module 14 →Problem Solving

Frequently asked questions

Do I need to implement data structures by hand in C# at work?

Rarely. System.Collections.Generic covers almost every need, and it is faster and better tested than hand-written code. Building them once by hand is how you learn their costs, and interviewers still ask you to, so both halves of this module matter.

Is PriorityQueue in .NET a max-heap or a min-heap?

A min-heap: the lowest priority value is dequeued first. For a max-heap, pass a reversed comparer such as Comparer.Create((a, b) => b.CompareTo(a)), or negate numeric priorities.

Is Array.Sort stable in C#?

No. Array.Sort and List.Sort use introsort, which does not preserve the order of equal elements. LINQ OrderBy and ThenBy are stable, so use them when ties must keep their original order.

Finish the C# handbook, then get hired

Sit the exam for your certificate, run your resume through the ATS checker, and see the jobs that ask for exactly this.

Check my resume

Found this course useful? Share it.

ShareX LinkedIn

Comments

Join the conversation. Sign in to leave a comment — we'd love to hear your thoughts.