Data Structures

Preface iii

Chapter 1 Object-Oriented Programming and Class Hierarchies 1

1.1 Abstract Data Types (ADTs), Interfaces, and the Java API 2

Interfaces 2

The implements Clause 5

Declaring a Variable of an Interface Type 6

Exercises for Section 1.1 6

1.2 Introduction to OOP 7

A Superclass and Subclass Example 8

Use of this. 9

Initializing Data Fields in a Subclass 10

The No-Parameter Constructor 11

Protected Visibility for Superclass Data Fields 11

Is-a versus Has-a Relationships 12

Exercises for Section 1.2 12

1.3 Method Overriding, Method Overloading, and Polymorphism 13

Method Overriding 13

Method Overloading 15

Polymorphism 17

Methods with Class Parameters 17

Exercises for Section 1.3 18

1.4 Abstract Classes 19

Referencing Actual Objects 21

Initializing Data Fields in an Abstract Class 21

Abstract Class Number and the Java Wrapper Classes 21

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

Implementing Multiple Interfaces 23

Extending an Interface 23

Exercises for Section 1.4 24

1.5 Class Object and Casting 24

The Method toString 24

Operations Determined by Type of Reference Variable 25

Casting in a Class Hierarchy 26

Using instanceof to Guard a Casting Operation 27

The Class Class 29

Exercises for Section 1.5 29

1.6 A Java Inheritance Example—The Exception Class Hierarchy 30

Division by Zero 30

Array Index Out of Bounds 30

Null Pointer 31

The Exception Class Hierarchy 31

The Class Throwable 31

Checked and Unchecked Exceptions 32

Handling Exceptions to Recover from Errors 34

Using try−catch to Recover from an Error 35

Throwing an Exception When Recovery Is Not Obvious 35

Exercises for Section 1.6 36

1.7 Packages and Visibility 37

Packages 37

The No−Package−Declared Environment 37

Package Visibility 38

Visibility Supports Encapsulation 38

Exercises for Section 1.7 39

1.8 A Shape Class Hierarchy 40

Case Study: Processing Geometric Figures 40

Exercises for Section 1.8 46

Chapter Review 46

Java Constructs Introduced in This Chapter 47

Java API Classes Introduced in This Chapter 47

User-Defined Interfaces and Classes in This Chapter 47

Quick-Check Exercises 47

Review Questions 48

Programming Projects 49

Answers to Quick-Check Exercises 51

Chapter 2 Lists and the Collections Framework 53

2.1 Algorithm Efficiency and Big-O 54

Big-O Notation 56

Formal Definition of Big-O 57

Summary of Notation 60

Comparing Performance 60

The Power of O(log n) Algorithms 62

Algorithms with Exponential and Factorial Growth Rates 62

Exercises for Section 2.1 63

2.2 The List Interface and ArrayList Class 63

The ArrayList Class 65

Generic Collections 67

Exercises for Section 2.2 69

2.3 Applications of ArrayList 70

A Phone Directory Application 71

Exercises for Section 2.3 72

2.4 Implementation of an ArrayList Class 72

The Constructor for Class KWArrayList 73

The add(E anEntry) Method 74

The add(int index, E anEntry) Method 75

The set and get Methods 76

The remove Method 76

The reallocate Method 77

Performance of the KWArrayList Algorithms 77

Exercises for Section 2.4 77

2.5 Single-Linked Lists 78

A List Node 80

Connecting Nodes 81

A Single-Linked List Class 81

Inserting a Node in a List 82

Removing a Node 83

Completing the KWSingleLinkedList Class 84

The get and set Methods 85

The add Methods 85

Exercises for Section 2.5 86

2.6 Double-Linked Lists and Circular Lists 87

The Node Class 88

Inserting into a Double-Linked List 88

Removing from a Double-Linked List 89

A Double-Linked List Class 90

Circular Lists 90

Exercises for Section 2.6 91

2.7 The LinkedList Class and the Iterator, ListIterator, and Iterable Interfaces 91

The LinkedList Class 91

The Iterator 92

The Iterator Interface 93

The Enhanced for Loop 95

The ListIterator Interface 95

Comparison of Iterator and ListIterator 97

