This fine book about data structures and algorithm analysis is not basic. It is a textbook for an advanced undergraduate class in data structures or a beginning class in algorithm analysis that is conceptual and grounded in theory. It fulfills its purpose by being well written and current; it is written for an informed and intelligent student of computer science, and it includes the most significant new work in data structures and algorithm analysis.

The book has 11 chapters. The first two are introductory, providing a review of mathematics and a summary of algorithm analysis strategies. Chapters 3 through 9 are about lists, stacks, and queues; trees; hashing; heaps; sorting; disjoint sets; and graphs. The last two chapters discuss algorithm design techniques and amortized analysis.

The book is comprehensive but concise. Data structures are typically presented in the context of the abstract data type. “Relaxed” or “lazy” or self-adjusting data structures such as splay trees, skew heaps, and Fibonacci heaps are included. Weiss provides a good discussion of amortized analysis of algorithms. The book also discusses skip lists.

The level of abstraction is appropriate for upper-level undergraduates or beginning graduate students. The material is current. Few other texts include the self-adjusting data structures and amortized analysis of algorithms, and these topics may be among the most significant to date in the area of data structures and algorithm analysis. Skip lists may not yet be covered in any other textbook.

An extensive set of references at the end of each chapter is preceded by a narrative that gives a historical context. The index is good. The exercises are excellent, and range in difficulty from straightforward to very difficult. Difficult and very difficult exercises are identified with one or two asterisks, respectively. This excellent textbook will challenge and inspire good computer science students.