Data Structures and Algorithms in Java
Michael T. Goodrich
Department of Computer Science University of California, Irvine

1
Roberto Tamassia
Department of Computer Science Brown University
0-471-73884-0
Fourth Edition
John Wiley & Sons, Inc.
ASSOCIATE PUBLISHER Dan Sayre
MARKETING DIRECTOR Frank Lyman
EDITORIAL ASSISTANT Bridget Morrisey
SENIOR PRODUCTION EDITOR Ken Santor
COVER DESIGNER Hope Miller
COVER PHOTO RESEARCHER Lisa Gee
COVER PHOTO Ralph A.
Clevenger/Corbis
This book was set in by the authors and printed and bound by R.R. Donnelley
- Crawfordsville. The cover was printed by Phoenix Color, Inc.


creativity, and project exercises to 670. Added exercises include new projects on
maintaining a game's high-score list, evaluating postfix and infix expressions,
minimax game-tree evaluation, processing stock buy and sell orders, scheduling
CPU jobs, n-body simulation, computing DNA-strand edit distance, and creating
and solving mazes.
This book is related to the following books:
• M.T. Goodrich, R. Tamassia, and D.M. Mount, Data Structures and Algorithms
in C++, John Wiley & Sons, Inc., 2004. This book has a similar overall structure to
the present book, but uses C++ as the underlying language (with some modest, but
necessary pedagogical differences required by this approach). Thus, it could make

3
for a handy companion book in a curriculum that allows for either a Java or C++
track in the introductory courses.
• M.T. Goodrich and R. Tamassia, Algorithm Design: Foundations, Analysis, and
Internet Examples, John Wiley & Sons, Inc., 2002. This is a textbook for a more
advanced algorithms and data structures course, such as CS210 (T/W/C/S versions)
in the IEEE/ACM 2001 curriculum.
Use as a Textbook
The design and analysis of efficient data structures has long been recognized as a
vital 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, the introductory courses are presented as a two- or three-
course sequence. Elementary data structures are often briefly introduced in the first
programming or introduction to computer science course and this is followed by a
more in-depth introduction to data structures in the following course(s).
Furthermore, this course sequence is typically followed at a later point in the
curriculum by a more in-depth study of data structures and algorithms. 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,

.
Students are encouraged to use this site along with the book, to help with exercises
and increase understanding of the subject. Instructors are likewise welcome to use
the site to help plan, organize, and present their course materials.
For the Student
for all readers, and specifically for students, we include:
• All the Java source code presented in this book.
• The student version of the net.datastructures package.
• Slide handouts (four-per-page) in PDF format.
• A database of hints to all exercises, indexed by problem number.
• Java animations and interactive applets for data structures and algorithms.
• Hyperlinks to other data structures and algorithms resources.
We feel that the Java animations and interactive applets should be of particular
interest, since they allow readers to interactively "play" with different data
structures, which leads to better understanding of the different ADTs. In addition,
the hints should be of considerable use to anyone needing a little help getting
started on certain exercises.
For the Instructor
For instructors using this book, we include the following additional teaching aids:
• Solutions to over two hundred of the book's exercises.
• A keyword-searchable database of additional exercises.
• The complete net.datastructures package.

5
• Additional Java source code.
• Slides in Powerpoint and PDF (one-per-page) format.
• Self-contained special-topic supplements, including discussions on convex
hulls, range trees, and orthogonal segment intersection.
The slides are fully editable, so as to allow an instructor using this book full
freedom in customizing his or her presentations.

PF1. Fundamental Programming Constructs
Chapters 1
& 2
PF2. Algorithms and Problem-Solving
Sections 1.9
& 4.2
PF3. Fundamental Data Structures
Sections 3.1, 5.1-3.2, 5.3, , 6.1-6.4, 7.1, 7.3, 8.1, 8.3, 9.1-9.4, 10.1, & 13.1
PF4. Recursion
Section 3.5
SE1. Software Design
Chapter 2 and Sections 6.2.2, 6.3, 7.3.7, 8.1.2, & 13.3.1
SE2. Using APIs
Sections 2.4, 5.1, 5.2, 5.3, 6.1.1, 6.2, 6.4, 6.3, 7.1, 7.3.1, 8.1, 9.1, 9.3, 11.6,
& 13.1
AL1. Basic Algorithmic Analysis
Chapter 4
AL2. Algorithmic Strategies
Sections 11.1.1
, 11.7.1, 12.2.1, 12.4.2, & 12.5.2
AL3. Fundamental Computing Algorithms
Sections 8.1.4, 8.2.3, 8.3.5, 9.2, & 9.3.3, and Chapters 11, 12, & 13
DS1. Functions, Relations, and Sets
Sections 4.1
, 8.1, & 11.6
DS3. Proof Techniques
Sections 4.3, 6.1.4, 7.3.3, 8.3, 10.2, 10.3, 10.4, 10.5, 11.2.1, 11.3, 11.6.2,
13.1
, 13.3.1, 13.4, & 13.5



