Data Structures (3^rd Ed.) Abstraction and Design Using Java

Preface iii

Chapter 1 Object–Oriented Programming and Class Hierarchies 1

1.1 ADTs, Interfaces, and the Java API 2

Interfaces 3

The implements Clause 6

Declaring a Variable of an Interface Type 7

Exercises for Section 1.1 7

1.2 Introduction to Object–Oriented Programming 8

A Superclass and Subclass Example 9

Use of this 10

Initializing Data Fields in a Subclass 11

The No–Parameter Constructor 12

Protected Visibility for Superclass Data Fields 13

Is–a Versus Has–a Relationships 13

Exercises for Section 1.2 14

1.3 Method Overriding, Method Overloading, and Polymorphism 14

Method Overriding 14

Method Overloading 16

Polymorphism 19

Methods with Class Parameters 20

Exercises for Section 1.3 20

1.4 Abstract Classes 21

Referencing Actual Objects 24

Initializing Data Fields in an Abstract Class 24

Abstract Class Number and the Java Wrapper Classes 24

Summary of Features of Actual Classes, Abstract Classes, and Interfaces 25

Implementing Multiple Interfaces 26

Extending an Interface 26

Exercises for Section 1.4 27

1.5 Class Object and Casting 27

The Method to String 28

Operations Determined by Type of Reference Variable 28

Casting in a Class Hierarchy 29

Using instance of to Guard a Casting Operation 31

The Class Class 33

Exercises for Section 1.5 33

1.6 A Java Inheritance Example—The Exception Class Hierarchy 34

Division by Zero 34

Array Index Out of Bounds 35

Null Pointer 35

The Exception Class Hierarchy 36

The Class Throwable 36

Checked and Unchecked Exceptions 37

Handling Exceptions to Recover from Errors 39

Using try–catch to Recover from an Error 40

Throwing an Exception When Recovery Is Not Obvious 41

Exercises for Section 1.6 42

1.7 Packages and Visibility 42

Packages 42

The No–Package–Declared Environment 43

Package Visibility 43

Visibility Supports Encapsulation 44

Exercises for Section 1.7 45

1.8 A Shape Class Hierarchy 46

Case Study: Processing Geometric Figures 46

Exercises for Section 1.8 52

Chapter Review, Exercises, and Programming Projects 52

Chapter 2 Lists and the Collections Framework 61

2.1 The List Interface and ArrayList Class 62

The ArrayList Class 63

Generic Collections 66

Specification of the ArrayList Class 68

Exercises for Section 2.1 69

2.2 Applications of ArrayList 69

A Phone Directory Application 70

Exercises for Section 2.2 70

2.3 Implementation of an ArrayList Class 71

The Constructor for Class KWArrayList<E> 72

The add(E anEntry) Method 73

The add(int index, E anEntry) Method 74

The set and get Methods 75

The remove Method 75

The reallocate Method 76

Implementing KWArray List as a Collection of Objects 76

The Vector Class 77

Exercises for Section 2.3 77

2.4 Algorithm Efficiency and Big–O 77

Big–O Notation 80

Formal Definition of Big–O 81

Summary of Notation 83

Comparing Performance 84

Algorithms with Exponential and Factorial Growth Rates 86

Performance of the KWArray List Algorithms 86

Exercises for Section 2.4 87

2.5 Single–Linked Lists 88

A List Node 90

Connecting Nodes 92

A Single–Linked List Class 92

Inserting a Node in a List 93

Removing a Node 93

Traversing a Single–Linked List 95

Completing the SingleLinked List Class 95

The get and set Methods 96

The add Methods 97

Exercises for Section 2.5 98

2.6 Double–Linked Lists and Circular Lists 99

Inserting into a Double–Linked List 101

Removing from a Double–Linked List 101

A Double–Linked List Class 102

Circular Lists 102

Exercises for Section 2.6 103

2.7 The Linked List Class and the Iterator, ListIterator, and

Iterable Interfaces 104

The LinkedList Class 104

The Iterator 105

The Iterator Interface 106

The ListIterator Interface 108

Comparison of Iterator and ListIterator 110

Conversion between a ListIterator and an Index 110

The Enhanced for Statement 110

The Iterable Interface 111

Exercises for Section 2.7 112

2.8 Implementation of a Double–Linked List Class 112

Implementing the KWLinkedList Methods 113

A Class that Implements the ListIterator Interface 114

The Constructor 114

The hasNext and next Methods 115

The hasPrevious and previous Methods 116

The add Method 117

