Author: Jeremy Kubica
Publisher: No Starch
Pages: 304
ISBN: 978-1718502604
Print: 1718502605
Kindle: ‎ B09WJYH4KL
Audience: Developers interested in data structures
Rating: 4.5
Reviewer: Kay Ewbank

This book looks at what lies behind data structures and how this relates to solving complex problems with the aim of providing new insights into how to use the underlying structure of your data to be more efficient.

The author uses real-world analogies (most involving how to get a decent cup of coffee) to make the ideas more relatable and accessible.

The opening chapter begins with the basics of storing data in memory, from the simple data structures - variables, structs, arrays and strings.  Kubica then moves on to binary search as a way of illustrating how algorithms can make use of the way data is stored to work with it effectively.

Dynamic data structures are introduced next as the first of the really important ways to work with data. The chapter introduces pointers and references, linked lists and double linked lists. A chapter on stacks and queues then looks at the different ways they retrieve stored data and what the benefits of each are.

Chapter 5 expores binary search trees, along with algorithms for searching for values, adding new values and deleting values, and this is followed by a chapter on ways to extend binary search trees, including tries and adapting data structures. 

By Chapter 7, Kubica has moved on to more advanced topics, in this case priority queues and heaps and how these can be used to process urgent requests first. He then looks at multidimensional grids and targets in the shape of grids. There's a good description of nearest-neighbor search, and how this can be firstly used to find the nearest cup of coffee, and the concept is then widened to prune the search space to reject infeasible regions.

Having explored the limitations of grids, spatial trees and spatial partitioning are the next topic of interest, including uniform quad trees and k-d trees. Quad trees are explained well using the analogy of a kitchen drawer containing everything being difficult to search, then considering organized drawers and how this can go too far because you have to look in multiple drawers, and finally arriving at the idea of the quadtree combining a branching structure of grids.

By Chapter 10 Kubica has moved on to hash trees and how they use mathematical functions to point to data's locations. As with the rest of the book, the use of coffee related examples is used to good effect to make the ideas understandable - mapping the name of a blend of coffee to the bin it's stored in. Caches are explored next. Modern web use has introduced most users to the idea of caches, but Kubica looks at how to work with caches effectively. A chapter on b-trees, self-balancing tree-based structures, comes next.

The final three chapters cover Bloom filters as a technique for extending hash tables to optimize the amount of memory needed; skip lists to make it possible to move more rapidly through elements in a list; and a brief exploration of graphs.

This is an interesting book. Data structures can be a dry topic, and Kubica does his best to keep the information accessible and entertaining. He doesn't always succeed, but if you work through the topics, you'll have a good grasp of how to set up and use the right data structures,

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.