xviii Preface
r
Chapter 8 uses the new union/find analysis by Seidel and Sharir, and shows the
O( Mα(M, N) ) bound instead of the weaker O( M log
∗
N ) bound in prior editions.
r
Chapter 12 adds material on suffix trees and suffix arrays, including the linear-time
suffix array construction algorithm by Karkkainen and Sanders (with implementation).
The sections covering deterministic skip lists and AA-trees have been removed.
r
Throughout the text, the code has been updated to use the diamond operator from
Java 7.
Approach
Although the material in this text is largely language independent, programming requires
the use of a specific language. As the title implies, we have chosen Java for this book.
Java is often examined in comparison with C++. Java offers many benefits, and pro-
grammers often view Java as a safer, more portable, and easier-to-use language than C++.
As such, it makes a fine core language for discussing and implementing fundamental data
structures. Other important parts of Java, such as threads and its GUI, although important,
are not needed in this text and thus are not discussed.
Complete versions of the data structures, in both Java and C++, are available on
the Internet. We use similar coding conventions to make the parallels between the two
languages more evident.
Overview
Chapter 1 contains review material on discrete math and recursion. I believe the only way
to be comfortable with recursion is to see good uses over and over. Therefore, recursion
is prevalent in this text, with examples in every chapter except Chapter 5. Chapter 1 also
presents material that serves as a review of inheritance in Java. Included is a discussion of
Java generics.
Chapter 2 deals with algorithm analysis. This chapter explains asymptotic analysis and
its major weaknesses. Many examples are provided, including an in-depth explanation of
logarithmic running time. Simple recursive programs are analyzed by intuitively converting
them into iterative programs. More complicated divide-and-conquer programs are intro-
duced, but some of the analysis (solving recurrence relations) is implicitly delayed until
Chapter 7, where it is performed in detail.
Chapter 3 covers lists, stacks, and queues. This chapter has been significantly revised
from prior editions. It now includes a discussion of the Collections API
ArrayList
and LinkedList classes, and it provides implementations of a significant subset of the
collections API
ArrayList and LinkedList classes.
Chapter 4 covers trees, with an emphasis on search trees, including external search
trees (B-trees). The UNIX file system and expression trees are used as examples. AVL trees
and splay trees are introduced. More careful treatment of search tree implementation details
is found in Chapter 12. Additional coverage of trees, such as file compression and game
trees, is deferred until Chapter 10. Data structures for an external medium are considered
as the final topic in several chapters. New to this edition is a discussion of the Collections
API
TreeSet and TreeMap classes, including a significant example that illustrates the use of
three separate maps to efficiently solve a problem.