Preface

This book has four major themes: algorithms, data structures, abstract data types (ADTs), and object-oriented methods. All of these themes are of central importance in computer science and software engineering. 

   The book focuses on a number of important ADTs – stacks, queues, lists (sequences), sets, maps (tables), priority queues, trees, and graphs – that turn up again and again in software engineering. It uses these ADTs to motivate the data structures required to implement them – arrays, linked lists, search trees, hash tables, and heaps – and algorithms associated with these data structures – insertion, deletion, searching, merging, sorting, and traversal. The book shows how to implement these data structures and algorithms in the object-oriented programming language Java.

   The book's typical approach is to introduce an ADT, illustrate its use by one or two example applications, develop a 'contract' specifying the ADT's values and operations, and finally consider which data structures are suitable for implementing the ADT. This approach clearly distinguishes between applications and implementations of the ADT, thus reinforcing a key software engineering principle: separation of concerns. The book motivates the study of data structures and algorithms by introducing them on a need-to-know basis. In other words, it adopts a practical (software engineering) approach to the subject, rather than a theoretical one. It does not neglect the important topic of algorithm analysis, but emphasizes its practical importance rather than the underlying mathematics.

   Object-oriented methods have emerged as the dominant software technology during the last decade, and Java has become the dominant programming language in computer science education. These developments call for a fresh approach to the teaching of programming and software engineering. This book takes such a fresh approach, using object-oriented methods from the outset to design and implement ADTs. It avoids the mistake of reworking an older book on algorithms and data structures that was written originally for Pascal or C.

   Several of the ADTs introduced in this book are directly supported by the Java 2 collection classes. Programmers will naturally prefer to use these collection classes rather than design and implement their own. Nevertheless, choosing the right collection classes for each application requires an understanding of the properties of different ADTs and their alternative implementations. This book aims to give readers the necessary understanding.

Readership

This book can be read by anyone who has taken a first programming course in Java.

   The book is designed primarily as a text for a second-level course in algorithms and data structures, in the context of a computer science program in which Java is the main programming language. In terms of the 1991 and 2001 ACM Computing Curricula, the book covers the knowledge units summarized in Table P.1.

   The book is also suitable for practicing software engineers who have just learned Java and who now wish to gain (or refresh) the knowledge of algorithms and data structures required to make effective use of the Java 2 collection classes.

   The detailed prerequisites of this book are as follows:

• A knowledge of fundamental Java programming topics – expressions, statements, objects, and classes – is essential. A knowledge of more advanced topics – inheritance, exceptions, interfaces, inner classes – is desirable but not essential before reading this book. Readers unfamiliar with the latter topics should refer to Appendix B whenever necessary.
• Certain mathematical topics – powers, logarithms, series summations, and recurrences – are needed to analyze the efficiency of algorithms. Most of these mathematical topics are taught in secondary/high schools. Readers unfamiliar with any of these topics should refer to Appendix A whenever necessary.

Outline

Chapter 1 introduces two of this book's major themes: algorithms and data structures. Chapter 2 takes a closer look at algorithms, showing how we can analyze their efficiency and introducing recursive algorithms.

   Chapters 3 and 4 review two simple and ubiquitous data structures – arrays and linked lists – together with their associated insertion, deletion, searching, merging, and sorting algorithms. Later in the book, Chapters 10, 12, 13, and 16 introduce more sophisticated data structures – binary search trees, hash tables, heaps, AVL-trees, and B-trees – again together with their associated algorithms.

   Chapter 5 takes a close look at the idea of an abstract data type (ADT). It introduces the notion of a 'contract' that specifies the values and operations of an ADT without committing to a particular representation. Chapters 6 (stacks), 7 (queues), 8 (lists), 9 (sets), 11 (maps), 13 (priority queues), 14 (trees), and 15 (graphs) introduce a variety of collection ADTs together with alternative implementations of each. The list, set, and map ADTs covered in Chapters 8, 9, and 11 are in fact simplified versions of the corresponding Java 2 collection classes.

   Chapter 17 concludes the book. It discusses the role of ADTs in object-oriented design. It also discusses the distinction between heterogeneous and homogeneous collections, and an extension of Java that supports generic homogeneous collections.

   Appendix A summarizes the mathematical topics needed to analyze the efficiency of algorithms. Appendix B summarizes the features of Java that are most important in this book, particularly the more advanced features that are likely to be omitted in a first programming course. Appendix C summarizes the Java 2 collection classes.

   Ideally, all the chapters of this book should be read in numerical order. Figure P.2 summarizes the dependencies between chapters. Clearly, Chapters 1–5 must be read first, and Chapters 6–9 all rely on this introductory material. Chapter 10 depends on Chapters 6 and 9, and in turn Chapters 11, 13 and 16 all depend on Chapter 10. Readers may vary the order of some of the later chapters, as indicated by Figure P.2. Readers may also omit any of Chapters 13–17 if time is short.

