Contents
1.2.1 Creating and Using Objects
1.3 Strings, Wrappers, Arrays, and Enum Types
1.5.1 The If and Switch Statements
1.5.3 Explicit Control-Flow Statements
2.1 Goals, Principles, and Patterns
2.1.1 Object-Oriented Design Goals
2.1.2 Object-Oriented Design Principles
2.2.1 Extending the CreditCard Class
2.2.2 Polymorphism and Dynamic Dispatch
2.3 Interfaces and Abstract Classes
2.3.2 Multiple Inheritance for Interfaces
2.4.3 Java's Exception Hierarchy
3.1.1 Storing Game Entries in an Array
3.1.3 java.util Methods for Arrays and Random Numbers
3.1.4 Simple Cryptography with Character Arrays
3.1.5 Two-Dimensional Arrays and Positional Games
3.2.1 Implementing a Singly Linked List Class
3.3.2 Designing and Implementing a Circularly Linked List
3.4.1 Implementing a Doubly Linked List Class
3.5.1 Equivalence Testing with Arrays
3.5.2 Equivalence Testing with Linked Lists
4.1.1 Moving Beyond Experimental Analysis
4.2 The Seven Functions Used in This Book
4.3.3 Examples of Algorithm Analysis
4.4 Simple Justification Techniques
4.4.3 Induction and Loop Invariants
5.1.2 Drawing an English Ruler
5.2 Analyzing Recursive Algorithms
5.3 Further Examples of Recursion
5.4 Designing Recursive Algorithms
5.5.1 Maximum Recursive Depth in Java
5.6 Eliminating Tail Recursion
6.1.1 The Stack Abstract Data Type
6.1.2 A Simple Array-Based Stack Implementation
6.1.3 Implementing a Stack with a Singly Linked List
6.1.4 Reversing an Array Using a Stack
6.1.5 Matching Parentheses and HTML Tags
6.2.1 The Queue Abstract Data Type
6.2.2 Array-Based Queue Implementation
6.2.3 Implementing a Queue with a Singly Linked List
6.3.1 The Deque Abstract Data Type
6.3.3 Deques in the Java Collections Framework
7.2.2 Implementing a Dynamic Array
7.2.3 Amortized Analysis of Dynamic Arrays
7.2.4 Java's StringBuilder class
7.3.2 The Positional List Abstract Data Type
7.3.3 Doubly Linked List Implementation
7.4.1 The Iterable Interface and Java's For-Each Loop
7.5 The Java Collections Framework
7.5.2 Comparison to Our Positional List ADT
7.5.3 List-Based Algorithms in the Java Collections Framework
7.7 Case Study: Maintaining Access Frequencies
7.7.2 Using a List with the Move-to-Front Heuristic
8.1.1 Tree Definitions and Properties
8.1.2 The Tree Abstract Data Type
8.1.3 Computing Depth and Height
8.2.1 The Binary Tree Abstract Data Type
8.2.2 Properties of Binary Trees
8.3.1 Linked Structure for Binary Trees
8.3.2 Array-Based Representation of a Binary Tree
8.3.3 Linked Structure for General Trees
8.4.1 Preorder and Postorder Traversals of General Trees
8.4.2 Breadth-First Tree Traversal
8.4.3 Inorder Traversal of a Binary Tree
8.4.4 Implementing Tree Traversals in Java
8.4.5 Applications of Tree Traversals
9.1 The Priority Queue Abstract Data Type
9.2 Implementing a Priority Queue
9.2.2 Comparing Keys with Total Orders
9.2.3 The AbstractPriorityQueue Base Class
9.2.4 Implementing a Priority Queue with an Unsorted List
9.2.5 Implementing a Priority Queue with a Sorted List
9.3.2 Implementing a Priority Queue with a Heap
9.3.3 Analysis of a Heap-Based Priority Queue
9.3.4 Bottom-Up Heap Construction 
9.3.5 Using the java.util.PriorityQueue Class
9.4 Sorting with a Priority Queue
9.4.1 Selection-Sort and Insertion-Sort
9.5.2 Implementing an Adaptable Priority Queue
10 Maps, Hash Tables, and Skip Lists
10.1.2 Application: Counting Word Frequencies
10.1.3 An AbstractMap Base Class
10.1.4 A Simple Unsorted Map Implementation
10.2.2 Collision-Handling Schemes
10.2.3 Load Factors, Rehashing, and Efficiency
10.2.4 Java Hash Table Implementation
10.3.2 Two Applications of Sorted Maps
10.4.1 Search and Update Operations in a Skip List
10.4.2 Probabilistic Analysis of Skip Lists
10.5 Sets, Multisets, and Multimaps
11.1.1 Searching Within a Binary Search Tree
11.1.2 Insertions and Deletions
11.1.4 Performance of a Binary Search Tree
11.2.1 Java Framework for Balancing Search Trees
11.4.4 Amortized Analysis of Splaying
11.6.1 Red-Black Tree Operations
12.1.2 Array-Based Implementation of Merge-Sort
12.1.3 The Running Time of Merge-Sort
12.1.4 Merge-Sort and Recurrence Equations
12.1.5 Alternative Implementations of Merge-Sort
12.2.2 Additional Optimizations for Quick-Sort
12.3 Studying Sorting through an Algorithmic Lens
12.3.1 Lower Bound for Sorting
12.3.2 Linear-Time Sorting: Bucket-Sort and Radix-Sort
12.4 Comparing Sorting Algorithms
12.5.2 Randomized Quick-Select
12.5.3 Analyzing Randomized Quick-Select
13.1 Abundance of Digitized Text
13.1.1 Notations for Character Strings
13.2 Pattern-Matching Algorithms
13.2.2 The Boyer-Moore Algorithm
13.2.3 The Knuth-Morris-Pratt Algorithm
13.4 Text Compression and the Greedy Method
13.4.1 The Huffman Coding Algorithm
13.5.2 DNA and Text Sequence Alignment
14.2 Data Structures for Graphs
14.2.2 Adjacency List Structure
14.2.3 Adjacency Map Structure
14.2.4 Adjacency Matrix Structure
14.3.2 DFS Implementation and Extensions
14.7.3 Disjoint Partitions and Union-Find Structures
15 Memory Management and B-Trees
15.1.1 Stacks in the Java Virtual Machine
15.1.2 Allocating Space in the Memory Heap
15.2 Memory Hierarchies and Caching
15.3 External Searching and B-Trees
Useful Mathematical Facts available at www.wiley.com/college/goodrich