Inner Classes: Static and Nonstatic 120

Exercises for Section 2.8 121

2.9 The Collections Framework Design 121

The Collection Interface 121

Common Features of Collections 122

The AbstractCollection, AbstractList, and

AbstractSequentialList Classes 123

The List and RandomAccess Interfaces (Advanced) 124

Exercises for Section 2.9 124

2.10 Application of the LinkedList Class 125

Case Study: Maintaining an Ordered List 125

Exercises for Section 2.10 130

2.11 Testing 130

Preparations for Testing 132

Testing Tips for Program Systems 133

Developing the Test Data 133

Testing Boundary Conditions 134

Stubs 136

Preconditions and Postconditions 137

Drivers 137

Using JUnit and Debuggers 138

Testing Class OrderedList 138

Case Study: Maintaining an Ordered List (continued) 138

Exercises for Section 2.11 140

Chapter Review, Exercises, and Programming Projects 141

Chapter 3 Stacks 149

3.1 Stack Abstract Data Type 150

Specification of the Stack Abstract Data Type 150

Exercises for Section 3.1 152

3.2 Stack Applications 153

Case Study: Finding Palindromes 153

Case Study: Testing Expressions for Balanced Parentheses 156

Exercises for Section 3.2 161

3.3 Implementing a Stack 162

Implementing a Stack as an Extension of Vector 162

Implementing a Stack with a List Component 163

Implementing a Stack Using an Array 165

Implementing a Stack as a Linked Data Structure 167

Comparison of Stack Implementations 169

Exercises for Section 3.3 169

3.4 Additional Stack Applications 170

Case Study: Evaluating Postfix Expressions 171

Case Study: Converting from Infix to Postfix 176

Case Study: Converting Expressions with Parentheses 185

Tying the Case Studies Together 188

Exercises for Section 3.4 188

Chapter Review, Exercises, and Programming Projects 189

Chapter 4 Queues 195

4.1 Queue Abstract Data Type 196

A Print Queue 196

The Unsuitability of a “Print Stack” 197

A Queue of Customers 197

Using a Queue for Traversing a Multi–Branch Data Structure 197

Specification for a Queue Interface 198

Class LinkedList Implements the Queue Interface 199

Exercises for Section 4.1 199

4.2 Maintaining a Queue of Customers 200

Case Study: Maintaining a Queue 200

Exercises for Section 4.2 205

4.3 Implementing the Queue Interface 206

Using a Double–Linked List to Implement the Queue Interface 206

Using a Single–Linked List to Implement the Queue Interface 207

Using a Circular Array to Implement the Queue Interface 209

Comparing the Three Implementations 216

Exercises for Section 4.3 217

4.4 The Deque Interface 217

Classes that Implement Deque 217

Using a Deque as a Queue 219

Using a Deque as a Stack 219

Exercises for Section 4.4 220

4.5 Simulating Waiting Lines Using Queues 221

Case Study: Simulate a Strategy for Serving Airline Passengers 221

Exercises for Section 4.5 236

Chapter Review, Exercises, and Programming Projects 237

Chapter 5 Recursion 243

5.1 Recursive Thinking 244

Steps to Design a Recursive Algorithm 246

Proving that a Recursive Method Is Correct 248

Tracing a Recursive Method 249

The Run–Time Stack and Activation Frames 249

Exercises for Section 5.1 251

5.2 Recursive Definitions of Mathematical Formulas 252

Recursion versus Iteration 255

Efficiency of Recursion 256

Exercises for Section 5.2 259

5.3 Recursive Array Search 259

Design of a Recursive Linear Search Algorithm 260

Implementation of Linear Search 260

Design of a Binary Search Algorithm 262

Efficiency of Binary Search 262

The Comparable Interface 263

Implementation of Binary Search 264

Testing Binary Search 265

Method Arrays.binarySearch 265

Exercises for Section 5.3 267

5.4 Recursive Data Structures 267

Recursive Definition of a Linked List 267

Class LinkedListRec 268

Removing a List Node 271

Exercises for Section 5.4 272

5.5 Problem Solving with Recursion 273

Case Study: Towers of Hanoi 273

Case Study: Counting Cells in a Blob 278

Exercises for Section 5.5 283

5.6 Backtracking 283

Case Study: Finding a Path through a Maze 284

Exercises for Section 5.6 288

Chapter Review, Exercises, and Programming Projects 289

Chapter 6 Trees 295

6.1 Tree Terminology and Applications 297

Tree Terminology 297

Binary Trees 298

