Data Structures and Other Objects Using Java

Michael Main is an Associate Professor in the Department of Computer Science at the University of Colorado - Boulder. He earned his BS, MS, and Ph.D. from Washington State University.

• 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