Head First Algorithms and Data Structures

Appendix A. Leftovers: The Top Ten Topics (We didn’t cover)

We’ve covered a lot of ground, and you’re almost finished with this book. We’ll miss you—but before we let you go, we wouldn’t feel right about sending you out into the world without a little more preparation. We can’t possibly fit everything you’ll need to know into this relatively small chapter. Actually, we did originally include everything else you need to know about algorithms and data structures, by reducing the type point size to .00004. It all fit, but nobody could read it. So we threw most of it away and kept the best bits for this Top Ten appendix. This really is the end of the book. Except for the index, of course (a must-read!).

#1 Tries (prefix trees)

Ever wonder how your phone knows you’re typing “hello” after you type “hel”?

It’s not magic, and it’s not checking every word in the dictionary. It’s a trie: a tree where each path from root to leaf spells out a word.

Here’s how it works. Instead of storing whole words in nodes, you store one character per node. The word “cat” is three nodes deep: c to a to t. The word “car” shares the first two nodes, then branches: c to a to r. Every word with the same prefix shares the same path.

That’s the trick. Words that start the same way are stored together.

Why they’re fast

With a trie, looking up a word takes O(length of word), rather than O(number of words in ...