The design and analysis of efficient data structures has long been recognized as a key subject in computing, for 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 introduction to data structures (CS2) course. Furthermore, this introductory 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). Curricula based upon the quarter system follow a similar approach, but divide the subject matter into more courses. In either case, however, we feel that the central role 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 simulation systems.
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.