Data Structures and Algorithms in Java

Citation

Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2014). Data Structures and Algorithms in Java (6th ed.). Wiley.

Chapter Summary

The book runs to 736 pages in fifteen chapters, followed by a bibliography and an index. Wiley describes the exercises as arranged by purpose: reinforcement problems check understanding, creativity problems ask for new classes, and projects ask for whole programs. Unlike many data-structures texts, it spends its first two chapters on the Java language and on object-oriented design before any data structure appears; the first one, the array, arrives on page 103.

Chapters 1–2: Java Primer; Object-Oriented Design

Chapter 1 reviews the language: classes and objects, strings, wrappers, arrays and enum types, expressions, control flow, simple input and output, and packages. Its last section treats software development as a process (design, pseudocode, coding, documentation and style, testing and debugging). Chapter 2 moves to the goals, principles and patterns of object-oriented design, then inheritance, interfaces and abstract classes, exceptions, casting and generics, and nested classes.

Chapter 3: Fundamental Data Structures

Arrays come first, with examples such as storing game entries, sorting an array and simple cryptography with character arrays. Singly, circularly and doubly linked lists follow, each with an implementation, and the chapter closes with equivalence testing and cloning of data structures.

Chapter 4: Algorithm Analysis

The chapter starts from experimental studies and their limits, introduces "the seven functions used in this book", and then develops asymptotic analysis with Big-Oh notation. It ends with simple justification techniques, including induction and loop invariants.

Chapter 5: Recursion

Illustrative examples (factorial, drawing an English ruler, binary search, file systems) lead into the analysis of recursive algorithms, linear, binary and multiple recursion, the design of recursive algorithms, the danger of unbounded recursion in Java, and the elimination of tail recursion. Wiley notes that this chapter is new in the sixth edition and collects material previously spread over several chapters.

Chapters 6–7: Stacks, Queues, and Deques; List and Iterator ADTs

Chapter 6 presents each of the three structures as an abstract data type and then implements it with arrays and, where relevant, linked lists; applications include reversing an array and matching parentheses and HTML tags. Chapter 7 covers the list ADT, array lists with an amortized analysis of dynamic arrays, positional lists, iterators and the Java Collections Framework, and ends with a case study on maintaining access frequencies with the move-to-front heuristic.

Chapters 8–9: Trees; Priority Queues

Chapter 8 defines general and binary trees, gives linked and array-based representations, and devotes a long section to traversals (preorder, postorder, breadth-first, inorder, Euler tours). Chapter 9 defines the priority queue ADT, implements it with unsorted and sorted lists and then with heaps, and shows selection-sort, insertion-sort and heap-sort as sorting with a priority queue. It closes with adaptable priority queues.

Chapters 10–11: Maps, Hash Tables, and Skip Lists; Search Trees

Chapter 10 covers the map ADT, hash tables (hash functions, collision handling, load factors and rehashing), sorted maps, skip lists, and sets, multisets and multimaps. Chapter 11 starts with binary search trees and a Java framework for balancing, then treats AVL trees, splay trees, (2,4) trees and red-black trees.

Chapters 12–13: Sorting and Selection; Text Processing

Chapter 12 covers merge-sort and quick-sort, the lower bound for comparison sorting, bucket-sort and radix-sort, a comparison of sorting algorithms, and selection by prune-and-search. Chapter 13 turns to strings: pattern matching (brute force, Boyer-Moore, Knuth-Morris-Pratt), tries, text compression with the greedy method, and dynamic programming.

Chapters 14–15: Graph Algorithms; Memory Management and B-Trees

Chapter 14 gives the graph ADT, four graph representations, depth-first and breadth-first search, transitive closure, topological ordering, shortest paths and minimum spanning trees. Chapter 15 looks below the language: stacks and the heap in the Java Virtual Machine, garbage collection, memory hierarchies and caching, B-trees and external-memory sorting.

Key Concepts

Chapters 1–5: Language, Design, Analysis and Recursion

• Object-oriented design principles and patterns: the vocabulary of Chapter 2, used later to explain why each structure is built as it is.
• Generics and interfaces: the Java mechanisms through which each abstract data type is expressed.
• Big-Oh and asymptotic analysis: the measure of running time used for every later structure.
• Recursion: a technique with its own analysis and its own failure modes, treated in a dedicated chapter.