Conversion between a ListIterator and an Index 97

The Iterable Interface 97

Exercises for Section 2.7 98

2.8 Application of the LinkedList Class 98

Case Study: Maintaining an Ordered List 99

Exercises for Section 2.8 105

2.9 Implementation of a Double-Linked List Class 105

Implementing the KWLinkedList Methods 106

A Class That Implements the ListIterator Interface 107

The Constructor 108

The hasNext and next Methods 108

The hasPrevious and previous Methods 109

The add Method 110

Inner Classes: Static and Nonstatic 112

Exercises for Section 2.9 113

2.10 The Collections Framework Design 114

The Collection Interface 114

Common Features of Collections 114

The AbstractCollection, AbstractList, and AbstractSequentialList Classes 116

The List and RandomAccess Interfaces (Advanced) 116

Exercises for Section 2.10 117

Chapter Review 117

Java API Interfaces and Classes Introduced in This Chapter 118

User-Defined Interfaces and Classes in this Chapter 119

Quick-Check Exercises 119

Review Questions 119

Programming Projects 120

Answers to Quick-Check Exercises 122

Chapter 3 Testing and Debugging 123

3.1 Types of Testing 124

Preparations for Testing 126

Testing Tips for Program Systems 126

Exercises for Section 3.1 127

3.2 Specifying the Tests 127

Testing Boundary Conditions 127

Exercises for Section 3.2 128

3.3 Stubs and Drivers 129

Stubs 129

Preconditions and Postconditions 129

Drivers 130

Exercises for Section 3.3 130

3.4 The JUnit5 Platform 130

Exercises for Section 3.4 135

3.5 Test-Driven Development 136

Exercises for Section 3.5 140

3.6 Testing Interactive Programs in JUnit 140

ByteArrayInputStream 141

ByteArrayOutputStream 141

Exercises for Section 3.6 142

3.7 Debugging a Program 143

Using a Debugger 144

The IntelliJ and Eclipse Debuggers 144

Exercises for Section 3.7 147

Chapter Review 148

Java API Classes Introduced in This Chapter 149

User-Defined Interfaces and Classes in This Chapter 149

Quick-Check Exercises 149

Review Questions 149

Programming Projects 149

Answers to Quick-Check Exercises 151

Chapter 4 Stacks, Queues, and Deques 152

4.1 Stack Abstract Data Type 153

Specification of the Stack Abstract Data Type 153

Exercises for Section 4.1 155

4.2 Stack Applications 156

Case Study: Finding Palindromes 156

Exercises for Section 4.2 160

4.3 Implementing a Stack 160

Implementing a Stack with an ArrayList Component 160

Implementing a Stack as a Linked Data Structure 162

Comparison of Stack Implementations 163

Exercises for Section 4.3 164

4.4 Additional Stack Applications 164

Case Study: Evaluating Postfix Expressions 165

Case Study: Converting from Infix to Postfix 170

Case Study: Converting Expressions with Parentheses 178

Tying the Case Studies Together 181

Exercises for Section 4.4 181

4.5 Queue Abstract Data Type 182

A Print Queue 182

The Unsuitability of a “Print Stack” 183

A Queue of Customers 183

Using a Queue for Traversing a Multi-Branch Data Structure 183

Specification for a Queue Interface 184

Class LinkedList Implements the Queue Interface 184

Exercises for Section 4.5 185

4.6 Queue Applications 186

Case Study: Maintaining a Queue 186

Exercises for Section 4.6 191

4.7 Implementing the Queue Interface 192

Using a Double-Linked List to Implement the Queue Interface 192

Using a Single-Linked List to Implement the Queue Interface 192

Using a Circular Array to Implement the Queue Interface 194

Overview of the Design 194

Implementing ArrayQueue 196

Increasing Queue Capacity 198

Implementing Class ArrayQueue.Iter 199

Comparing the Three Implementations 200

Exercises for Section 4.7 201

4.8 The Deque Interface 201

Classes that Implement Deque 202

Using a Deque as a Queue 203

Using a Deque as a Stack 203

Exercises for Section 4.8 204

Chapter Review 205

Java API Classes Introduced in This Chapter 205

User-Defined Interfaces and Classes in This Chapter 205

