Roadmap › 0. Fundamentals › Step 2
DSA
Data Structures & Algorithms — How They Work Inside
Big-O and how to measure algorithms, arrays and dynamic arrays, linked lists, stacks and queues, hash tables (how hashing and collisions work), trees, binary search trees, heaps, tries, graphs, searching, sorting algorithms step by step, recursion, two pointers and sliding window, greedy, dynamic programming and backtracking — with C# code and where .NET and SQL Server use each one.
What it is & where it is used
A data structure is a way to organise data in memory; an algorithm is a step-by-step procedure to solve a problem using it. The right choice is the difference between a page that loads in 50 ms and one that times out.
| Need | Data structure | .NET type | Used inside |
|---|---|---|---|
| Ordered list, index access | Dynamic array | List<T>, T[] | Almost everything |
| Fast lookup by key | Hash table | Dictionary<K,V>, HashSet<T> | Caches, EF Core change tracker, ASP.NET routing tables |
| Last-in-first-out | Stack | Stack<T> | Call stack, undo, expression parsing |
| First-in-first-out | Queue | Queue<T>, Channel<T> | Thread pool work queue, message queues |
| Sorted data, range queries | Balanced tree / B-tree | SortedDictionary (red-black tree), SortedSet | SQL Server indexes (B+ trees), file systems |
| Smallest/largest first | Heap | PriorityQueue<T,P> | Schedulers, Dijkstra, top-K |
| Prefix search | Trie | — (custom) | Autocomplete, routers |
| Relationships | Graph | adjacency lists | Social networks, maps, dependency resolution (DI containers, NuGet) |
Versions & history
| Year | Milestone |
|---|---|
| ~300 BC | Euclid's algorithm for greatest common divisor |
| 1945–1960s | Merge sort (von Neumann, 1945), binary search, hash tables (1953), quicksort (Hoare, 1959), Dijkstra's shortest path (1956/59), heapsort (1964) |
| 1970s | B-trees (Bayer & McCreight, 1970) — the basis of database indexes; red-black trees (1972/1978); Knuth's The Art of Computer Programming |
| 1990s–2000s | Skip lists, consistent hashing (distributed caches), MapReduce |
| 2002 | Timsort (Python; later Java) |
| 2010s | .NET's Array.Sort uses introsort (quicksort + heapsort + insertion sort) |
| 2021 | .NET 6 adds PriorityQueue<TElement, TPriority> |
Lifecycle
How to solve an algorithm problem (interview or real work):
- Understand — restate the problem, inputs, outputs, constraints (n up to 10⁵? sorted? duplicates? negative numbers?).
- Examples — work through a small case by hand, including edge cases (empty, one element, all same).
- Brute force — say the simplest solution and its complexity.
- Optimise — look for a better data structure (hash map, heap, sorting first) or pattern (two pointers, sliding window, BFS, DP).
- Code — clean, with meaningful names.
- Test — run your examples and edge cases through the code.
- Analyse — state time and space complexity; mention trade-offs.
Tools used to develop
- Practice: LeetCode, HackerRank, Codility (used by many companies' online tests), GeeksforGeeks, Exercism (C# track).
- Visualise: visualgo.net, Python Tutor (pythontutor.com supports several languages), USFCA data-structure visualisations.
- Measure: BenchmarkDotNet,
Stopwatch, Visual Studio profiler. - Reference: Introduction to Algorithms (CLRS), Grokking Algorithms, the Coding Round Practice course on DevLadder for C# solutions.