## Table of Contents

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