Quick-Check Exercises 206

Review Questions 207

Programming Projects 208

Answers to Quick-Check Exercises 211

Chapter 5 Recursion 213

5.1 Recursive Thinking 214

Steps to Design a Recursive Algorithm 216

Proving that a Recursive Method Is Correct 218

Tracing a Recursive Method 218

The Run-Time Stack and Activation Frames 219

Exercises for Section 5.1 220

5.2 Recursive Definitions of Mathematical Formulas 221

Tail Recursion versus Iteration 225

Efficiency of Recursion 225

Exercises for Section 5.2 228

5.3 Recursive Array Search 229

Design of a Recursive Linear Search Algorithm 229

Implementation of Linear Search 230

Design of a Binary Search Algorithm 231

Efficiency of Binary Search 232

The Comparable Interface 233

Implementation of Binary Search 233

Testing Binary Search 235

Method Arrays.binarySearch 236

Exercises for Section 5.3 236

5.4 Recursive Data Structures 236

Recursive Definition of a Linked List 237

Class LinkedListRec 237

Method size 237

Method toString 238

Method replace 238

Method add 239

Removing a List Node 239

Exercises for Section 5.4 240

5.5 Problem Solving with Recursion 241

Case Study: Towers of Hanoi 241

Case Study: Counting Cells in a Blob 246

Exercises for Section 5.5 250

5.6 Backtracking 250

Case Study: Finding a Path through a Maze 251

Exercises for Section 5.6 255

Chapter Review 255

User-Defined Classes in This Chapter 256

Quick-Check Exercises 256

Review Questions 256

Programming Projects 257

Answers to Quick-Check Exercises 258

Chapter 6 Trees 259

6.1 Tree Terminology and Applications 260

Tree Terminology 260

Binary Trees 261

Some Types of Binary Trees 262

General Trees 265

Exercises for Section 6.1 266

6.2 Tree Traversals 267

Visualizing Tree Traversals 268

Traversals of Binary Search Trees and Expression Trees 268

Exercises for Section 6.2 269

6.3 Implementing a BinaryTree Class 270

The Node Class 270

The BinaryTree Class 271

The Constructors 272

The getLeftSubtree and getRightSubtree Methods 273

The isLeaf Method 274

The toString Method 274

The Recursive toString Method 274

Exercises for Section 6.3 276

6.4 Lambda Expressions and Functional Interfaces 277

Functional Interfaces 278

A General Preorder Traversal Method 281

Using preOrderTraverse 282

Exercises for Section 6.4 282

6.5 Binary Search Trees 283

Overview of a Binary Search Tree 283

Performance 284

Interface SearchTree 284

The BinarySearchTree Class 285

Implementing the find Methods 286

Insertion into a Binary Search Tree 287

Implementing the add Methods 287

Removal from a Binary Search Tree 289

Implementing the delete Methods 291

Method findLargestChild 293

Testing a Binary Search Tree 294

Case Study: Writing an Index for a Term Paper 294

Exercises for Section 6.5 297

6.6 Heaps and Priority Queues 298

Inserting an Item into a Heap 298

Removing an Item from a Heap 299

Implementing a Heap 299

Performance of the Heap 302

Priority Queues 302

The PriorityQueue Class 303

The offer Method 305

The poll Method 306

The Other Methods 307

Exercises for Section 6.6 307

6.7 Huffman Trees 308

Case Study: Building a Custom Huffman Tree 309

Exercises for Section 6.7 315

Chapter Review 316

Java API Interfaces and Classes Introduced in This Chapter 317

User-Defined Interfaces and Classes in This Chapter 317

Quick-Check Exercises 317

Review Questions 318

Programming Projects 318

Answers to Quick-Check Exercises 321

Chapter 7 Sets and Maps 322

7.1 Sets and the Set Interface 323

The Set Abstraction 323

The Set Interface and Methods 325

Using Method of to Initialize a Collection 327

Comparison of Lists and Sets 327

Exercises for Section 7.1 328

7.2 Maps and the Map Interface 329

The Map Hierarchy 330

The Map Interface 330

Creating a Map 331

Exercises for Section 7.2 333

7.3 Hash Tables 333

Hash Codes and Index Calculation 334

