Why Algorithms and Data Structures Still Matter: A Roadmap for .NET Developers

Version note: The code in this post was built with .NET 10 and C# 14 and verified with xUnit v3 4.0.2 tests; measurements were taken with BenchmarkDotNet 0.15.8.

Guess First

The Bookstore catalog holds 100,000 books, and the checkout screen asks "which book is this ISBN (International Standard Book Number)?" 100 times per basket. We answer the same question with three structures: keep the books in a List<Book> and scan from the start, run binary search on an array sorted by ISBN, and use a Dictionary<string, Book> keyed by ISBN.

With 1,000 books, roughly how many times faster is the Dictionary than the List? When the catalog grows 100 times to 100,000 books, what happens to that gap: does it stay the same, grow 100 times, or something else? Where does the sorted array land between the two? The measurement in the middle of the post has the answer; write your guess down.

Abstract Data Type versus Implementation

Every post in this series rests on one distinction. An abstract data type (ADT) states what a structure promises: "give me an ISBN and I return the book", "give me back the last thing you added", "give me the smallest". The implementation decides how that promise is kept in memory and what each operation costs. One ADT has several implementations, and they differ in more than speed: memory use, ordering guarantees and which operations are cheap or expensive all change.

The most familiar .NET example is IList<T>. The interface promises reading and writing by index, inserting in the middle and removing. List<T> keeps that promise with an array underneath: access by index is a single address calculation, but inserting in the middle shifts every element to its right. LinkedList<T> does not implement IList<T> at all. It implements only ICollection<T> and the read-side interfaces; the BCL (Base Class Library) designers deliberately refused to give that contract to a structure where indexing would be O(n), so that code reading the interface and assuming "indexing is cheap" is not misled.

The ADT in the Bookstore scenario is this small:

namespace Bookstore;

public sealed record Book(string Isbn, string Title, decimal Price);

// ADT: what the catalog promises, not how it stores books
public interface IBookCatalog
{
    Book? FindByIsbn(string isbn);
}

The rest of the code knows this interface, not the structure behind it. That is the precondition for being able to change the structure later: fixing a wrong choice becomes a matter of swapping a single class behind the interface.

Three Implementations of One Contract

The first implementation is the plainest: walk every book and return the one whose ISBN matches.

public sealed class ListCatalog(IEnumerable<Book> books) : IBookCatalog
{
    private readonly List<Book> _books = [.. books];

    public Book? FindByIsbn(string isbn)
    {
        foreach (Book book in _books)
        {
            if (book.Isbn == isbn)
                return book;
        }
        return null;
    }
}

The second sorts the books by ISBN once and then halves the range on every lookup. The sorting cost is paid once in the constructor; each lookup makes at most log₂(n) comparisons.

public sealed class SortedArrayCatalog : IBookCatalog
{
    private readonly Book[] _books;

    public SortedArrayCatalog(IEnumerable<Book> books)
    {
        _books = [.. books];
        Array.Sort(_books, (a, b) => string.CompareOrdinal(a.Isbn, b.Isbn));
    }

    public Book? FindByIsbn(string isbn)
    {
        int lo = 0, hi = _books.Length;
        while (lo < hi)
        {
            int mid = lo + (hi - lo) / 2;
            int cmp = string.CompareOrdinal(_books[mid].Isbn, isbn);
            if (cmp == 0) return _books[mid];
            if (cmp < 0) lo = mid + 1;
            else hi = mid;
        }
        return null;
    }
}

The third computes a hash code from the ISBN and goes straight to the matching bucket:

public sealed class DictionaryCatalog(IEnumerable<Book> books) : IBookCatalog
{
    private readonly Dictionary<string, Book> _byIsbn = books.ToDictionary(b => b.Isbn, StringComparer.Ordinal);

    public Book? FindByIsbn(string isbn) => _byIsbn.GetValueOrDefault(isbn);
}

In one line each: lookup is O(n) in the List, O(log n) in the sorted array and O(1) on average in the Dictionary. What the notation means, why we say "on average" and why constants are dropped is covered in the "What Is Big-O Notation" post of the Big-O and Complexity series; here we only look at the outcome.

