Data structures are a well-established part of the computer science (CS) curriculum. Courses and textbooks vary in emphasis. Often the introductory sequence for CS majors and others includes both programming and data structures so that students read and write code for lists, queues, and trees, for example. More advanced data structure courses may concentrate on theory. This 200-page text is entirely theoretical with no code at all. Brief pseudocode is included for tree search and insertion and deletion. The author teaches the corresponding course to students in the second semester of the first year who have had discrete mathematics and introduction to programming. Each chapter has several mostly theoretical exercises, with answers to about half of them provided.

The first three chapters give a different impression than the remainder of the text. The first chapter is an interesting motivating example using Boyer-Moore string search. Only at the end is there a one-sentence mention that the array is the data structure, and “array” does not appear in the index. The second chapter, “Linear Lists,” has nice examples on optimal prefix code and arithmetic expressions. The next chapter, “Graphs,” just mentions minimum spanning trees, shortest path, and maximum flow without giving algorithms or proofs; it ends with some good examples.

At this point, the text becomes more traditional, perhaps because the author has taught the data structures course over 30 times. The next chapters, “Trees,” “AVL Trees,” and “B-Trees,” clearly explain the details of insertion, deletion, and rebalancing. The advantages of trees and B-trees are only briefly mentioned. At the author’s institution, the course format is two hours of lecture and two hours of recitation, so that the discussion sessions may allow for more examples, more insight into the uses of the data structures, and help with the theoretical exercises. The book concludes with chapters on heaps, sets, hash tables, sorting, and codes.