You are previewing Data Structures and Algorithms in Java, 6th Edition.
O'Reilly logo
Data Structures and Algorithms in Java, 6th Edition

Book Description

The design and analysis of efficient data structures has long been recognized as a key component of the Computer Science curriculum. Goodrich, Tomassia and Goldwasser's approach to this classic topic is based on the object-oriented paradigm as the framework of choice for the design of data structures. For each ADT presented in the text, the authors provide an associated Java interface. Concrete data structures realizing the ADTs are provided as Java classes implementing the interfaces. The Java code implementing fundamental data structures in this book is organized in a single Java package, net.datastructures. This package forms a coherent library of data structures and algorithms in Java specifically designed for educational purposes in a way that is complimentary with the Java Collections Framework.

Table of Contents

  1. Cover Page
  2. Title Page
  3. Copyright
  4. Dedication
  5. Preface to the Sixth Edition
    1. Prerequisites
    2. Online Resources
    3. Use as a Textbook
    4. About the Authors
    5. Additional Books by These Authors
    6. Acknowledgments
  6. Contents
  7. Chapter 1: Java Primer
    1. 1.1 Getting Started
    2. 1.2 Classes and Objects
    3. 1.3 Strings, Wrappers, Arrays, and Enum Types
    4. 1.4 Expressions
    5. 1.5 Control Flow
    6. 1.6 Simple Input and Output
    7. 1.7 An Example Program
    8. 1.8 Packages and Imports
    9. 1.9 Software Development
    10. 1.10 Exercises
    11. Chapter Notes
  8. Chapter 2: Object-Oriented Design
    1. 2.1 Goals, Principles, and Patterns
    2. 2.2 Inheritance
    3. 2.3 Interfaces and Abstract Classes
    4. 2.4 Exceptions
    5. 2.5 Casting and Generics
    6. 2.6 Nested Classes
    7. 2.7 Exercises
    8. Chapter Notes
  9. Chapter 3: Fundamental Data Structures
    1. 3.1 Using Arrays
    2. 3.2 Singly Linked Lists
    3. 3.3 Circularly Linked Lists
    4. 3.4 Doubly Linked Lists
    5. 3.5 Equivalence Testing
    6. 3.6 Cloning Data Structures
    7. 3.7 Exercises
    8. Chapter Notes
  10. Chapter 4: Algorithm Analysis
    1. 4.1 Experimental Studies
    2. 4.2 The Seven Functions Used in This Book
    3. 4.3 Asymptotic Analysis
    4. 4.4 Simple Justification Techniques
    5. 4.5 Exercises
    6. Chapter Notes
  11. Chapter 5: Recursion
    1. 5.1 Illustrative Examples
    2. 5.2 Analyzing Recursive Algorithms
    3. 5.3 Further Examples of Recursion
    4. 5.4 Designing Recursive Algorithms
    5. 5.5 Recursion Run Amok
    6. 5.6 Eliminating Tail Recursion
    7. 5.7 Exercises
    8. Chapter Notes
  12. Chapter 6: Stacks, Queues, and Deques
    1. 6.1 Stacks
    2. 6.2 Queues
    3. 6.3 Double-Ended Queues
    4. 6.4 Exercises
    5. Chapter Notes
  13. Chapter 7: List and Iterator ADTs
    1. 7.1 The List ADT
    2. 7.2 Array Lists
    3. 7.3 Positional Lists
    4. 7.4 Iterators
    5. 7.5 The Java Collections Framework
    6. 7.6 Sorting a Positional List
    7. 7.7 Case Study: Maintaining Access Frequencies
    8. 7.8 Exercises
    9. Chapter Notes
  14. Chapter 8: Trees
    1. 8.1 General Trees
    2. 8.2 Binary Trees
    3. 8.3 Implementing Trees
    4. 8.4 Tree Traversal Algorithms
    5. 8.5 Exercises
    6. Chapter Notes
  15. Chapter 9: Priority Queues
    1. 9.1 The Priority Queue Abstract Data Type
    2. 9.2 Implementing a Priority Queue
    3. 9.3 Heaps
    4. 9.4 Sorting with a Priority Queue
    5. 9.5 Adaptable Priority Queues
    6. 9.6 Exercises
    7. Chapter Notes
  16. Chapter 10: Maps, Hash Tables, and Skip Lists
    1. 10.1 Maps
    2. 10.2 Hash Tables
    3. 10.3 Sorted Maps
    4. 10.4 Skip Lists
    5. 10.5 Sets, Multisets, and Multimaps
    6. 10.6 Exercises
    7. Chapter Notes
  17. Chapter 11: Search Trees
    1. 11.1 Binary Search Trees
    2. 11.2 Balanced Search Trees
    3. 11.3 AVL Trees
    4. 11.4 Splay Trees
    5. 11.5 (2,4) Trees
    6. 11.6 Red-Black Trees
    7. 11.7 Exercises
    8. Chapter Notes
  18. Chapter 12: Sorting and Selection
    1. 12.1 Merge-Sort
    2. 12.2 Quick-Sort
    3. 12.3 Studying Sorting through an Algorithmic Lens
    4. 12.4 Comparing Sorting Algorithms
    5. 12.5 Selection
    6. 12.6 Exercises
    7. Chapter Notes
  19. Chapter 13: Text Processing
    1. 13.1 Abundance of Digitized Text
    2. 13.2 Pattern-Matching Algorithms
    3. 13.3 Tries
    4. 13.4 Text Compression and the Greedy Method
    5. 13.5 Dynamic Programming
    6. 13.6 Exercises
    7. Chapter Notes
  20. Chapter 14: Graph Algorithms
    1. 14.1 Graphs
    2. 14.2 Data Structures for Graphs
    3. 14.3 Graph Traversals
    4. 14.4 Transitive Closure
    5. 14.5 Directed Acyclic Graphs
    6. 14.6 Shortest Paths
    7. 14.7 Minimum Spanning Trees
    8. 14.8 Exercises
    9. Chapter Notes
  21. Chapter 15: Memory Management and B-Trees
    1. 15.1 Memory Management
    2. 15.2 Memory Hierarchies and Caching
    3. 15.3 External Searching and B-Trees
    4. 15.4 External-Memory Sorting
    5. 15.5 Exercises
    6. Chapter Notes
  22. Bibliography
  23. Index