Test First: Do All Three Give the Same Answer?

Before measuring speed, pin down correctness. A fast structure that returns wrong answers is worthless. The routine for every structure in the series is the same: first an xUnit test, then the implementation, finally the measurement. This post's test builds the three catalogs from the same 1,000 books and checks that each ISBN returns the very same Book instance:

public class BookCatalogTests
{
    private static readonly Book[] Books = SampleBooks.Create(1_000);

    public static TheoryData<string> CatalogNames => ["list", "sorted", "dictionary"];

    private static IBookCatalog Create(string name) => name switch
    {
        "list" => new ListCatalog(Books),
        "sorted" => new SortedArrayCatalog(Books),
        _ => new DictionaryCatalog(Books),
    };

    [Theory]
    [MemberData(nameof(CatalogNames))]
    public void FindByIsbn_ExistingIsbn_ReturnsSameBook(string name)
    {
        IBookCatalog catalog = Create(name);

        foreach (Book book in Books)
            Assert.Same(book, catalog.FindByIsbn(book.Isbn));
    }

    [Theory]
    [MemberData(nameof(CatalogNames))]
    public void FindByIsbn_MissingIsbn_ReturnsNull(string name)
    {
        IBookCatalog catalog = Create(name);

        Assert.Null(catalog.FindByIsbn("9780000000000x"));
    }
}

$ dotnet test --project tests/Algorithms.Tests -- --filter-class Algorithms.Tests.BookCatalogTests
Running tests from tests/Algorithms.Tests/bin/Debug/net10.0/Algorithms.Tests.dll (net10.0|arm64)
tests/Algorithms.Tests/bin/Debug/net10.0/Algorithms.Tests.dll (net10.0|arm64) passed (658ms)

Test run summary: Passed!
  total: 6
  failed: 0
  succeeded: 6
  skipped: 0
  duration: 782ms

SampleBooks.Create uses a Random with a fixed seed to produce distinct 13-digit ISBNs starting with 978; every run gets the same data, so tests and measurements are repeatable. The --filter-class argument belongs to xUnit v3's runner on Microsoft Testing Platform (MTP); with the .NET 10 SDK (Software Development Kit) the xUnit v3 4.x packages run on MTP, and the solution's global.json has a "test": { "runner": "Microsoft.Testing.Platform" } line for that.

Measuring: a Catalog That Grows 100 Times

Timing a single loop with a Stopwatch cannot separate JIT (Just-In-Time) compilation, warm-up and noise. Every measurement in this series uses BenchmarkDotNet; its setup and how to read the results are in the C# Advanced series post "Performance in C#: Allocations, Structs and Measuring with BenchmarkDotNet". For each N the benchmark builds the three catalogs and looks up 100 existing ISBNs picked at random:

[MemoryDiagnoser]
public class CatalogBenchmarks
{
    private IBookCatalog _list = null!, _sorted = null!, _dictionary = null!;
    private string[] _lookups = null!;

    [Params(1_000, 100_000)]
    public int N;

    [GlobalSetup]
    public void Setup()
    {
        Book[] books = SampleBooks.Create(N);
        _list = new ListCatalog(books);
        _sorted = new SortedArrayCatalog(books);
        _dictionary = new DictionaryCatalog(books);
        Random random = new(7);
        // 100 lookups of existing ISBNs, picked at random
        _lookups = [.. Enumerable.Range(0, 100).Select(_ => books[random.Next(N)].Isbn)];
    }

    [Benchmark(Baseline = true)]
    public int List() => Run(_list);

    [Benchmark]
    public int SortedArray() => Run(_sorted);

    [Benchmark]
    public int Dictionary() => Run(_dictionary);

    private int Run(IBookCatalog catalog)
    {
        int found = 0;
        foreach (string isbn in _lookups)
            if (catalog.FindByIsbn(isbn) is not null) found++;
        return found;
    }
}