Some Types of Binary Trees 298

Full, Perfect, and Complete Binary Trees 301

General Trees 301

Exercises for Section 6.1 303

6.2 Tree Traversals 304

Visualizing Tree Traversals 304

Traversals of Binary Search Trees and Expression Trees 305

Exercises for Section 6.2 306

6.3 Implementing a BinaryTree Class 307

The Node<E> Class 307

The BinaryTree<E> Class 308

Exercises for Section 6.3 314

6.4 Binary Search Trees 315

Overview of a Binary Search Tree 315

Performance 316

Interface SearchTree 317

The BinarySearchTree Class 317

Insertion into a Binary Search Tree 319

Removal from a Binary Search Tree 323

Testing a Binary Search Tree 328

Case Study: Writing an Index for a Term Paper 329

Exercises for Section 6.4 331

6.5 Heaps and Priority Queues 332

Inserting an Item into a Heap 333

Removing an Item from a Heap 333

Implementing a Heap 334

Priority Queues 337

The PriorityQueue Class 338

Using a Heap as the Basis of a Priority Queue 338

The Other Methods 341

Using a Comparator 342

The compare Method 342

Exercises for Section 6.5 344

6.6 Huffman Trees 345

Case Study: Building a Custom Huffman Tree 346

Exercises for Section 6.6 353

Chapter Review, Exercises, and Programming Projects 354

Chapter 7 Sets and Maps 361

7.1 Sets and the Set Interface 362

The Set Abstraction 363

The Set Interface and Methods 364

Comparison of Lists and Sets 366

Exercises for Section 7.1 366

7.2 Maps and the Map Interface 367

The Map Hierarchy 368

The Map Interface 369

Exercises for Section 7.2 371

7.3 Hash Tables 372

Hash Codes and Index Calculation 372

Methods for Generating Hash Codes 373

Open Addressing 374

Table Wraparound and Search Termination 375

Traversing a Hash Table 376

Deleting an Item Using Open Addressing 377

Reducing Collisions by Expanding the Table Size 377

Reducing Collisions Using Quadratic Probing 378

Problems with Quadratic Probing 378

Chaining 379

Performance of Hash Tables 380

Exercises for Section 7.3 382

7.4 Implementing the Hash Table 384

Interface KWHashMap 384

Class Entry 384

Class HashtableOpen 386

Class HashtableChain 391

Testing the Hash Table Implementations 394

Exercises for Section 7.4 395

7.5 Implementation Considerations for Maps and Sets 396

Methods hashCode and equals 396

Implementing HashSetOpen 396

Writing HashSetOpen as an Adapter Class 397

Implementing the Java Map and Set Interfaces 398

Nested Interface Map.Entry 398

Creating a Set View of a Map 399

Method entrySet and Classes EntrySet and SetIterator 399

Classes TreeMap and TreeSet 400

Exercises for Section 7.5 401

7.6 Additional Applications of Maps 401

Case Study: Implementing a Cell Phone Contact List 401

Case Study: Completing the Huffman Coding Problem 404

Exercises for Section 7.6 408

7.7 Navigable Sets and Maps 408

Application of a NavigableMap 410

Exercises for Section 7.7 412

Chapter Review, Exercises, and Programming Projects 413

Chapter 8 Sorting 419

8.1 Using Java Sorting Methods 420

Exercises for Section 8.1 424

8.2 Selection Sort 425

Analysis of Selection Sort 426

Code for Selection Sort 426

Exercises for Section 8.2 427

8.3 Bubble Sort 428

Analysis of Bubble Sort 429

Code for Bubble Sort 430

Exercises for Section 8.3 431

8.4 Insertion Sort 431

Analysis of Insertion Sort 433

Code for Insertion Sort 434

Exercises for Section 8.4 435

8.5 Comparison of Quadratic Sorts 435

Comparisons versus Exchanges 436

Exercises for Section 8.5 436

8.6 Shell Sort: A Better Insertion Sort 437

Analysis of Shell Sort 438

Code for Shell Sort 439

Exercises for Section 8.6 440

8.7 Merge Sort 441

Analysis of Merge 442

Code for Merge 442

Algorithm for Merge Sort 443

Trace of Merge Sort Algorithm 444

Analysis of Merge Sort 444

Code for Merge Sort 445

Exercises for Section 8.7 446

8.8 Heapsort 446

First Version of a Heapsort Algorithm 446

Revising the Heapsort Algorithm 447

Algorithm to Build a Heap 449

Analysis of Revised Heapsort Algorithm 449