Methods for Generating Hash Codes 335

Open Addressing 335

Table Wraparound and Search Termination 336

Traversing a Hash Table 338

Deleting an Item Using Open Addressing 338

Reducing Collisions by Expanding the Table Size 338

Algorithm for rehashing 339

Reducing Collisions Using Quadratic Probing 339

Problems with Quadratic Probing 340

Chaining 340

Performance of Hash Tables 341

Performance of Open Addressing versus Chaining 341

Performance of Hash Tables versus Sorted Arrays and Binary Search Trees 342

Storage Requirements for Hash Tables, Sorted Arrays, and Trees 342

Storage requirements for Open Addressing and Chaining 343

Exercises for Section 7.3 343

7.4 Implementing the Hash Table 345

Interface KWHashMap 345

Class Entry 345

Class HashtableOpen 346

Class HashtableChain 351

Testing the Hash Table Implementations 354

Exercises for Section 7.4 355

7.5 Implementation Considerations for Maps and Sets 355

Methods hashCode and equals 355

Implementing HashSetOpen 356

Writing HashSetOpen as an Adapter Class 356

Implementing the Java Map and Set Interfaces 357

Interface Map.Entry and Class AbstractMap.SimpleEntry 357

Creating a Set View of a Map 358

Method entrySet and Classes EntrySet and SetIterator 358

Classes TreeMap and TreeSet 359

Exercises for Section 7.5 360

7.6 Additional Applications of Maps 360

Case Study: Implementing a Cell Phone Contact list 360

Case Study: Completing the Huffman Coding Problem 362

Encoding the Huffman Tree 366

Exercises for Section 7.6 367

7.7 Navigable Sets and Maps 367

Application of a NavigableMap 369

Exercises for Section 7.7 371

7.8 Skip-Lists 371

Skip-List Structure 372

Searching a Skip-List 372

Performance of a Skip-List Search 373

Inserting into a Skip-List 373

Increasing the Height of a Skip-List 374

Implementing a Skip-List 374

SkipList Methods for Search and Retrieval 375

Method put for Inserting into a Skip-List 376

Constants and Methods for Computing Random Level 378

Performance of a Skip-List 378

Testing Class Skip-List 379

Exercises for Section 7.8 379

Chapter Review 380

Java API Interfaces and Classes Introduced in This Chapter 381

User-Defined Interfaces and Classes in This Chapter 381

Quick-Check Exercises 381

Review Questions 382

Programming Projects 383

Answers to Quick-Check Exercises 384

Chapter 8 Sorting 385

8.1 Using Java Sorting Methods 386

Collections.sort Methods 389

Method List.sort 389

Exercises for Section 8.1 390

8.2 Selection Sort 390

Analysis of Selection Sort 391

Implementation of Selection Sort 392

Exercises for Section 8.2 393

8.3 Insertion Sort 393

Analysis of Insertion Sort 395

Implementation of Insertion Sort 395

Exercises for Section 8.3 396

8.4 Comparison of Quadratic Sorts 397

Comparisons versus Exchanges 398

Exercises for Section 8.4 398

8.5 Shell Sort: A Better Insertion Sort 398

Analysis of Shell Sort 400

Implementation of Shell Sort 400

Exercises for Section 8.5 401

8.6 Merge Sort 402

Analysis of Merge 403

Implementation of Merge 403

Design of Merge Sort 404

Trace of Merge Sort Algorithm 404

Analysis of Merge Sort 405

Implementation of Merge Sort 406

Exercises for Section 8.6 406

8.7 Timsort 407

Merging Adjacent Runs 410

Performance of Timsort 410

Implementation of Timsort 411

Exercises for Section 8.7 414

8.8 Heapsort 414

First Version of a Heapsort Algorithm 414

Analysis of Revised Heapsort Algorithm 416

Implementation of Heapsort 417

Exercises for Section 8.8 418

8.9 Quicksort 418

Algorithm for Quicksort 419

Analysis of Quicksort 420

Implementation of Quicksort 420

Algorithm for Partitioning 421

Implementation of partition 422

A Revised partition Algorithm 424

Implementation of Revised partition Method 425

Exercises for Section 8.9 426