BenchmarkDotNet v0.15.8, macOS 27.0.1 (26A434) [Darwin 27.0.0]
Apple M5, 1 CPU, 10 logical and 10 physical cores
.NET SDK 10.0.402
  [Host] : .NET 10.0.13 (10.0.13, 10.0.1326.50504), Arm64 RyuJIT armv8.0-a

| Method      | N      | Mean           | Median         | Ratio | Allocated |
|------------ |------- |---------------:|---------------:|------:|----------:|
| List        | 1000   |    79,000.6 ns |    76,585.9 ns |  1.01 |         - |
| SortedArray | 1000   |     2,055.1 ns |     2,018.0 ns |  0.03 |         - |
| Dictionary  | 1000   |       882.7 ns |       882.9 ns |  0.01 |         - |
|             |        |                |                |       |           |
| List        | 100000 | 9,693,796.6 ns | 9,634,433.9 ns | 1.004 |         - |
| SortedArray | 100000 |     6,548.1 ns |     4,696.6 ns | 0.001 |         - |
| Dictionary  | 100000 |       930.2 ns |       913.9 ns | 0.000 |         - |

Back to your guess. With 1,000 books the List finishes 100 lookups in 79 µs and the Dictionary in 0.88 µs: about 90 times. With 100,000 books the List climbs to 9.7 ms while the Dictionary stays at 0.93 µs: the gap passes 10,000 times. The catalog grew 100 times, and the List's time grew about 120 times; the Dictionary's time barely moved. The sorted array behaves differently from both: its time went from 2 µs to 4.7–6.5 µs. Comparisons per lookup rose from log₂(1,000) ≈ 10 to log₂(100,000) ≈ 17, and on top of that a 100,000-element array no longer fits in the processor's cache.

Two more things in this table. First, the gap between the sorted array's mean at 100,000 (6.5 µs) and its median (4.7 µs) is noise: the measurement ran while other work was running on the machine. Look at ratios and the direction of growth, not absolute numbers. Second, the "Allocated" column is empty for all three: none of them allocates on the heap during a lookup. The cost comes entirely from walking memory and comparing.

Why Write Your Own When the BCL Has It?

In production code you would write none of these three catalogs yourself. Dictionary, Array.BinarySearch and List<T> already exist, have been tested for years and are most likely faster than the version you would write. This series still writes every structure from scratch, for three reasons.

The first is seeing the cost. Once you have written it with your own hands, you do not forget why List<T>.Insert(0, x) is slow, why a key with a bad GetHashCode brings a Dictionary to its knees, or why Array.Sort does not keep equal elements in order. That knowledge lets you ask in a code review, "what does this Contains inside a loop do with 50,000 records?"

The second is needs the BCL does not cover. A ring buffer that keeps the last N log lines and overwrites the oldest when full, a trie for autocomplete, union-find for grouping duplicate customer accounts, topological sort for dependency order: none of them ships ready-made. You will build them by combining pieces from these posts.

The third is interviews. The series does not aim at them but delivers them as a by-product: once you learn patterns such as two pointers, sliding window, BFS (Breadth-First Search) and dynamic programming through real Bookstore problems, the question at the whiteboard looks familiar too.

How the Series Works

All the code lives in one solution. The solution file uses the XML (Extensible Markup Language) based .slnx format; with the .NET 10 SDK dotnet new sln produces this format by default:

Algorithms.slnx
# sdk 10.0.402 and Microsoft.Testing.Platform as the test runner
global.json
# net10.0, C# 14, Nullable and ImplicitUsings on
Directory.Build.props
# our own structures: Linear, Hashing, Sorting, Trees, Graphs...
src/Algorithms/
# BenchmarkDotNet 0.15.8
src/Algorithms.Benchmarks/
# xUnit v3 4.0.2
tests/Algorithms.Tests/

The order is the same in every post. First we write the structure's contract as a test, usually one that compares against the BCL counterpart, because Dictionary or SortedSet is the most reliable reference we have. Tests that generate random operations and check at every step that both structures give the same answer will show up often. Then the implementation, then the measurement. Benchmarks run one at a time with dotnet run -c Release --project src/Algorithms.Benchmarks -- --filter '*Catalog*'.

