Data Abstraction In this text we view our data structures from three different perspectives:
their specification, their application, and their implementation. The specification describes the
logical or abstract level—what the logical relationships among the data elements are and what
operations can be performed on the structure. The application level, sometimes called the client
level, is concerned with how the data structure is used to solve a problem—why the operations
do what they do. The implementation level involves the coding details—how the structures
and operations are implemented. In other words we treat our data structures as abstract data
Efficiency Analysis In Chapter 1 we introduce order of growth efficiency analysis using a unique
approach involving the interaction of two students playing a game. Time and space analysis is
consistently applied throughout the text, allowing us to compare and contrast data structure
implementations and the applications that use them.
Recursion Treatment Recursion is introduced early (Chapter 3) and used throughout the re-
mainder of the text. We present a design and analysis approach to recursion based on answering
three simple questions. Answering the questions, which are based on formal inductive reasoning,
leads the programmer to a solid recursive design and program.
Interesting Applications Eight primary data structures (stacks, queues, collections, indexed
lists, trees, maps, priority queues, and graphs) are treated in separate chapters that include their
definition, several implementations, and one or more interesting applications based on their use.
Applications involve, for example, balanced expressions, postfix expressions, image generation
(new!), fractals (new!), queue simulation, card decks and games (new!), text analysis (new!), tree
and graph traversals, and big integers.
Robust Exercises We average more than 40 exercises per chapter. The exercises are organized by
chapter sections to make them easier for you to manage. They vary in level of difficulty, including
short and long programming problems (marked with “programming-required” icons—one icon
to indicate short exercises and two icons for projects), the analysis of algorithms, and problems
to test students’ understanding of abstract concepts. In this edition we have streamlined the
previous exercises, allowing us to add even more options for you to choose from. In particular
we have added several larger programming exercises to many of the chapters.
Input/Output Options It is difficult to know what background the students using a data struc-
tures text will have in Java I/O. To allow all the students using our text to concentrate on the