Figure P.2 Dependencies between chapters.

Scope

This book is an introductory text. As such, it covers several topics, such as algorithm complexity, hash tables, and graphs, in rather less depth than would be possible in a more advanced text. Moreover, it omits altogether a variety of interesting algorithms, such as compression, encryption, geometric, linear algebra, and scheduling algorithms.

   Under Further Reading there is a list of books that do cover these more advanced topics, together with seminal papers on topics covered by this book. There are also bibliographic notes that suggest further reading on the topics covered by each chapter and by the book as a whole.

Java Collections framework

The Java 2 software development kit (SDK) provides a library of classes supporting the most common ADTs: lists, sets, and maps. These are known collectively as the Java collection classes, and they fit together in what is called the Java Collections framework. Programmers should use these collection classes rather than designing and implementing their own. However, the framework is complex and incomplete, and selecting the correct collection class for a given problem is not always easy.

   This book aims to help programmers in the following ways:

• To reduce complexity, we introduce our own contract for each ADT. Our contract captures the fundamental properties of the ADT, and is not biased towards a particular implementation.
• To maintain compatibility, our ADT contract is always a simplified version of the contract of the corresponding Java collection class (if any).The applications presented in this book can all be trivially modified to use the corresponding collection classes. (The only necessary changes are to import the java.util package and to modify certain constructor invocations.)
• To guide the selection of the appropriate ADT for a given problem, we present one or more short examples, and a case study, illustrating how to use each ADT.
• To guide the selection of the most appropriate implementation of an ADT, we analyze the efficiency of several alternative implementations, and compare them with the corresponding Java collection class (if any).
• In addition to the list, set, and map ADTs supported by the Java Collections framework, we also cover other important ADTs: stacks, queues, priority queues, trees, and graphs. Our contracts for these ADTs follow the same style as the Java Collections framework, so readers should be able to adapt easily.

Companion Web site

This book is complemented by a Web site, whose URL is:

   This Web site contains the book's contents and preface, answers to selected exercises, and Java code for all ADTs and case studies. New features will be added from time to time.

Case studies

Case studies are an important feature of this book. They can be found in Chapters 6–9, 11, 13–15, and 17.

   Each case study leads the reader through the object-oriented design and implementation of a fair-sized application program. The presentation focuses on the selection of an ADT appropriate for the application, and later on the choice of the most suitable implementation of that ADT (from among those presented earlier in the chapter). The object-oriented design of the application program itself, and the development of algorithms to be employed by the application program, are also discussed. User interface issues are generally omitted here, however.

   Complete Java source code for all case studies may be found at the companion Web site. For some case studies, there is an application program that can be downloaded and run. For others, there is an applet that can be run immediately using a Java-enabled Web browser. Where appropriate, each case study comes in two versions, one using the classes developed in this book and the other using the Java collection classes.

Exercises

Each chapter is followed by a set of exercises. Some of these exercises are drill, or simple modifications to designs, algorithms, or implementations presented in the chapter. The more challenging exercises are clearly marked as * (hard) or ** (harder).

   Sample answers to selected exercises can be found at the companion Web site.

About the authors

David Watt is a Professor of Computing Science at the University of Glasgow. He has 26 years' experience of teaching undergraduates and graduates, in programming, algorithms, data structures, software engineering, and other topics. He developed the material of Chapters 1–12 for a course in algorithms and data structures, first taught in early 1999. His research interests are design, specification, and implementation of programming languages.

Deryck Brown is a Senior Lecturer in Computing Science at the Robert Gordon University, Aberdeen. He has 6 years' experience of teaching undergraduates and graduates, in object-oriented programming, software engineering, and several other topics. His research interests are specification and implementation of programming languages, and genetic algorithms.

Acknowledgements

Most of the algorithms and data structures described in this textbook have long since passed into computer science folklore, and are almost impossible to attribute to individuals. Instead, we acknowledge those colleagues who have particularly influenced us through discussions on the topics of this book: David Davidson, Rob Irving, Alistair Kilgour, John McCall, and Joe Morris. We wish to thank the Wiley reviewers for reading and providing valuable comments on an earlier draft of this book. In addition, we would like to thank William Teahan for his extensive and detailed comments. Finally, we are delighted to acknowledge the assistance of the staff at John Wiley & Sons, particularly our editors Gaynor Redvers-Mutton and Gemma Quilter.