Data Structures and Other Objects Using Java

CHAPTER 1 THE PHASES OF SOFTWARE DEVELOPMENT 1
1.1 Specification, Design, Implementation 4
Design Technique: Decomposing the Problem 5
How to Write a Specification for a Java Method 6
Pitfall: Throw an Exception to Indicate a Failed Precondition 9
Temperature Conversion: Implementation 10
Programming Tip: Use Javadoc to Write Specifications 13
Programming Tip: Use Final Variables to Improve Clarity 13
Programming Tip: Make Exception Messages Informative 14
Programming Tip: Format Output with System.out.printf 14
Self-Test Exercises for Section 1.1 15
1.2 Running Time Analysis 16
The Stair-Counting Problem 16
Big-O Notation 21
Time Analysis of Java Methods 23
Worst-Case, Average-Case, and Best-Case Analyses 25
Self-Test Exercises for Section 1.2 26
1.3 Testing and Debugging 26
Choosing Test Data 27
Boundary Values 27
Fully Exercising Code 28
Pitfall: Avoid Impulsive Changes 29
Using a Debugger 29
Assert Statements 29
Turning Assert Statements On and Off 30
Programming Tip: Use a Separate Method for Complex Assertions 32
Pitfall: Avoid Using Assertions to Check Preconditions 34
Static Checking Tools 34
Self-Test Exercises for Section 1.3 34
Chapter Summary 35
Solutions to Self-Test Exercises 36
CHAPTER 2 JAVA CLASSES AND INFORMATION HIDING 38
2.1 Classes and Their Members 40
Defining a New Class 41
Instance Variables 41
Constructors 42
No-Arguments Constructors 43
Methods 43
Accessor Methods 44
Programming Tip: Four Reasons to Implement Accessor Methods 44
Pitfall: Division Throws Away the Fractional Part 45
Programming Tip: Use the Boolean Type for True or False Values 46
Modification Methods 46
Pitfall: Potential Arithmetic Overflows 48
Complete Definition of Throttle.java 48
Methods May Activate Other Methods 51
Self-Test Exercises for Section 2.1 51
2.2 Using a Class 52
Creating and Using Objects 52
A Program with Several Throttle Objects 53
Null References 54
NullPointerException 55
Assignment Statements with Reference Variables 55
Clones 58
Testing for Equality 58
Terminology Controversy: "The Throttle That t Refers To" 59
Self-Test Exercises for Section 2.2 59
2.3 Packages 60
Declaring a Package 60
The Import Statement to Use a Package 63
The JCL Packages 63
More about Public, Private, and Package Access 63
Self-Test Exercises for Section 2.3 65
2.4 Parameters, Equals Methods, and Clones 65
The Location Class 66
Static Methods 72
Parameters That Are Objects 73
Methods May Access Private Instance Variables of Objects in Their Own Class 74
The Return Value of a Method May Be an Object 75
Programming Tip: How to Choose the Names of Methods 76
Java's Object Type 77
Using and Implementing an Equals Method 77
Pitfall: ClassCastException 80
Every Class Has an Equals Method 80
Using and Implementing a Clone Method 81
Pitfall: Older Java Code Requires a Typecast for Clones 81
Programming Tip: Always Use super.clone for Your Clone Method 85
Programming Tip: When to Throw a Runtime Exception 85
A Demonstration Program for the Location Class 85
What Happens When a Parameter Is Changed Within a Method? 86
Self-Test Exercises for Section 2.4 89
2.5 The Java Class Libraries 90
Chapter Summary 92
Solutions to Self-Test Exercises 93
Programming Projects 95
CHAPTER 3 COLLECTION CLASSES 103
3.1 A Review of Java Arrays 104
Pitfall: Exceptions That Arise from Arrays 106
The Length of an Array 106
Assignment Statements with Arrays 106
Clones of Arrays 107
The Arrays Utility Class 108
Array Parameters 110
Programming Tip: Enhanced For-Loops for Arrays 111
Self-Test Exercises for Section 3.1 112
3.2 An ADT for a Bag of Integers 113
The Bag ADT-Specification 114
OutOfMemoryError and Other Limitations for Collection Classes 118
The IntArrayBag Class-Specification 118
The IntArrayBag Class-Demonstration Program 122
The IntArrayBag Class-Design 125
The Invariant of an ADT 126
The IntArrayBag ADT-Implementation 127
Programming Tip: Cloning a Class That Contains an Array 136
The Bag ADT-Putting the Pieces Together 137
Programming Tip: Document the ADT Invariant in the Implementation File 141
The Bag ADT-Testing 141
Pitfall: An Object Can Be an Argument to Its Own Method 142
The Bag ADT-Analysis 142
Self-Test Exercises for Section 3.2 144
3.3 Programming Project: The Sequence ADT 145
The Sequence ADT-Specification 146
The Sequence ADT-Documentation 150
The Sequence ADT-Design 150
The Sequence ADT-Pseudocode for the Implementation 156
Self-Test Exercises for Section 3.3 158
3.4 Programming Project: The Polynomial 159
Self-Test Exercises for Section 3.4 162
3.5 The Java HashSet and Iterators 162
The HashSet Class 162
Some of the HashSet Members 162
Iterators 163
Pitfall: Do Not Access an Iterator's next Item When hasNext Is False 164
Pitfall: Changing a Container Object Can Invalidate Its Iterator 164
Invalid Iterators 164
Self-Test Exercises for Section 3.5 165
Chapter Summary 165
Solutions to Self-Test Exercises 166
Programming Projects 169
CHAPTER 4 LINKED LISTS 175
4.1 Fundamentals of Linked Lists 176
Declaring a Class for Nodes 177
Head Nodes, Tail Nodes 177
The Null Reference 178
Pitfall: NullPointerExceptions with Linked Lists 179
Self-Test Exercises for Section 4.1 179
4.2 Methods for Manipulating Nodes 179
Constructor for the Node Class 180
Getting and Setting the Data and Link of a Node 180
Public Versus Private Instance Variables 181
Adding a New Node at the Head of a Linked List 182
Removing a Node from the Head of a Linked List 183
Adding a New Node That Is Not at the Head 185
Removing a Node That Is Not at the Head 188
Pitfall: NullPointerExceptions with removeNodeAfter 191
Self-Test Exercises for Section 4.2 191
4.3 Manipulating an Entire Linked List 192
Computing the Length of a Linked List 193
Programming Tip: How to Traverse a Linked List 196
Pitfall: Forgetting to Test the Empty List 197
Searching for an Element in a Linked List 197
Finding a Node by Its Position in a Linked List 198
Copying a Linked List 200
A Second Copy Method, Returning Both Head and Tail References 204
Programming Tip: A Method Can Return an Array 205
Copying Part of a Linked List 206
Using Linked Lists 207
Self-Test Exercises for Section 4.3 214
4.4 The Bag ADT with a Linked List 215
Our Second Bag-Specification 215
The grab Method 219
Our Second Bag-Class Declaration 219
The Second Bag-Implementation 220
Programming Tip: Cloning a Class That Contains a Linked List 223
Programming Tip: How to Choose between Different Approaches 225
The Second Bag-Putting the Pieces Together 229
Self-Test Exercises for Section 4.4 232
4.5 Programming Project: The Sequence ADT with a Linked List 232
The Revised Sequence ADT-Design Suggestions 232
The Revised Sequence ADT-Clone Method 235
Self-Test Exercises for Section 4.5 238
4.6 Beyond Simple Linked Lists 239
Arrays Versus Linked Lists and Doubly Linked Lists 239
Dummy Nodes 240
Java's List Classes 241
ListIterators 242
Making the Decision 243
Self-Test Exercises for Section 4.6 244
Chapter Summary 244
Solutions to Self-Test Exercises 245
Programming Projects 248
CHAPTER 5 GENERIC PROGRAMMING 251
5.1 Java's Object Type and Wrapper Classes 252
Widening Conversions 253
Narrowing Conversions 254
Wrapper Classes 256
Autoboxing and Auto-Unboxing Conversions 256
Advantages and Disadvantages of Wrapper Objects 257
Self-Test Exercises for Section 5.1 257
5.2 Object Methods and Generic Methods 258
Object Methods 259
Generic Methods 259
Pitfall: Generic Method Restrictions 260
Self-Test Exercises for Section 5.2 261
5.3 Generic Classes 262
Writing a Generic Class 262
Using a Generic Class 262
Pitfall: Generic Class Restrictions 263
Details for Implementing a Generic Class 263
Creating an Array to Hold Elements of the Unknown Type 263
Retrieving E Objects from the Array 264
Warnings in Generic Code 264
Programming Tip: Suppressing Unchecked Warnings 265
Using ArrayBag as the Type of a Parameter or Return Value 266
Counting the Occurrences of an Object 266
The Collection Is Really a Collection of References to Objects 267
Set Unused References to Null 269
Steps for Converting a Collection Class to a Generic Class 269
Deep Clones for Collection Classes 271
Using the Bag of Objects 279
Details of the Story-Writing Program 282
Self-Test Exercises for Section 5.3 282
5.4 Generic Nodes 283
Nodes That Contain Object Data 283
Pitfall: Misuse of the equals Method 283
Other Collections That Use Linked Lists 285
Self-Test Exercises for Section 5.4 285
5.5 Interfaces and Iterators 286
Interfaces 286
How to Write a Class That Implements an Interface 287
Generic Interfaces and the Iterable Interface 287
How to Write a Generic Class That Implements a Generic Interface 288
The Lister Class 289
Pitfall: Don't Change a List While an Iterator Is Being Used 291
The Comparable Generic Interface 292
Parameters That Use Interfaces 293
Using instanceof to Test Whether a Class Implements an Interface 294
The Cloneable Interface 295
Self-Test Exercises for Section 5.5 295
5.6 A Generic Bag Class That Implements the Iterable Interface (Optional Section) 296
Programming Tip: Enhanced For-Loops for the Iterable Interface 297
Implementing a Bag of Objects Using a Linked List and an Iterator 298
Programming Tip: External Iterators Versus Internal Iterators 298
Summary of the Four Bag Implementations 299
Self-Test Exercises for Section 5.6 299
5.7 The Java Collection Interface and Map Interface (Optional Section) 300
The Collection Interface 300
The Map Interface and the TreeMap Class 300
The TreeMap Class 302
The Word Counting Program 305
Self-Test Exercises for Section 5.7 306
Chapter Summary 309
Solutions to Self-Test Exercises 310
Programming Projects 312
CHAPTER 6 STACKS 315
6.1 Introduction to Stacks 316
The Stack Class-Specification 317
We Will Implement a Generic Stack 319
Programming Example: Reversing a Word 319
Self-Test Exercises for Section 6.1 320
6.2 Stack Applications 320
Programming Example: Balanced Parentheses 320
Programming Tip: The Switch Statement 324
Evaluating Arithmetic Expressions 325
Evaluating Arithmetic Expressions-Specification 325
Evaluating Arithmetic Expressions-Design 325
Implementation of the Evaluate Method 329
Evaluating Arithmetic Expressions-Testing and Analysis 333
Evaluating Arithmetic Expressions-Enhancements 334
Self-Test Exercises for Section 6.2 334
6.3 Implementations of the Stack ADT 335
Array Implementation of a Stack 335
Linked List Implementation of a Stack 341
Self-Test Exercises for Section 6.3 344
6.4 More Complex Stack Applications 345
Evaluating Postfix Expressions 345
Translating Infix to Postfix Notation 348
Using Precedence Rules in the Infix Expression 350
Correctness of the Conversion from Infix to Postfix 353
Self-Test Exercises for Section 6.4 354
Chapter Summary 354
Solutions to Self-Test Exercises 355
Programming Projects 356
CHAPTER 7 QUEUES 360
7.1 Introduction to Queues 361
The Queue Class 362
Uses for Queues 364
Self-Test Exercises for Section 7.1 365
7.2 Queue Applications 365
Java Queues 365
Programming Example: Palindromes 366
Programming Example: Car Wash Simulation 369
Car Wash Simulation-Specification 369
Car Wash Simulation-Design 369
Car Wash Simulation-Implementing the Car Wash Classes 374
Car Wash Simulation-Implementing the Simulation Method 375
Self-Test Exercises for Section 7.2 375
7.3 Implementations of the Queue Class 383
Array Implementation of a Queue 383
Programming Tip: Use Helper Methods to Improve Clarity 386
Linked List Implementation of a Queue 393
Pitfall: Forgetting Which End Is Which 398
Self-Test Exercises for Section 7.3 398
7.4 Deques and Priority Queues (Optional Section) 399
Double-Ended Queues 399
Priority Queues 400
Priority Queue ADT-Specification 400
Priority Queue Class-An Implementation That Uses an Ordinary Queue 402
Priority Queue ADT-A Direct Implementation 403
Java's Priority Queue 403
Self-Test Exercises for Section 7.4 404
Chapter Summary 404
Solutions to Self-Test Exercises 404
Programming Projects 406
CHAPTER 8 RECURSIVE THINKING 409
8.1 Recursive Methods 410
Tracing Recursive Calls 413
Programming Example: An Extension of writeVertical 413
A Closer Look at Recursion 415
General Form of a Successful Recursive Method 418
Self-Test Exercises for Section 8.1 419
8.2 Studies of Recursion: Fractals and Mazes 420
Programming Example: Generating Random Fractals 420
A Method for Generating Random Fractals-Specification 421
The Stopping Case for Generating a Random Fractal 426
Putting the Random Fractal Method in an Applet 426
Programming Example: Traversing a Maze 429
Traversing a Maze-Specification 429
Traversing a Maze-Design 432
Traversing a Maze-Implementation 433
The Recursive Pattern of Exhaustive Search with Backtracking 435
Programming Example: The Teddy Bear Game 437
Self-Test Exercises for Section 8.2 437
8.3 Reasoning about Recursion 439
How to Ensure That There Is No Infinite Recursion in the General Case 442
Inductive Reasoning about the Correctness of a Recursive Method 444
Self-Test Exercises for Section 8.3 445
Chapter Summary 446
Solutions to Self-Test Exercises 446
Programming Projects 448
CHAPTER 9 TREES 453
9.1 Introduction to Trees 454
Binary Trees 454
Binary Taxonomy Trees 457
More Than Two Children 458
Self-Test Exercises for Section 9.1 459
9.2 Tree Representations 459
Array Representation of Complete Binary Trees 459
Representing a Binary Tree with a Generic Class for Nodes 462
Self-Test Exercises for Section 9.2 464
9.3 A Class for Binary Tree Nodes 464
Programming Example: Animal Guessing 473
Animal-Guessing Program-Design and Implementation 475
Animal-Guessing Program-Improvements 481
Self-Test Exercises for Section 9.3 481
9.4 Tree Traversals 484
Traversals of Binary Trees 484
Printing a Tree with an Indentation to Show the Depths 488
BTNode, IntBTNode, and Other Classes 497
Self-Test Exercises for Section 9.4 497
9.5 Binary Search Trees 498
The Binary Search Tree Storage Rules 498
The Binary Search Tree Bag-Implementation of Some Simple Methods 503
Counting the Occurrences of an Element in a Binary Search Tree 504
Adding a New Element to a Binary Search Tree 505
Removing an Element from a Binary Search Tree 506
The addAll, addMany, and union Methods 510
Pitfall: Violating the addTree Precondition 511
Implementing addAll 512
Time Analysis and an Internal Iterator 513
Self-Test Exercises for Section 9.5 513
Chapter Summary 514
Solutions to Self-Test Exercises 514
Programming Projects 517
CHAPTER 10 TREE PROJECTS 520
10.1 Heaps 521
The Heap Storage Rules 521
The Priority Queue Class with Heaps 522
Adding an Element to a Heap 523
Removing an Element from a Heap 524
Self-Test Exercises for Section 10.1 527
10.2 B-Trees 527
The Problem of Unbalanced Trees 527
The B-Tree Rules 528
An Example B-Tree 529
The Set Class with B-Trees 530
Searching for an Element in a B-Tree 535
Programming Tip: Private Methods to Simplify Implementations 537
Adding an Element to a B-Tree 537
The Loose Addition Operation for a B-Tree 538
A Private Method to Fix an Excess in a Child 540
Back to the add Method 541
Employing Top-Down Design 543
Removing an Element from a B-Tree 543
The Loose Removal from a B-Tree 544
A Private Method to Fix a Shortage in a Child 546
Removing the Biggest Element from a B-Tree 549
Programming Tip: Write and Test Small Pieces 549
External B-Trees 550
Self-Test Exercises for Section 10.2 551
10.3 Java Support for Trees 552
The DefaultMutableTreeNode from javax.swing.tree 552
Using the JTree Class to Display a Tree in an Applet 552
The JApplet Class 552
Programming Tip: Adding a Component to a JApplet 553
What the TreeExample Applet Displays 553
Self-Test Exercises for Section 10.3 553
10.4 Trees, Logs, and Time Analysis 558
Time Analysis for Binary Search Trees 559
Time Analysis for Heaps 559
Logarithms 562
Logarithmic Algorithms 563
Self-Test Exercises for Section 10.4 563
Chapter Summary 563
Solutions to Self-Test Exercises 564
Programming Projects 566
CHAPTER 11 SEARCHING 567
11.1 Serial Search and Binary Search 568
Serial Search 568
Serial Search-Analysis 568
Binary Search 571
Binary Search-Design 572
Pitfall: Common Indexing Errors in Binary Search Implementations 574
Binary Search-Analysis 574
Java's Binary Search Methods 579
Self-Test Exercises for Section 11.1 581
11.2 Open-Address Hashing 581
Introduction to Hashing 581
Noninteger Keys and Java's hashCode Method 583
Pitfall: Classes Often Need a New hashCode Method 584
The Table ADT-Specification 584
The Table ADT-Design 587
The Table ADT-Implementation 589
A Practical Illustration of Open-Address Hashing 594
Choosing a Hash Function to Reduce Collisions 596
Double Hashing to Reduce Clustering 596
Self-Test Exercises for Section 11.2 598
11.3 Using Java's Hashtable Class 599
11.4 Chained Hashing 600
Self-Test Exercises for Section 11.4 601
11.5 Programming Project: A Table Class Implemented with Java's Vector and LinkedList 603
A New Table Class 603
Data Structures for the New Table Class 603
Implementing the New Table Class 604
Self-Test Exercises for Section 11.6 605
11.6 Time Analysis of Hashing 605
The Load Factor of a Hash Table 607
Self-Test Exercises for Section 11.5 609
Chapter Summary 609
Solutions to Self-Test Exercises 610
Programming Projects 612
CHAPTER 12 SORTING 614
12.1 Quadratic Sorting Algorithms 615
Selectionsort-Specification 615
Selectionsort-Design 616
Selectionsort-Testing 619
Selectionsort-Analysis 620
Programming Tip: Rough Estimates Suffice for Big-O 622
Insertionsort 622
Insertionsort-Analysis 626
Self-Test Exercises for Section 12.1 629
12.2 Recursive Sorting Algorithms 629
Divide-and-Conquer Using Recursion 629
Mergesort 630
The merge Function 631
Mergesort-Analysis 638
Mergesort for Files 640
Quicksort 640
The Partition Method 643
Quicksort-Analysis 646
Quicksort-Choosing a Good Pivot Element 648
Self-Test Exercises for Section 12.2 648
12.3 An O(n log n) Algorithm Using a Heap 649
Heapsort 649
Making the Heap 656
Reheapification Downward 657
Heapsort-Analysis 658
Self-Test Exercise for Section 12.3 659
12.4 Java's Sort Methods 660
Self-Test Exercises for Section 12.4 660
12.5 Concurrent Recursive Sorting 660
Mergesort with a Threshold 661
Pitfall: The RecursiveAction Class Did Not Appear Until Java 7 662
Java's RecursiveAction Class 662
The Sorter's Constructor 663
The Sorter's compute Method 664
Programming Tip: Using InvokeAll 664
Using a ForkJoinPool to Get Concurrent Recursion Started 665
Beyond the Simple Sorter Class 668
Self-Test Exercises for Section 12.5 668
Chapter Summary 669
Solutions to Self-Test Exercises 669
Programming Projects 671
CHAPTER 13 SOFTWARE REUSE WITH EXTENDED CLASSES 675
13.1 Extended Classes 676
How to Declare an Extended Class 678
The Constructors of an Extended Class 679
Using an Extended Class 680
Descendants and Ancestors 681
Overriding Inherited Methods 682
Covariant Return Values 684
Widening Conversions for Extended Classes 684
Narrowing Conversions for Extended Classes 685
Self-Test Exercises for Section 13.1 686
13.2 Generic Type Parameters and Inheritance 686
Self-Test Exercise for Section 13.2 688
13.3 Simulation of an Ecosystem 688
Programming Tip: When to Use an Extended Class 689
Implementing Part of the Organism Object Hierarchy 689
The Organism Class 689
The Animal Class: An Extended Class with New Private Instance Variables 693
How to Provide a New Constructor for an Extended Class 693
The Other Animal Methods 695
Self-Test Exercises for the Middle of Section 13.3 696
The Herbivore Class 700
The Pond Life Simulation Program 703
Pond Life-Implementation Details 708
Using the Pond Model 708
Self-Test Exercises for the End of Section 13.3 709
13.4 Abstract Classes and a Game Class 710
Introduction to the AbstractGame Class 710
Protected Methods 716
Final Methods 716
Abstract Methods 717
An Extended Class to Play Connect Four 718
The Private Member Variables of the Connect Four Class 718
Three Connect Four Methods That Deal with the Game's Status 720
Three Connect Four Methods That Deal with Moves 721
The clone Method 722
Writing Your Own Derived Games from the AbstractGame Class 723
Self-Test Exercises for Section 13.4 724
Chapter Summary 724
Further Reading 724
Solutions to Self-Test Exercises 725
Programming Projects 727
CHAPTER 14 GRAPHS 728
14.1 Graph Definitions 729
Undirected Graphs 729
Programming Example: Undirected State Graphs 730
Directed Graphs 733
More Graph Terminology 734
Airline Routes Example 735
Self-Test Exercises for Section 14.1 736
14.2 Graph Implementations 736
Representing Graphs with an Adjacency Matrix 736
Using a Two-Dimensional Array to Store an Adjacency Matrix 737
Representing Graphs with Edge Lists 738
Representing Graphs with Edge Sets 739
Which Representation Is Best? 739
Programming Example: Labeled Graph ADT 740
The Graph Constructor and size Method 741
Methods for Manipulating Edges 742
Methods for Manipulating Vertex Labels 743
Labeled Graph ADT-Implementation 743
Self-Test Exercises for Section 14.2 749
14.3 Graph Traversals 749
Depth-First Search 750
Breadth-First Search 754
Depth-First Search-Implementation 756
Breadth-First Search-Implementation 758
Self-Test Exercises for Section 14.3 759
14.4 Path Algorithms 759
Determining Whether a Path Exists 759
Graphs with Weighted Edges 759
Shortest-Distance Algorithm 760
Shortest-Path Algorithm 770
Self-Test Exercises for Section 14.4 771
Chapter Summary 771
Solutions to Self-Test Exercises 772
Programming Projects 773
APPENDIXES
A. JAVA'S PRIMITIVE TYPES AND ARITHMETIC OVERFLOW 775
B. JAVA INPUT AND OUTPUT 778
C. THROWING AND CATCHING JAVA EXCEPTIONS 782
D. ARRAYLIST, VECTOR, HASHTABLE, AND HASHMAP CLASSES 787
E. A CLASS FOR NODES IN A LINKED LIST 791
F. A CLASS FOR A BAG OF OBJECTS 799
G. FURTHER BIG-O NOTATION 805
H. JAVADOC 807
I. APPLETS FOR INTERACTIVE TESTING 814
INDEX 815