Data Structures and Algorithms in Java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. The major changes in this sixth edition include the following:
We assume that the reader is at least vaguely familiar with a high-level programming language, such as C, C++, Python, or Java, and that he or she understands the main constructs from such a high-level language, including:
For readers who are familiar with these concepts, but not with how they are expressed in Java, we provide a primer on the Java language in Chapter 1. Still, this book is primarily a data structures book, not a Java book; hence, it does not provide a comprehensive treatment of Java. Nevertheless, we do not assume that the reader is necessarily familiar with object-oriented design or with linked structures, such as linked lists, for these topics are covered in the core chapters of this book.
In terms of mathematical background, we assume the reader is somewhat familiar with topics from high-school mathematics. Even so, in Chapter 4, we discuss the seven most-important functions for algorithm analysis. In fact, sections that use something other than one of these seven functions are considered optional, and are indicated with a star ().
This book is accompanied by an extensive set of online resources, which can be found at the following website:
www.wiley.com/college/goodrich
Included on this website is a collection of educational aids that augment the topics of this book, for both students and instructors. For all readers, and especially for students, we include the following resources:
For instructors using this book, we include the following additional teaching aids:
The slides are fully editable, so as to allow an instructor using this book full freedom in customizing his or her presentations.
The design and analysis of efficient data structures has long been recognized as a core subject in computing. 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 and algorithms in most software systems, including the Web, operating systems, databases, compilers, and scientific simulation systems.
This book is designed for use in a beginning-level data structures course, or in an intermediate-level introduction to algorithms course. The chapters for this book are organized to provide a pedagogical path that starts with the basics of Java programming and object-oriented design. We then discuss concrete structures including arrays and linked lists, and foundational techniques like algorithm analysis and recursion. In the main portion of the book we present fundamental data structures and algorithms, concluding with a discussion of memory management. A detailed table of contents follows this preface, beginning on page x.
To assist instructors in designing a course in the context of the IEEE/ACM 2013 Computing Curriculum, the following table describes curricular knowledge units that are covered within this book.
Knowledge Unit | Relevant Material |
AL/Basic Analysis | Chapter 4 and Sections 5.2 & 12.1.4 |
AL/Algorithmic Strategies | Sections 5.3.3, 12.1.1, 13.2.1, 13.4.2, 13.5, 14.6.2 & 14.7 |
AL/Fundamental Data Structures and Algorithms | Sections 3.1.2, 5.1.3, 9.3, 9.4.1, 10.2, 11.1, 13.2, and Chapters 12 & 14 |
AL/Advanced Data Structures | Sections 7.2.1, 10.4, 11.2–11.6, 12.2.1, 13.3, 14.5.1 & 15.3 |
AR/Memory System Organization and Architecture | Chapter 15 |
DS/Sets, Relations, and Functions | Sections 9.2.2 & 10.5 |
DS/Proof Techniques | Sections 4.4, 5.2, 7.2.3, 9.3.4 & 12.3.1 |
DS/Basics of Counting | Sections 2.2.3, 6.2.2, 8.2.2 & 12.1.4. |
DS/Graphs and Trees | Chapters 8 and 14 |
DS/Discrete Probability | Sections 3.1.3, 10.2, 10.4.2 & 12.2.1 |
PL/Object-Oriented Programming | Chapter 2 and Sections 7.3, 9.5.1 & 11.2.1 |
SDF/Algorithms and Design | Sections 2.1, 4.3 & 12.1.1 |
SDF/Fundamental Programming Concepts | Chapters 1 & 5 |
SDF/Fundamental Data Structures | Chapters 3 & 6, and Sections 1.3, 9.1 & 10.1 |
SDF/Developmental Methods | Sections 1.9 & 2.4 |
SE/Software Design | Section 2.1 |
Mapping the IEEE/ACM 2013 Computing Curriculum knowledge units to coverage within this book.
Michael Goodrich received his Ph.D. in Computer Science from Purdue University in 1987. He is currently a Chancellor's Professor in the Department of Computer Science at University of California, Irvine. Previously, he was a professor at Johns Hopkins University. He is a Fulbright Scholar and a Fellow of the American Association for the Advancement of Science (AAAS), Association for Computing Machinery (ACM), and Institute of Electrical and Electronics Engineers (IEEE). He is a recipient of the IEEE Computer Society Technical Achievement Award, the ACM Recognition of Service Award, and the Pond Award for Excellence in Undergraduate Teaching.
Roberto Tamassia received his Ph.D. in Electrical and Computer Engineering from the University of Illinois at Urbana–Champaign in 1988. He is the Plastech Professor of Computer Science and the Chair of the Department of Computer Science at Brown University. He is also the Director of Brown's Center for Geometric Computing. His research interests include information security, cryptography, analysis, design, and implementation of algorithms, graph drawing, and computational geometry. He is a Fellow of the American Association for the Advancement of Science (AAAS), Association for Computing Machinery (ACM) and Institute for Electrical and Electronic Engineers (IEEE). He is a recipient of the IEEE Computer Society Technical Achievement Award.
Michael Goldwasser received his Ph.D. in Computer Science from Stanford University in 1997. He is currently Professor and Director of the Computer Science program in the Department of Mathematics and Computer Science at Saint Louis University. He was previously a faculty member in the Department of Computer Science at Loyola University Chicago. His research interests focus on the design and implementation of algorithms, having published work involving approximation algorithms, online computation, computational biology, and computational geometry. He is also active in the computer science education community.
There are so many individuals who have made contributions to the development of this book over the past decade, it is difficult to name them all. We wish to reiterate our thanks to the many research collaborators and teaching assistants whose feedback shaped the previous versions of this material. The benefits of those contributions carry forward to this book.
For the sixth edition, we are indebted to the outside reviewers and readers for their copious comments, emails, and constructive criticisms. We therefore thank the following people for their comments and suggestions: Sameer O. Abufardeh (North Dakota State University), Mary Boelk (Marquette University), Frederick Crabbe (United States Naval Academy), Scot Drysdale (Dartmouth College), David Eisner, Henry A. Etlinger (Rochester Institute of Technology), Chun-Hsi Huang (University of Connecticut), John Lasseter (Hobart and William Smith Colleges), Yupeng Lin, Suely Oliveira (University of Iowa), Vincent van Oostrom (Utrecht University), Justus Piater (University of Innsbruck), Victor I. Shtern (Boston University), Tim Soethout, and a number of additional anonymous reviewers.
There have been a number of friends and colleagues whose comments have led to improvements in the text. We are particularly thankful to Erin Chambers, Karen Goodrich, David Letscher, David Mount, and Ioannis Tollis for their insightful comments. In addition, contributions by David Mount to the coverage of recursion and to several figures are gratefully acknowledged.
We appreciate the wonderful team at Wiley, including our editor, Beth Lang Golub, for her enthusiastic support of this project from beginning to end, and the Product Solutions Group editors, Mary O'Sullivan and Ellen Keohane, for carrying the project to its completion. The quality of this book is greatly enhanced as a result of the attention to detail demonstrated by our copyeditor, Julie Kennedy. The final months of the production process were gracefully managed by Joyce Poh.
Finally, we would like to warmly thank Karen Goodrich, Isabel Cruz, Susan Goldwasser, Giuseppe Di Battista, Franco Preparata, Ioannis Tollis, and our parents for providing advice, encouragement, and support at various stages of the preparation of this book, and Calista and Maya Goldwasser for offering their advice regarding the artistic merits of many illustrations. More importantly, we thank all of these people for reminding us that there are things in life beyond writing books.
Michael T. Goodrich
Roberto Tamassia
Michael H. Goldwasser