The Series Map

The series has 22 posts in six blocks. Each block builds on the previous one; reading them in order is recommended.

• Linear structures (02–05): arrays and dynamic arrays, linked lists, stacks, queues and ring buffers, recursion and the call stack.
• Hashing (06–07): writing a hash table from scratch, then array patterns such as two pointers, sliding window and prefix sum.
• Sorting and searching (08–10): insertion and merge sort, quick sort and .NET's introsort, every variant of binary search.
• Trees, heaps and tries (11–14): binary search trees, balanced trees and the B-tree, heaps and priority queues, tries.
• Graphs (15–18): BFS and DFS (Depth-First Search), topological sort, Dijkstra, union-find and minimum spanning trees.
• Paradigms (19–22): backtracking, greedy algorithms and two posts on dynamic programming.

The series leans on two published series. The API (Application Programming Interface) of .NET's collections was covered in the C# Collections series; here the API is not repeated, we look only at the internals and compare them with our own version. The complexity map in that series' "Immutable Collections in C# and Choosing the Right Collection" post reads like a summary of this series; it is worth keeping open alongside. Complexity analysis itself, meaning what O, Ω and Θ mean, deriving complexity from code and amortized analysis, is in the Big-O and Complexity series. This series gives each structure's complexity in one line and points there.

In Production

Think of n in terms of the data two years from now, not today's. On launch day, a List lookup in an 800-book catalog draws nobody's attention; the table says 79 µs. The same code with 100,000 books and 100 lookups per basket reaches 9.7 ms, paid on every request. On an endpoint serving 200 requests per second that is almost two full CPU (Central Processing Unit) cores spent on lookups alone. The code did not change; the data grew.

Every structure has a build and update cost. The sorted array is good at lookups, but adding a new book means shifting every element to its right to keep the order. If the catalog loads once a day, that is fine; if hundreds of price and stock updates arrive per minute, it is not. The Dictionary is fast at both lookups and inserts but keeps no ordering, so it cannot answer a query like "give me the books in this ISBN range". When choosing, look at the whole mix of operations, not only the most frequent one.

Memory is a cost too. The Dictionary also stores each key's hash code and chain information, so it keeps the same data in more memory than a sorted array. With a few million records that difference can decide a container's memory limit. Keep [MemoryDiagnoser] on when measuring, and measure the build cost separately.

Common Pitfalls

Deciding from small data. A 78 µs difference between List and Dictionary at 1,000 records means nothing to anyone; the same difference becomes 10,000 times at 100,000 records. Measure with the real production n, or larger.

Not seeing the cost behind an interface. Calling books.Contains(x) in a method that takes IEnumerable<Book> is cheap if a HashSet is behind it and expensive if a List or a lazy LINQ (Language Integrated Query) query is. The code looks the same; the cost depends entirely on the implementation.

One-shot Stopwatch measurements. The first call includes JIT compilation, later calls benefit from caches, and a single measurement mixes both. A performance claim should come with BenchmarkDotNet output.

Trying to write everything yourself. This series writes the structures to learn them; in production the BCL's tested collections are the default choice. Write your own only when the BCL has no counterpart or a measurement shows it does not meet the need.

A Small Experiment

★☆☆ Add 10,000 and 1,000,000 to the [Params] of CatalogBenchmarks. Does the List's time grow in proportion to n? At what point does the sorted array's time rise noticeably?

★★☆ Replace half of the 100 looked-up ISBNs with ISBNs that are not in the catalog. Which implementation's time changes and which does not? Explain why by looking at each one's loop.

★★★ Add IReadOnlyList<Book> FindByIsbnPrefix(string prefix) to IBookCatalog. Which of the three implementations can do this efficiently and which cannot? Write a solution for the sorted array using the lower bound idea and add a test that compares it with the List version.

The next post starts with the most basic structure of the series: the array. We look at how int[] and object[] sit in memory, at index arithmetic and bounds checks, then write our own DynamicArray<T> and see exactly what happens when a List<T>'s capacity runs out.