The data structures course has evolved so much over the last 15 years that those of us who taught it back then would be hard pressed to recognize it. It has followed the trend of moving more abstract material to lower-level courses without removing old material. The question raised is similar to the one raised by “new math” years ago--theory or methodology? We appear to want both. We have also come to realize that most students want to obtain employment, which requires that we prepare them for real-life programming environments. Thus, this course is becoming more and more difficult to teach and, of course, to learn. This textbook attempts to meet all of these competing concerns.

Dale is a proven author whose textbooks have frequently become the standard to which others are compared. Here she has produced another excellent textbook. It is readable; is laid out in a standard, reasonable order, which does not require the instructor to skip around; and has good exercises. All textbooks on the subject, including this one, probably contain more material than can be taught effectively in a course on data structures. Nonetheless, this appears to be a textbook for a single course, rather than a large collection of topics that can be used for several courses. I like the end-of-chapter exercises. There are many of them, of varying levels of difficulty. At the end of the book, Dale gives answers to some of the exercises and sample programming projects, again of varying degrees of difficulty. Programming exercises serve several different needs. One is to make sure that students can code the algorithms associated with the data structures. The second is to be sure that they can apply the data structures to solving problems; this involves recognizing what data structure is called for and then actually writing the code to solve the problem. The third is to be sure the students can solve problems that require the use of several data structures.

The textbook begins with a chapter on all phases of software engineering, which is followed by a chapter on abstraction and the C++ class structure. These two chapters may be review, in which case they should be covered quickly. If this material is new, the presentation is good but possibly too brief. However important this material is, the instructor should not spend too much time here at the expense of some of the core data structures later in the book.

Chapter 3 begins the material on abstract data types (ADTs) with lists, both unordered and ordered. The chapter also introduces algorithm analysis using the big-O notation. Chapter 4 introduces stacks, queues, and sets; pointers and dynamic data; and templates. The idea of pointers should be review material for many students, but templates will probably be new to all of them. Chapter 5 implements the material from chapters 3 and 4 using pointers. Chapter 6 is devoted to circular linked lists and doubly linked lists. More advanced C++ ideas are introduced using this material as a vehicle.

Chapter 7 is a good discussion of recursion, including how recursion works. It serves as a good introduction to the implementation of block structured languages. Dale also compares iteration and recursion and discusses when to use recursion.

Chapter 8 contains the standard introduction to trees, mainly using a binary search tree. It includes both iterative and recursive versions of the standard operation algorithms. Chapter 9 continues with other tree-like structures: expression trees, heaps, priority queues, and graphs. Chapter 10 is a fairly standard discussion of sorting and searching, with comparisons of algorithms.