Code for Heapsort 449

Exercises for Section 8.8 451

8.9 Quicksort 451

Algorithm for Quicksort 452

Analysis of Quicksort 452

Code for Quicksort 453

Algorithm for Partitioning 454

Code for partition 455

A Revised Partition Algorithm 457

Code for Revised partition Method 458

Exercises for Section 8.9 460

8.10 Testing the Sort Algorithms 460

Exercises for Section 8.10 462

8.11 The Dutch National Flag Problem (Optional Topic) 462

Case Study: The Problem of the Dutch National Flag 462

Exercises for Section 8.11 466

Chapter Review, Exercises, and Programming Projects 466

Chapter 9 Self–Balancing Search Trees 471

9.1 Tree Balance and Rotation 472

Why Balance Is Important 472

Rotation 473

Algorithm for Rotation 473

Implementing Rotation 475

Exercises for Section 9.1 476

9.2 AVL Trees 477

Balancing a Left–Left Tree 477

Balancing a Left–Right Tree 478

Four Kinds of Critically Unbalanced Trees 479

Implementing an AVL Tree 481

Inserting into an AVL Tree 483

Removal from an AVL Tree 489

Performance of the AVL Tree 489

Exercises for Section 9.2 489

9.3 Red–Black Trees 490

Insertion into a Red–Black Tree 491

Removal from a Red–Black Tree 501

Performance of a Red–Black Tree 502

The TreeMap and TreeSet Classes 502

Exercises for Section 9.3 502

9.4 2–3 Trees 503

Searching a 2–3 Tree 503

Inserting an Item into a 2–3 Tree 504

Analysis of 2–3 Trees and Comparison with Balanced Binary Trees 508

Removal from a 2–3 Tree 508

Exercises for Section 9.4 510

9.5 B–Trees and 2–3–4 Trees 510

B–Trees 510

Implementing the B–Tree 512

Code for the insert Method 514

The insert Into Node Method 515

The split Node Method 516

Removal from a B–Tree 518

B+ Trees 520

2–3–4 Trees 520

Relating 2–3–4 Trees to Red–Black Trees 522

Exercises for Section 9.5 524

9.6 Skip–Lists 525

Skip–List Structure 525

Searching a Skip–List 526

Performance of a Skip–List Search 526

Inserting into a Skip–List 526

Increasing the Height of a Skip–List 527

Implementing a Skip–List 527

Searching a Skip–List 528

Insertion 529

Determining the Size of the Inserted Node 530

Completing the Insertion Process 530

Performance of a Skip–List 530

Exercises for Section 9.6 531

Chapter Review, Exercises, and Programming Projects 531

Chapter 10 Graphs 541

10.1 Graph Terminology 542

Visual Representation of Graphs 542

Directed and Undirected Graphs 543

Paths and Cycles 544

Relationship between Graphs and Trees 546

Graph Applications 546

Exercises for Section 10.1 547

10.2 The Graph ADT and Edge Class 547

Exercises for Section 10.2 549

10.3 Implementing the Graph ADT 550

Adjacency List 550

Adjacency Matrix 550

Overview of the Hierarchy 552

Class AbstractGraph 552

The ListGraph Class 555

The MatrixGraph Class 558

Comparing Implementations 558

Exercises for Section 10.3 559

10.4 Traversals of Graphs 560

Breadth–First Search 560

Depth–First Search 565

Exercises for Section 10.4 572

10.5 Applications of Graph Traversals 573

Case Study: Shortest Path through a Maze 573

Case Study: Topological Sort of a Graph 577

Exercises for Section 10.5 580

10.6 Algorithms Using Weighted Graphs 580

Finding the Shortest Path from a Vertex to All Other Vertices 580

Minimum Spanning Trees 584

Exercises for Section 10.6 588

Chapter Review, Exercises, and Programming Projects 589

Appendix A Introduction to Java 597

A.1 The Java Environment and Classes 598

The Java Virtual Machine 599

The Java Compiler 599

Classes and Objects 599

The Java API 600

The import Statement 600

Method main 600

Execution of a Java Program 601

Exercises for Section A.1 602

A.2 Primitive Data Types and Reference Variables 602

Primitive Data Types 602

Primitive–Type Variables 603

Primitive–Type Constants 604

Operators 604

Postfix and Prefix Increment 604

Type Compatibility and Conversion 606

Referencing Objects 607

Creating Objects 607

Exercises for Section A.2 608

A.3 Java Control Statements 608

Sequence and Compound Statements 608