8.10 Testing the Sort Algorithms 427

Exercises for Section 8.10 428

8.11 The Dutch National Flag Problem (Optional Topic) 428

Case Study: The Problem of the Dutch National Flag 429

Exercises for Section 8.11 431

Chapter Review 432

Java Classes Introduced in This Chapter 432

User-Defined Classes in This Chapter 432

Quick-Check Exercises 433

Review Questions 433

Programming Projects 433

Answers to Quick-Check Exercises 434

Chapter 9 Self-Balancing Search Trees 435

9.1 Tree Balance and Rotation 436

Why Balance Is Important 436

Rotation 436

Algorithm for Rotation 437

Implementing Rotation 438

Exercises for Section 9.1 440

9.2 AVL Trees 440

Balancing a Left–Left Tree 440

Balancing a Left–Right Tree 441

Four Kinds of Critically Unbalanced Trees 442

Implementing an AVL Tree 444

The AVLNode Class 445

Inserting into an AVL Tree 446

add Starter Method 447

Recursive add Method 447

Initial Algorithm for rebalanceLeft 448

The Effect of Rotations on Balance 448

Revised Algorithm for rebalanceLeft 449

Method rebalanceLeft 449

The decrementBalance Method 450

Removal from an AVL Tree 451

Performance of the AVL Tree 452

Exercises for Section 9.2 452

9.3 Red–Black Trees 453

Insertion into a Red–Black Tree 453

Implementation of Red–Black Tree Class 458

Algorithm for Red–Black Tree Insertion 458

The add Starter Method 460

The Recursive add Method 461

Removal from a Red–Black Tree 462

Performance of a Red–Black Tree 462

The TreeMap and TreeSet Classes 463

Exercises for Section 9.3 463

9.4 2–3 Trees 464

Searching a 2–3 Tree 465

Inserting an Item into a 2–3 Tree 465

Inserting into a 2-Node Leaf 465

Inserting into a 3-Node Leaf with a 2-Node Parent 466

Inserting into a 3-Node Leaf with a 3-Node Parent 466

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

Removal from a 2–3 Tree 469

Exercises for Section 9.4 470

9.5 B-Trees and 2–3–4 Trees 470

B-Trees 471

Implementing the B-Tree 472

Code for the insert Method 474

The insertIntoNode Method 475

The splitNode Method 476

Removal from a B-Tree 478

B+ Trees 479

2–3–4 Trees 480

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

Exercises for Section 9.5 482

Chapter Review 483

Java Classes Introduced in This Chapter 484

User-Defined Interfaces and Classes in This Chapter 484

Quick-Check Exercises 485

Review Questions 486

Programming Projects 486

Answers to Quick-Check Exercises 489

Chapter 10 Graphs 492

10.1 Graph Terminology 493

Visual Representation of Graphs 493

Directed and Undirected Graphs 494

Paths and Cycles 494

Relationship between Graphs and Trees 496

Graph Applications 496

Exercises for Section 10.1 497

10.2 The Graph ADT and Edge Class 497

Representing Vertices and Edges 498

Exercises for Section 10.2 499

10.3 Implementing the Graph ADT 499

Adjacency List 499

Adjacency Matrix 501

Overview of the Hierarchy 501

Declaring the Graph Interface 502

The ListGraph Class 503

Comparing Implementations 506

Exercises for Section 10.3 507

10.4 Traversals of Graphs 508

Breadth-First Search 508

Depth-First Search 513

Exercises for Section 10.4 519

10.5 Applications of Graph Traversals 519

Case Study: Shortest Path through a Maze 519

Case Study: Topological Sort of a Graph 523

Exercises for Section 10.5 526

10.6 Algorithms Using Weighted Graphs 526

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

Analysis of Dijkstra’s Algorithm 528

Minimum Spanning Trees 530

Exercises for Section 10.6 533

10.7 A Heuristic Algorithm A* to Find the Best Path 534

A* (A-Star) an Improvement of Dijkstra’s Algorithm 535

Exercises for Section 10.7 541

Chapter Review 541

User-Defined Classes and Interfaces in This Chapter 542

Quick-Check Exercises 542

Review Questions 543

Programming Projects 543

