This Java data structures book provides a strong introduction to object-oriented programming. It features a comprehensive presentation of the fundamentals of algorithm analysis foralgorithm and data structure comparisons, along with basic software engineering principles for the object-oriented analysis and design of a large information system. It is the first data structures book to present an introduction to software design and development at an intermediate level. Key Features bull; bull;Data structure library: Lists, stacks, queues, trees, balanced trees, graphs, and files are discussed in detail and implemented in Java. bull;UML: Software analysis and modeling are presented using a subset of UML at a level accessible to second- or third-year students. bull;Timing analysis: Timing is extensively studied and used throughout. bull;Two case studies: Real examples illustrate the object-oriented development process for the analysis and design of a non-trivial system. bull;Electronic materials: All of the code included in the text and an example of a well-designed data structure library with implementations of all the standard data structures is provided for downloading.

Most computer-science curricula have at least one course in data structures. Such a course is usually taken by all majors since its contents are used in subsequent courses. Historically, this course has dealt almost solely with data structures, including their time and space analyses (along the lines of the courses CS1 and CS2 of the ACM88 Curriculum). However, in recent years, such a course is also expected to give students a good object-oriented programming background and, increasingly, an introductory background in software development. This is reflected in the ACM/IEEE report, "Computing Curricula 2001: Computer Science." The report recommends that one half of the .SE1 knowledge unit--software design--be covered in first year. The topics to be covered include fundamental design concepts and principles, object-oriented analysis and design, and design for reuse. This book was written to provide a strong introduction to these software design topics at the first- or second-year level. The material is integrated with the coverage of data structures in keeping with the recommendations of Curricula 2001. This book was originally designed for a second-year course taken by all our majors to reinforce data structures from first year and introduce software design. With the evolution of more software design into first year, in some situations it is also appropriate for the second term of first year (i.e., CS2). In particular, it will be useful to those institutions that have a strong object-oriented CS1 course and wish to present more application-level software development to their students. For example, the book covers almost all the material of courses CS102 O , CS103 O , and CS112 O of Curricula 2001. To fit at the CS2 level, the book includes all the material on the basic data structures--arrays and linked lists--before treating more advanced data structures. The amount of advanced material that can be covered in a second-term first-year course depends on the background of the students and the pace of the course. However, the book has more material than can typically be covered in a CS2 course. As a result, it can also be used in a subsequent course to develop more depth in data structures and software engineering. Alternately, if first year uses a breadth-first approach, this book is suitable for a strong second-year course that integrates data structures and software engineering. Our presentation is from an object-oriented perspective and includes many of the recent software engineering techniques for an object-oriented development of a system. For our implementation language, we have chosen Java. It is an object-oriented language that includes interfaces, abstract classes, multiple interface inheritance, exception handling, automatic garbage collection, and GUI interfaces. In addition, it is extremely portable as it runs in a Web browser on almost every machine. Although Java is the language of implementation, we only use moderate amounts of code. Like in most other recent data structure books, abstract data types (ADTs) are discussed early. ADTs offer several advantages that include encapsulation and information hiding. ADTs are discussed both formally (that can largely be ignored) and in terms of their Java implementation. In any object-oriented programming language, a concrete class provides a clean implementation of an ADT. The use of inheritance facilitates the design of modular, extendable, and reusable systems. The existence of multiple interface inheritance in Java opens up the possibilities for more modular systems. Yet using ADTs and inheritance in developing software does not guarantee quality software. One of the primary- goals is to integrate several software-engineering principles with the data structures content of the course. Students at the first- or second-year level should be introduced to the principles of software en