8
14. Memory
A. Useful Mathematical Facts Prerequisites
We have written this book assuming that the reader comes to it with certain
knowledge.That is, we assume that the reader is at least vaguely familiar with a
high-level programming language, such as C, C++, or Java, and that he or she
understands the main constructs from such a high-level language, including:
• Variables and expressions.
• Methods (also known as functions or procedures).
• Decision structures (such as if-statements and switch-statements).
• Iteration structures (for-loops and while-loops).
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 (). We give a summary of other useful mathematical facts,
including elementary probability, in Appendix A.
About the Authors
Professors Goodrich and Tamassia are well-recognized researchers in algorithms

algorithmdesign.net, supported by Drs. Goodrich and Tamassia, are used as
reference material by students, teachers, and professionals worldwide.
Acknowledgments
There are a number of individuals who have made contributions to this book.
We are grateful to all our research collaborators and teaching assistants, who
provided feedback on early drafts of chapters and have helped us in developing
exercises, programming assignments, and algorithm animation systems.In
particular, we would like to thank Jeff Achter, Vesselin Arnaudov, James Baker,
Ryan Baker,Benjamin Boer, Mike Boilen, Devin Borland, Lubomir Bourdev, Stina
Bridgeman, Bryan Cantrill, Yi-Jen Chiang, Robert Cohen, David Ellis, David
Emory, Jody Fanto, Ben Finkel, Ashim Garg, Natasha Gelfand, Mark Handy,
Michael Horn, Beno^it Hudson, Jovanna Ignatowicz, Seth Padowitz, James
Piechota, Dan Polivy, Seth Proctor, Susannah Raub, Haru Sakai, Andy Schwerin,
Michael Shapiro, MikeShim, Michael Shin, Galina Shubina, Christian Straub, Ye

10
Sun, Nikos Triandopoulos, Luca Vismara, Danfeng Yao, Jason Ye, and Eric
Zamore.
Lubomir Bourdev, Mike Demmer, Mark Handy, Michael Horn, and Scott Speigler
developed a basic Java tutorial, which ultimately led to Chapter 1
, Java
Programming.
Special thanks go to Eric Zamore, who contributed to the development of the Java
code examples in this book and to the initial design, implementation, and testing of
the net.datastructures library of data structures and algorithms in Java. We are also
grateful to Vesselin Arnaudov and ike Shim for testing the current version of
net.datastructures
Many students and instructors have used the two previous editions of this book and
their experiences and responses have helped shape this fourth edition.
There have been a number of friends and colleagues whose comments have lead to

Visio® for the figures.
Finally, we would like to warmly thank Isabel Cruz, Karen Goodrich, 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. We
also thank them for reminding us that there are things in life beyond writing books.
Michael T. Goodrich
Roberto Tamassia

20
1.3.2
Operators

21
1.3.3

13
Casting and Autoboxing/Unboxing in
Expressions
25
1.4
Control Flow
27
1.4.1
The If and Switch
Statements
27
1.4.2
Loops

29
1.4.3
Explicit Control-Flow
Statements
32
1.5
Arrays
34

1.9.3
Coding

49
1.9.4
Testing and
Debugging
53
1.10
Exercises
55
java.datastructures.net

