This handbook of data structures and algorithms is designed as a comprehensive resource for computer
science students and practitioners. The book is, quite literally, the product of a marriage
of theory and practice. As an alternative to the survey approach taken by traditional data structures
and algorithms textbooks, this book builds on a theoretical foundation to offer a top-down
application-centered approach and a systematic treatment of data structure design and their practical
implementation.
The book serves three major purposes: guidance, implementation, and insight. Charts, decision
trees, and text provide guidance through the large body of material presented. Unlike a textbook,
it is not necessary to read the entire book to fully benefit from its contents. Our intention is that
readers with a specific problem will follow the provided guidance and organizational tools to quickly
identify the most appropriate data structure or algorithm for their problem. For example, readers
seeking a data structure for an application are first guided to a suitable abstract data type (ADT),
and then to the most appropriate implementation of that ADT. Trade-offs between competing data
types and implementations motivate each decision in the context of the problem at hand.
Traditional textbooks generally gloss over the different possible variations of a given data structure
type. For example, a typical textbook has a chapter on “hashing” that treats all of the various
uses of hashing uniformly as one idea (for example, hash-based implementations of a set or mapping).
However, in reality, implementing them all in terms of a single ADT would lead to inefficiencies
for alternate uses. Consider an application that requires a mapping from each word in a
text document to the positions at which it occurs. One could use Java’s HashMap to associate each
word with a linked list of line numbers. However, each insertion to associate a new word with a line
number would require using get (to discover that the word is not yet in the mapping), and then put
(that duplicates most of the work performed by get). In this book, we explicitly include the BucketMapping
interface to provide efficient support for such an application. By explicitly introducing
separate interfaces and ADTs for important variations in usage, differences can be highlighted and
understood.
The book includes complete implementations for a wide variety of important data structures and
algorithms. Unlike most textbooks that sweep details under the rug to simplify the implementation
for “ease of explanation,” we have taken the approach of providing complete object-oriented implementations
within an extensible class hierarchy. Yet we have not done so at the expense of clarity.
Because of the completeness of implementation, chapters on some topics are longer than one might
see in a textbook covering a similar topic. However, the organization of the chapters simplifies
navigation, and the detailed implementations provide design insights useful to practitioners. Our
implementations follow standard Java programming conventions.