Answers to Quick-Check Exercises 545

Appendix A Introduction to Java A-1

A.1 The Java Environment and Classes A-2

The Java Virtual Machine A-3

The Java Compiler A-3

Classes and Objects A-3

The Java API A-3

The import Statement A-4

Method main A-4

Execution of a Java Program A-5

Use of jshell A-5

Exercises for Section A.1 A-6

A.2 Primitive Data Types and Reference Variables A-6

Primitive Data Types A-6

Primitive-Type Variables A-8

Primitive-Type Constants A-8

Operators A-8

Postfix and Prefix Increment A-10

Type Compatibility and Conversion A-10

Referencing Objects A-11

Creating Objects A-11

Exercises for Section A.2 A-12

A.3 Java Control Statements A-13

Sequence and Compound Statements A-13

Selection and Repetition Control A-13

Nested if Statements A-15

The switch Statement A-16

Exercises for Section A.3 A-17

A.4 Methods and Class Math A-17

The Instance Methods println and print A-18

Call-by-Value Arguments A-18

The Class Math A-18

Escape Sequences A-19

Exercises for Section A.4 A-20

A.5 The String, StringBuilder, StringBuffer, and StringJoiner Classes A-21

The String Class A-21

Strings Are Immutable A-23

The Garbage Collector A-24

Comparing Objects A-24

The String.format Method A-25

The Formatter Class A-26

The String.split Method A-27

Introduction to Regular Expressions A-27

Matching One of a Group of Characters A-27

Qualifiers A-27

Defined Character Groups A-28

Unicode Character Class Support A-29

The StringBuilder and StringBuffer Classes A-29

StringJoiner Class A-31

Exercises for Section A.5 A-32

A.6 Wrapper Classes for Primitive Types A-33

Exercises for Section A.6 A-34

A.7 Defining Your Own Classes A-35

Private Data Fields, Public Methods A-38

Constructors A-39

The No-Parameter Constructor A-39

Modifier and Accessor Methods A-40

Use of this. in a Method A-40

The Method toString A-40

The Method equals A-41

Declaring Local Variables in Class Person A-42

An Application that Uses Class Person A-42

Objects as Arguments A-43

Classes as Components of Other Classes A-44

Java Documentation Style for Classes and Methods A-44

Exercises for Section A.7 A-47

A.8 Arrays A-47

Data Field length A-49

Method Arrays.copyOf A-50

Method System.arrayCopy A-50

Array Data Fields A-51

Array Results and Arguments A-52

Arrays of Arrays A-52

Exercises for Section A.8 A-55

A.9 Enumeration Types A-56

Using Enumeration Types A-57

Assigning Values to Enumeration Types A-58

Exercises for Section A.9 A-58

A.10 I/O Using Streams, Class Scanner, and Class JOptionPane A-58

The Scanner A-59

Using a Scanner to Read from a File A-61

Exceptions A-61

Tokenized Input A-61

Extracting Tokens Using Scanner.findInLine A-62

Using a BufferedReader to Read from an Input Stream A-62

Output Streams A-62

Passing Arguments to Method main A-63

Closing Streams A-63

Try with Resources A-63

A Complete File-Processing Application A-64

Input/Output Using Class JOptionPane A-65

Converting Numeric Strings to Numbers A-66

GUI Menus Using Method showOptionDialog A-66

Exercises for Section A.10 A-67

A.11 Catching Exceptions A-67

Catching and Handling Exceptions A-68

Exercises for Section A.11 A-74

A.12 Throwing Exceptions A-74

The throws Clause A-74

The throw Statement A-75

Exercises for Section A.12 A-78

Appendix Review A-79

Java Constructs Introduced in This Appendix A-81

Java API Classes Introduced in This Appendix A-81

User‐Defined Interfaces and Classes in This Appendix A-82

Quick‐Check Exercises A-82

Review Questions A-82

Programming Projects A-83

Answer to Quick‐Check Exercises A-84

Appendix B Overview of UML A-85

B.1 The Class Diagram A-85

Representing Classes and Interfaces A-86

Generalization A-87

Inner or Nested Classes A-88

Aggregation and Composition A-88

B.2 Object Diagrams A-89

Glossary G-1

Index I-1