15
1.1 Getting Started: Classes, Types, and Objects
Building data structures and algorithms requires that we communicate detailed
instructions to a computer, and an excellent way to perform such communication is
using a high-level computer language, such as Java. In this chapter, we give a brief
overview of the Java programming language, assuming the reader is somewhat
familiar with an existing high-level language. This book does not provide a complete
description of the Java language, however. There are major aspects of the language
that are not directly relevant to data structure design, which are not included here,
such as threads and sockets. For the reader interested in learning more about Java,
please see the notes at the end of this chapter. We begin with a program that prints
"Hello Universe!" on the screen, which is shown in a dissected form in Figure 1.1.
Code Fragment 1.1: A Counter class for a simple
counter, which can be accessed, incremented, and
decremented.

17

In this example, notice that the class definition is delimited by braces, that is, it
begins with a "{" and ends with a "} ". In Java, any set of statements between the
braces "{" and "}" define a program block.
As with the Universe class, the Counter class is public, which means that any other
class can create and use a Counter object. The Counter has one instance variable—
an integer called count. This variable is initialized to 0 in the constructor method,
Counter, which is called when we wish to create a new Counter object (this method
always has the same name as the class it belongs to). This class also has one
accessor method, getCount, which returns the current value of the counter. Finally,
this class has two update methods—a method, incrementCount, which increments
the counter, and a method, decrementCount, which decrements the counter.
Admittedly, this is a pretty boring class, but at least it shows us the syntax and
structure of a Java class. It also shows us that a Java class does not have to have a
main method (but such a class can do nothing by itself).
The name of a class, method, or variable in Java is called an identifier, which can be
any string of characters as long as it begins with a letter and consists of letters,
numbers, and underscore characters (where "letter" and "number" can be from any
written language defined in the Unicode character set). We list the exceptions to
this general rule for Java identifiers in Table 1.1
.
Table 1.1: A listing of the reserved words in Java.
These names cannot be used as method or variable
names in Java.
Reserved Words

private
true
class
goto
protected
try
const
if
public
void
continue
implements
return
volatile
default
import
short
while
do
instanceof
static
double
int
super
Class Modifiers

20
Class modifiers are optional keywords that precede the class keyword. We have
already seen examples that use the public keyword. In general, the different class
modifiers and their meaning is as follows:

21
int
32-bit signed two's complement integer
long
64-bit signed two's complement integer
float
32-bit floating-point number (IEEE 754-1985)
double
64-bit floating-point number (IEEE 754-1985)
A variable declared to have one of these types simply stores a value of that type,
rather than a reference to some object. Integer constants, like 14 or 195, are of type
int, unless followed immediately by an 'L' or 'l', in which case they are of type long.
Floating-point constants, like 3.1415 or 2.158e5, are of type double, unless
followed immediately by an 'F' or 'f', in which case they are of type float. We show
a simple class in Code Fragment 1.2 that defines a number of base types as local
variables for the main method.
Code Fragment 1.2: A Base class showing
example uses of base types.

22

Comments
Note the use of comments in this and other examples. These comments are
annotations provided for human readers and are not processed by a Java compiler.
Java allows for two kinds of comments-block comments and inline comments-
which define text ignored by the compiler. Java uses a /* to begin a block
comment and a */ to close it. Of particular note is a comment that begins with /**,
for such comments have a special format that allows a program called Javadoc to
read these comments and automatically generate documentation for Java
programs. We discuss the syntax and interpretation of Javadoc comments in

simply create new objects and to assign the reference to these objects to a variable.
Figure 1.3: Example uses of the new operator.

24

Calling the new operator on a class type causes three events to occur:
• A new object is dynamically allocated in memory, and all instance
variables are initialized to standard default values. The default values are null
for object variables and 0 for all base types except boolean variables (which are
false by default).
• The constructor for the new object is called with the parameters specified.
The constructor fills in meaningful values for the instance variables and performs
any additional computations that must be done to create this object.
• After the constructor returns, the new operator returns a reference (that is,
a memory address) to the newly created object. If the expression is in the form of
an assignment statement, then this address is stored in the object variable, so the
object variable refers to this newly created object.
Number Objects
We sometimes want to store numbers as objects, but base type numbers are not
themselves objects, as we have noted. To get around this obstacle, Java defines a
wrapper class for each numeric base type. We call these classes number classes.
In Table 1.2, we show the numeric base types and their corresponding number
class, along with examples of how number objects are created and accessed. Since
Java 5.0, a creation operation is performed automatically any time we pass a base
number to a method expecting a corresponding object. Likewise, the

25