The study of data structures is part of the core of every collegiate computer science and computer engineering major program we are familiar with. Typically, in programs based upon semesters, elementary data structures are briefly introduced in the first programming or introduction to computer science course (CS1), and this is followed by a more in-depth data structures (CS2) course (possibly preceded by an intermediate programming and introduction to data structures course, CS1.5). Furthermore, the CS2 course is typically listed as a prerequisite for a host of other courses, and is often followed at a later point in the curriculum by a more in-depth study of data structures and algorithms (CS7). We feel that this book provides a strong foundation for a CS2 course, with the companion book, Algorithm Design: Foundations, Analysis, and Internet Examples, being a good text for a CS7 course. The importance of data structure design and analysis in the curriculum is fully justified, given the importance of efficient data structures in most software systems, including operating systems, databases, compilers, and scientific simulations.
With the emergence of the object-oriented paradigm as the framework of choice for the implementation of robust and reusable software, we have tried to take a consistent object-oriented viewpoint throughout this text. One of the main ideas of the object-oriented approach is that data should be presented as being encapsulated with the methods that access and modify them. That is, rather than simply viewing data as a collection of bytes and addresses, we think of data as instances of an abstract data type (ADT) that includes a repertory of methods for performing operations on the data. Likewise, object-oriented solutions are often organized utilizing common design patterns, which facilitate software reuse and robustness. Thus, we present each data structure using ADTs and their respective implementations and we introduce important design patterns as means to organize those implementations into classes, methods, and objects.