1 Starting a fabulous adventure
This opening chapter sets the tone for a practical, curiosity-driven tour of data structures and algorithms, asking what makes some of them feel genuinely “fabulous.” The author highlights qualities such as tackling real problems beyond canned library solutions, embracing counterintuitive ideas like immutability for robust undo/redo, and recognizing patterns that transfer across domains (for example, backtracking unites tree search, map coloring, sudoku, and code formatting). The chapter also celebrates writing code that foregrounds meaning over mechanisms, delighting in “magic trick” data structures, exploiting language features to their fullest, reframing problems for dramatic speedups, connecting practice to theory, and, above all, having fun—while expanding a working toolbox and reshaping how we think about programming.
Core concepts are defined succinctly: a data structure organizes information; an algorithm is a finite procedure (not necessarily deterministic or computer-bound) that solves a problem. Complexity measures how cost grows with input size, typically expressed with big-O notation. The chapter sketches common classes—from constant and logarithmic through linear, quasilinear, quadratic, and on to exponential and factorial—along with guidance on choosing the right measure of “size” and the right notion of “cost” (time, memory, or other resources). It cautions that best-, average-, and worst-case behaviors all matter, and that an asymptotically superior algorithm is not automatically the best choice for typical, small, real-world inputs.
As a warmup, the chapter builds an immutable linked list and a simple linear-time reverse operation, then uses that tiny example to practice performance scrutiny. Design choices (such as how to represent the empty list and leveraging record types for immutability) trade convenience against pitfalls: equality semantics that trigger extra work, recursive comparisons that risk stack overflows, and a naive string concatenation that becomes accidentally quadratic. The exercise illustrates how even small, clear code can hide real costs. The road ahead promises classic structures with twists (persistence, memoization, elegant reordering, and even a quirky near-constant-time reversal), cross-domain algorithms from developer tools (backtracking, unification and anti-unification), and a hands-on toolkit for probability and inference. Though examples are in C#, the ideas generalize broadly, with the next chapter diving deeper into immutable lists.
A graph comparing the growth curves for logarithmic, linear, quasilinear, quadratic and exponential growth. Logarithmic is the shallowest curve, growing very slowly, and exponential is the fastest.
Summary
- There are lots of books about standard data structures such as lists, trees and hash tables, and the algorithms for sorting and searching them. And there are lots of implementations of them already in class libraries. In this book we’ll look at the less well-known, more off-the-beaten-path data structures and algorithms that I had to learn about during my career. I’ve chosen the topics I found the most fabulous: the ones that are counterintuitive, or seemingly magical, or that push boundaries of languages.
- I had to learn about almost all the topics in this book when I needed a new tool in my toolbox to solve a job-related problem. I hope this book saves you from having to read all the abstruse papers that I had to digest if you too have such a problem to solve.
- But more important to me is that all these fabulous adventures gave me a deeper appreciation for what computer programmers are capable of. They changed how I think about the craft of programming. And I had a lot of fun along the way! I hope you do too.
- Asymptotic complexity gives a measurement of how a solution scales to the size of the problem you’re throwing at it. We generally want algorithms to be better than quadratic if we want them to scale to large problems.
- Complexity analysis can be subtle. It’s important to remember that time is not the only resource users care about, and that they might also have opinions on whether avoiding a bad worst-case scenario is more or less important than achieving an excellent average performance.
- If problems are always small, then asymptotic complexity matters less.
- Reversing a linked list is straightforward if you have an immutable list! We’ll look at other kinds of immutable lists next.
FAQ
What does Chapter 1 cover?
Three things: why certain algorithms and data structures feel “fabulous,” clear definitions of data structures, algorithms, and complexity, and a warm-up exercise reversing an immutable linked list in C#.What makes an algorithm or data structure “fabulous” in this book’s sense?
- Solves real problems off the beaten path (e.g., learning anti-unification from research papers)- Yields counterintuitive wins (immutability helping undo/redo and reasoning)
- Applies across domains (backtracking for trees, map coloring, Sudoku, code formatting)
- Emphasizes meaning over mechanisms (code that reads in domain terms)
- Feels like a magic trick (e.g., Hughes list hiding data in a tree)
- Leverages language features deeply (e.g., recursive generics in C# finger trees)
- Reframes problems to change the game (e.g., HashLife via immutable quadtrees)
- Connects with theory (shared patterns across disparate types)
- Keeps programming fun
How does the chapter define data structures, algorithms, and complexity?
A data structure organizes information. An algorithm is a finite sequence of steps to solve a problem—possibly randomized and not necessarily run by a computer. Complexity relates problem size to the cost (time, memory, etc.) required to solve it.What are common time complexities and simple examples of each?
- O(1): First element of an array- O(log n): Minimum identifier length needed as unique items grow
- O(n): Sum n integers
- O(n log n): Sort n strings
- O(n²): Naive “concatenate n small strings” approach
- O(2ⁿ) / O(n!): Enumerate all subsets/orderings
How should I think about “size” and “cost” in complexity analysis?
State the size measure explicitly when non-obvious (e.g., tree height vs node count). Consider costs beyond time (memory, other resources). Distinguish best-, average-, and worst-case time; all may matter depending on workloads.Why isn’t the best asymptotic algorithm always the best choice?
Asymptotics dominate only at large scales. For common, small inputs a simpler algorithm with a worse worst case can be faster in practice, as with a naive string search used by Visual Basic because it excelled on typical short-string patterns.How is the immutable linked list defined, and why is the empty list a real object?
The list is either empty or a value plus a tail list, implemented as a sealed record with Value and Tail. The empty list is a valid singleton object so you can safely call methods on it, avoiding null-as-empty pitfalls in OO code.What performance pitfalls are highlighted in the initial list implementation?
- IsEmpty using record equality is costlier than checking Tail == null- Record-generated value equality is recursive (O(n) over shared prefixes) and can risk stack overflow on long lists
- ToString with repeated concatenation is accidentally quadratic; use a StringBuilder
- Node creation is O(1); building n nodes is O(n)
Fabulous Adventures in Data Structures and Algorithms ebook for free