Selection and Repetition Control 609

Nested if Statements 610

The switch Statement 612

Exercises for Section A.3 613

A.4 Methods and Class Math 613

The Instance Methods println and print 613

Call–by–Value Arguments 614

The Class Math 615

Escape Sequences 616

Exercises for Section A.4 617

A.5 The String, StringBuilder, and StringBuffer Classes 617

The String Class 617

Strings Are Immutable 620

The Garbage Collector 620

Comparing Objects 621

The String.format Method 622

The Formatter Class 623

The String.split Method 624

Introduction to Regular Expressions 624

Matching One of a Group of Characters 624

Qualifiers 624

Defined Character Groups 625

Unicode Character Class Support 626

The StringBuilder and StringBuffer Classes 627

Exercises for Section A.5 628

A.6 Wrapper Classes for Primitive Types 629

Exercises for Section A.6 630

A.7 Defining Your Own Classes 631

Private Data Fields, Public Methods 635

Constructors 635

The No–Parameter Constructor 636

Modifier and Accessor Methods 636

Use of this in a Method 637

The Method to String 637

The Method equals 637

Declaring Local Variables in Class Person 639

An Application that Uses Class Person 639

Objects as Arguments 640

Classes as Components of Other Classes 642

Java Documentation Style for Classes and Methods 642

Exercises for Section A.7 644

A.8 Arrays 645

Data Field length 647

Method Arrays.copyOf 648

Method System.arrayCopy 648

Array Data Fields 649

Array Results and Arguments 651

Arrays of Arrays 651

Exercises for Section A.8 653

A.9 Input/Output Using Class JOptionPane 655

Converting Numeric Strings to Numbers 656

GUI Menus Using Method showOptionDialog 657

Exercises for Section A.9 657

A.10 Input/Output Using Streams and the Scanner Class 658

Input Streams 658

Console Input 658

Output Streams 659

Passing Arguments to Method main 659

Closing Streams 659

Exceptions 660

A Complete File–Processing Application 660

The Scanner 662

Tokenized Input 664

Extracting Tokens Using Scanner.findInLine 664

Exercises for Section A.10 665

A.11 Catching Exceptions 665

Catching and Handling Exceptions 666

Exercises for Section A.11 672

A.12 Throwing Exceptions 672

The throws Clause 672

The throw Statement 674

Exercises for Section A.12 678

Appendix Review, Exercises, and Programming Projects 679

Appendix B Overview of UML 685

B.1 The Class Diagram 686

Representing Classes and Interfaces 686

Generalization 689

Inner or Nested Classes 690

Association 690

Aggregation and Composition 691

Generic Classes 692

B.2 Sequence Diagrams 692

Time Axis 692

Objects 693

Life Lines 694

Activation Bars 694

Messages 694

Use of Notes 694

Appendix C Event–Oriented Programming 695

C.1 Elements of an Event–Oriented Application 696

Components and Events 697

Event Listeners 698

The ActionListener Interface 698

Registering an Event Listener 699

Creating a User Interface 700

Exercises for Section C.1 703

C.2 Overview of the AWT and Swing Hierarchy 704

Example and Overview: TwoCircles 705

JFrame 709

JPanel 710

Graphics 711

Graphics Coordinates 712

Exercises for Section C.2 712

C.3 Layout Managers 712

Border Layout 713

Flow Layout 715

Box Layout 716

Grid Layout 717

Combining Layouts 718

Exercises for Section C.3 719

C.4 Components for Data Entry 719

Check Box 720

Radio Button 721

Combo Box 723

Text Field 724

Label 726

Text Area 726

Exercises for Section C.4 726

C.5 Using Data Entry Components in a GUI 727

Case Study: Liquid Volume Converter 727

Limiting the Number of Significant Digits 732

Formatting Currency for Different Locales 733

Exercises for Section C.5 734

C.6 Menus and Toolbars 735

The Classes JMenuItem, JMenu, and JMenuBar 735

Icons 737

Toolbars 737

Case Study: A Drawing Application 739

Exercises for Section C.6 747

C.7 Processing Mouse Events 747

MouseAdapter and MouseMotionAdapter 748

Case Study: A Drawing Application (continued) 749

Exercises for Section C.7 757

Appendix Review, Exercises, and Programming Projects 757

Appendix D Testing and Debugging 763

D.1 Testing Using the JUnit Framework 764

D.2 Debugging a Program 767

Using a Debugger 769

D.3 Visualizing Data Structures 772

Glossary 775

Index 785