Data structures, which are used to represent data, are one side of the programming coin; algorithms are the other side. Just as a coin has two sides, and we cannot remove either one, programming has the two sides of data structures and algorithms, and we cannot ignore either one. The choice of representation of a program's data is as central to program design as is the choice of algorithm. Having said this, we focus, primarily on data structures and their performance, and secondarily on algorithms. We have to make wise choices of representations; therefore, we must have a basic knowledge of data representations and their properties. We aim to provide you with the strengths and weaknesses of data structures within the context of programming and algorithms, so that you can make wise choices.
The study of data structures is exciting and rewarding. The basic ideas are simple, yet many problems raised by these simple ideas are challenging and often unsolved. When we have to decide what should be taught in a data-structures course, the only agreement seems to be on the course title.
This text has been written for a junior- or senior-level course in data structures. Our goals are to introduce you to the world of data structures, to show you how to evaluate data structures, to help you obtain insight into data structures, and to give you the basis for making wise choices of data structures. We introduce the overarching framework of abstract data types (ADTs) in Chapter 1 and present the three approaches to performance evaluation (empirical, simulational, and analytical) in Chapter 2. We also discuss the three approaches to analytical evaluation, namely, worst case, expected case, and amortized case. Amortized analysis, which can be thought of as worst-case batch analysis, is a recently introduced and powerful tool for evaluating algorithms and data structures. In Chapters 3 and 4 we provide a medium-paced, detailed review of lists and maps. The core of the text is Chapters 5 through 14 in which we present the more advanced topics of trees, strings, sets, tables, dictionaries, partitions, sorting, and graphs. The pace is brisker and less detailed. Finally, in Chapter 15, we preview six advanced data structures (skip lists, quad trees, k-d trees, segment trees, range trees, and hierarchical trees) and two advanced data-structuring techniques (dynamization and persistence).
This text has a different emphasis to that of other currently available data-structure texts. Specifically, it
We use Pascal to provide detailed, example implementations of ADT operations and pseudo-Pascal when we give partial implementations. Each chapter terminates not only with a set of exercises, but also with a history section that provides references to the data-structuring literature. We use ``*'' to indicate a difficult section or exercise; the *-ed sections can be omitted on a first reading. An instructor's manual will be available for those instructors who adopt the text.
Derick Wood, January 14, 1993