Contents
1.1 Classes, Objects, and Applications
Handling Exceptional Situations
Exceptions and Classes: An Example
Implementation-Dependent Structures
Implementation-Independent Structures
1.5 Basic Structuring Mechanisms
1.6 Comparing Algorithms: Order of Growth Analysis
Measuring an Algorithm’s Time Efficiency
Preconditions and Postconditions
2.5 Array-Based Stack Implementations
Definitions of Stack Operations
2.6 Application: Balanced Expressions
2.7 Introduction to Linked Lists
Comparing Stack Implementations
2.9 Application: Postfix Expression Evaluator
Evaluating Postfix Expressions
Postfix Expression Evaluation Algorithm
The Java Stack Class and the Collections Framework
3.1 Recursive Definitions, Algorithms, and Programs
Iterative Solution for Factorial
Verifying Recursive Algorithms
3.3 Recursive Processing of Arrays
3.4 Recursive Processing of Linked Lists
Recursive Nature of Linked Lists
3.8 When to Use a Recursive Solution
4.3 Array-Based Queue Implementations
4.4 An Interactive Test Driver
A Test Driver for the ArrayBoundedQueue Class
4.5 Link-Based Queue Implementations
A Circular Linked Queue Design
Comparing Queue Implementations
The Java Library Collection Framework Queue/Deque
4.8 Application: Average Waiting Time
Problem Discussion and Example
4.9 Concurrency, Interference, and Synchronization
Concurrency and the Java Library Collection Classes
Assumptions for Our Collections
5.2 Array-Based Collection Implementation
5.3 Application: Vocabulary Density
5.4 Comparing Objects Revisited
5.5 Sorted Array-Based Collection Implementation
Implementing ADTs “by Copy” or “by Reference”
5.6 Link-Based Collection Implementation
Comparing Collection Implementations
The Java Collections Framework
6.3 Applications: Card Deck and Games
Application: Arranging a Card Hand
Application: How Rare Is a Pair?
6.4 Sorted Array-Based List Implementation
A Linked List as an Array of Nodes
6.6 Application: Large Integers
7.3 The Binary Search Tree Interface
7.4 The Implementation Level: Basics
7.5 Iterative Versus Recursive Method Implementations
Recursive Approach to the size Method
Iterative Approach to the size Method
7.6 The Implementation Level: Remaining Observers
The contains and get Operations
7.7 The Implementation Level: Transformers
7.8 Binary Search Tree Performance
Text Analysis Experiment Revisited
Insertion Order and Tree Shape
Balancing a Binary Search Tree
7.9 Application: Word Frequency Counter
Application-Specific Variations
An ArrayList-Based Implementation
8.3 Application: String-to-String Map
9.1 The Priority Queue Interface
9.2 Priority Queue Implementations
A Nonlinked Representation of Binary Trees
Heaps Versus Other Representations of Priority Queues
10.3 Implementations of Graphs
10.4 Application: Graph Traversals
10.5 Application: The Single-Source Shortest-Paths Problem
11 Sorting and Searching Algorithms
11.4 More Sorting Considerations
Appendix A: Java Reserved Words
Appendix B: Operator Precedence
Appendix C: Primitive Data Types