Chapters 6–11: Linear Structures, Trees and Maps

• Abstract data type: an operations-only specification, paired in the book with a Java interface.
• Amortized analysis: used for dynamic arrays and, in a starred section, for splay trees.
• Positional list and iterator: ways of exposing locations in a sequence without exposing the representation.
• Heap, hash table and balanced search tree: the three central structures for priority queues, maps and ordered maps.

Chapters 12–15: Algorithms and Systems

• Divide-and-conquer sorting and the sorting lower bound: the contrast between merge-sort and quick-sort and the limits of comparison sorting.
• Tries and dynamic programming: the tools of the text-processing chapter.
• Graph traversal, shortest paths and spanning trees: the core of the graph chapter.
• Memory hierarchies and B-trees: the link between data structures and the machine.

Critical Analysis

Strengths

• Interface first, then implementation. Wiley states that every ADT has an associated Java interface and that concrete structures are classes implementing it, gathered in the package net.datastructures and designed to complement the Java Collections Framework. Chapter 7 compares the book's positional list with the Collections Framework directly, which helps readers move from teaching code to library code.
• A deliberate order. Algorithm analysis (Chapter 4) and recursion (Chapter 5) come before the stacks, trees and sorts that depend on them, and the hardest structures (balanced trees, Chapter 11) arrive after maps and priority queues have set the pattern.
• Exercises sorted by purpose. The split into reinforcement, creativity and project problems lets a course pick short checks for homework and whole programs for assignments.
• Wide scope for one volume. Text processing, graph algorithms and external memory sit beside the classical structures, so the book can serve as the bridge to a dedicated algorithms course.

Limitations

• Java is part of the price of admission. About the first hundred pages cover the language and object-oriented design. That is helpful for readers who need it, but readers who already write Java will skim them, and readers who want language-neutral treatment will find the code tied to Java idioms such as generics, iterators and nested classes.
• Late-Java features are not in the picture. Wiley's list of changes mentions type inference introduced in Java 7, and nothing in the contents points to later language features, so code written in newer Java styles will look different from the printed examples.
• Algorithms are treated briefly. Text processing takes one chapter of about forty pages and graphs one of about seventy-five, so the book introduces these topics rather than developing them.
• Some sections are analysis-heavy. Several sections carry a star mark in the contents (for example bottom-up heap construction, the probabilistic analysis of skip lists, and the amortized analysis of splaying). Readers meeting the subject for the first time can expect to leave these for a second pass.

Where It Fits in the Course

This is a second-course text: it assumes a first programming course and builds data structures in a single language. Among the books listed for the course, Wengrow's A Common-Sense Guide to Data Structures and Algorithms and Bhargava's Grokking Algorithms are gentler, plain-language or illustrated introductions that can serve as a first pass or a companion; neither is organised around a Java class library. Pat Morin's Open Data Structures covers similar ground with a precise interface, implementation and running-time proof for each structure, and it is free online in Java, C++ and pseudocode editions, which makes it a natural second source for the proofs Goodrich, Tamassia and Goldwasser treat lightly.

Brass's Advanced Data Structures is a graduate-level text that treats data structures as algorithm design, with code in C, and Okasaki's Purely Functional Data Structures addresses immutable structures in functional languages. Both are sensible next steps after this book rather than alternatives to it.

How to Use This Book

The book suits second-year undergraduates who have finished a first programming course and want the classical structures implemented in Java; the contents list no separate mathematics chapter, and Chapter 4 itself introduces the growth functions, Big-Oh notation and proof by induction. A reader who already knows Java can start at Chapter 2 or Chapter 3.

A practical plan for one semester:

• Core: Chapters 3 to 9 in order, with Chapter 4 read before the structures that use its analysis. Chapter 5 should be finished before the tree chapter.
• Second half: Chapters 10 and 11 (maps and search trees) and Chapter 12 (sorting), choosing among the balanced trees according to the course (AVL and red-black trees, for example).
• Optional: Chapters 13 to 15 as the bridge to an algorithms course, or as independent study; skip the starred sections on a first pass.

Write the code rather than only reading it: implement the stack, queue and positional list from the interfaces, then compare each one with its counterpart in the Java Collections Framework. Use reinforcement problems after each section and keep creativity problems and projects for the end of each chapter.