Data Structures and Algorithms in Java

Michael Goodrich received his Ph.D. in Computer Science from Purdue University in 1987. He is currently a professor in the Department of Computer Science at John Hopkins University, and codirector of the Johns Hopkins Center for Algorithms Engineering. He is an editor for the International Journal of Computational Geometry & Applications, Journal of Computational and System Sciences, and Journal of Graph Algorithms and Applications. Roberto Tamassia received his Ph.D. in Electrical and Computer Engineering from the University of Illinois at Urbana-Champaign in 1988. He is currently a professor in the Department of Computer Science at Brown University. He is also an editor for Computational Geometry: Theory and Applications, and the Journal of Graph Algorithms and Applications, and previously served on the editorial board of IEEE Transactions on Computers. Michael Goldwasser, PhD in Computer Science from Stanford University, 1997; Associate Professor and Director of CS at St. Louis University; author of Object-Oriented Programming in Python, Pearson, 2008.

strong>1 Java Primer 1 1.1 Getting Started 2

1.1.1 Base Types 4

1.2 Classes and Objects 5

1.2.1 Creating and Using Objects 6

1.2.2 Defining a Class 9

1.3 Strings, Wrappers, Arrays, and Enum Types 17

1.4 Expressions 23

1.4.1 Literals 23

1.4.2 Operators 24

1.4.3 Type Conversions 28

1.5 Control Flow 30

1.5.1 The If and Switch Statements 30

1.5.2 Loops 33

1.5.3 Explicit Control-Flow Statements 37

1.6 Simple Input and Output 38

1.7 An Example Program 41

1.8 Packages and Imports 44

1.9 Software Development 46

1.9.1 Design 46

1.9.2 Pseudocode 48

1.9.3 Coding 49

1.9.4 Documentation and Style 50

1.9.5 Testing and Debugging 53

1.10 Exercises 55

2 Object-Oriented Design 59

2.1 Goals, Principles, and Patterns 60

2.1.1 Object-Oriented Design Goals 60

2.1.2 Object-Oriented Design Principles 61

2.1.3 Design Patterns 63

2.2 Inheritance 64

2.2.1 Extending the CreditCard Class 65

2.2.2 Polymorphism and Dynamic Dispatch 68

2.2.3 Inheritance Hierarchies 69

2.3 Interfaces and Abstract Classes 76

2.3.1 Interfaces in Java 76

2.3.2 Multiple Inheritance for Interfaces 79

2.3.3 Abstract Classes 80

2.4 Exceptions 82

2.4.1 Catching Exceptions 82

2.4.2 Throwing Exceptions 85

2.4.3 Java’s Exception Hierarchy 86

2.5 Casting and Generics 88

2.5.1 Casting 88

2.5.2 Generics 91

2.6 Nested Classes 96

2.7 Exercises 97

3 Fundamental Data Structures 103

3.1 Using Arrays 104

3.1.1 Storing Game Entries in an Array 104

3.1.2 Sorting an Array 110

3.1.3 java.util Methods for Arrays and Random Numbers 112

3.1.4 Simple Cryptography with Character Arrays 115

3.1.5 Two-Dimensional Arrays and Positional Games 118

3.2 Singly Linked Lists 122

3.2.1 Implementing a Singly Linked List Class 126

3.3 Circularly Linked Lists 128

3.3.1 Round-Robin Scheduling 128

3.3.2 Designing and Implementing a Circularly Linked List 129

3.4 Doubly Linked Lists 132

3.4.1 Implementing a Doubly Linked List Class 135

3.5 Equivalence Testing 138

3.5.1 Equivalence Testing with Arrays 139

3.5.2 Equivalence Testing with Linked Lists 140

3.6 Cloning Data Structures 141

3.6.1 Cloning Arrays 142

3.6.2 Cloning Linked Lists 144

3.7 Exercises 145

4 Algorithm Analysis 149

4.1 Experimental Studies 151

4.1.1 Moving Beyond Experimental Analysis 154

4.2 The Seven Functions Used in This Book 156

4.2.1 Comparing Growth Rates 163

4.3 Asymptotic Analysis 164

4.3.1 The “Big-Oh” Notation 164

4.3.2 Comparative Analysis 168

4.3.3 Examples of Algorithm Analysis 170

4.4 Simple Justification Techniques 178

4.4.1 By Example 178

4.4.2 The “Contra” Attack 178

4.4.3 Induction and Loop Invariants 179

4.5 Exercises 182

5 Recursion 189

5.1 Illustrative Examples 191

5.1.1 The Factorial Function 191

5.1.2 Drawing an English Ruler 193

5.1.3 Binary Search 196

5.1.4 File Systems 198

5.2 Analyzing Recursive Algorithms 202

5.3 Further Examples of Recursion 206

5.3.1 Linear Recursion 206

5.3.2 Binary Recursion 211

5.3.3 Multiple Recursion 212

5.4 Designing Recursive Algorithms 214

5.5 Recursion Run Amok 215

5.5.1 Maximum Recursive Depth in Java 218

5.6 Eliminating Tail Recursion 219

5.7 Exercises 221

6 Stacks, Queues, and Deques 225

6.1 Stacks 226

6.1.1 The Stack Abstract Data Type 227

6.1.2 A Simple Array-Based Stack Implementation 230

6.1.3 Implementing a Stack with a Singly Linked List 233

6.1.4 Reversing an Array Using a Stack 234

6.1.5 Matching Parentheses and HTML Tags 235

6.2 Queues 238

6.2.1 The Queue Abstract Data Type 239

6.2.2 Array-Based Queue Implementation 241

6.2.3 Implementing a Queue with a Singly Linked List 245

6.2.4 A Circular Queue 246

6.3 Double-Ended Queues 248

6.3.1 The Deque Abstract Data Type 248

6.3.2 Implementing a Deque 250

6.3.3 Deques in the Java Collections Framework 251

6.4 Exercises 252

7 List and Iterator ADTs 257

7.1 The List ADT 258

7.2 Array Lists 260

7.2.1 Dynamic Arrays 263

7.2.2 Implementing a Dynamic Array 264

7.2.3 Amortized Analysis of Dynamic Arrays 265

7.2.4 Java’s StringBuilder class 269

7.3 Positional Lists 270

7.3.1 Positions 272

7.3.2 The Positional List Abstract Data Type 272

7.3.3 Doubly Linked List Implementation 276

7.4 Iterators 282

7.4.1 The Iterable Interface and Java’s For-Each Loop 283

7.4.2 Implementing Iterators 284

7.5 The Java Collections Framework 288

7.5.1 List Iterators in Java 289

7.5.2 Comparison to Our Positional List ADT 290

7.5.3 List-Based Algorithms in the Java Collections Framework 291

7.6 Sorting a Positional List 293

7.7 Case Study: Maintaining Access Frequencies 294

7.7.1 Using a Sorted List 294

7.7.2 Using a List with the Move-to-Front Heuristic 297

7.8 Exercises 300

8 Trees 307

8.1 General Trees308

8.1.1 Tree Definitions and Properties 309

8.1.2 The Tree Abstract Data Type 312

8.1.3 Computing Depth and Height 314

8.2 Binary Trees 317

8.2.1 The Binary Tree Abstract Data Type 319

8.2.2 Properties of Binary Trees 321

8.3 Implementing Trees 323

8.3.1 Linked Structure for Binary Trees 323

8.3.2 Array-Based Representation of a Binary Tree 331

8.3.3 Linked Structure for General Trees 333

8.4 Tree Traversal Algorithms 334

8.4.1 Preorder and Postorder Traversals of General Trees 334

8.4.2 Breadth-First Tree Traversal 336

8.4.3 Inorder Traversal of a Binary Tree 337

8.4.4 Implementing Tree Traversals in Java 339

8.4.5 Applications of Tree Traversals 343

8.4.6 Euler Tours 348

8.5 Exercises 350

9 Priority Queues 359

9.1 The Priority Queue Abstract Data Type 360

9.1.1 Priorities 360

9.1.2 The Priority Queue ADT 361

9.2 Implementing a Priority Queue 362

9.2.1 The Entry Composite 362

9.2.2 Comparing Keys with Total Orders 363

9.2.3 The AbstractPriorityQueue Base Class 364

9.2.4 Implementing a Priority Queue with an Unsorted List 366

9.2.5 Implementing a Priority Queue with a Sorted List 368

9.3 Heaps 370

9.3.1 The Heap Data Structure 370

9.3.2 Implementing a Priority Queue with a Heap 372

9.3.3 Analysis of a Heap-Based Priority Queue 379

9.3.4 Bottom-Up Heap Construction ⋆ 380

9.3.5 Using the java.util.PriorityQueue Class 384

9.4 Sorting with a Priority Queue 385

9.4.1 Selection-Sort and Insertion-Sort 386

9.4.2 Heap-Sort 388

9.5 Adaptable Priority Queues 390

9.5.1 Location-Aware Entries 391

9.5.2 Implementing an Adaptable Priority Queue 392

9.6 Exercises 395

10 Maps, Hash Tables, and Skip Lists 401

10.1 Maps 402

10.1.1 The Map ADT 403

10.1.2 Application: Counting Word Frequencies 405

10.1.3 An AbstractMap Base Class 406

10.1.4 A Simple Unsorted Map Implementation 408

10.2 Hash Tables 410

10.2.1 Hash Functions 411

10.2.2 Collision-Handling Schemes 417

10.2.3 Load Factors, Rehashing, and Efficiency 420

10.2.4 Java Hash Table Implementation 422

10.3 Sorted Maps 428

10.3.1 Sorted Search Tables 429

10.3.2 Two Applications of Sorted Maps 433

10.4 Skip Lists 436

10.4.1 Search and Update Operations in a Skip List 438

10.4.2 Probabilistic Analysis of Skip Lists ⋆ 442

10.5 Sets, Multisets, and Multimaps 445

10.5.1 The Set ADT 445

10.5.2 The Multiset ADT 447

10.5.3 The Multimap ADT 448

10.6 Exercises 451

11 Search Trees 459

11.1 Binary Search Trees 460

11.1.1 Searching Within a Binary Search Tree 461

11.1.2 Insertions and Deletions 463

11.1.3 Java Implementation 466

11.1.4 Performance of a Binary Search Tree 470

11.2 Balanced Search Trees 472

11.2.1 Java Framework for Balancing Search Trees 475

11.3 AVL Trees 479

11.3.1 Update Operations 481

11.3.2 Java Implementation 486

11.4 Splay Trees 488

11.4.1 Splaying 488

11.4.2 When to Splay 492

11.4.3 Java Implementation 494

11.4.4 Amortized Analysis of Splaying ⋆ 495

11.5 (2,4) Trees 500

11.5.1 Multiway Search Trees 500

11.5.2 (2,4)-Tree Operations 503

11.6 Red-Black Trees 510

11.6.1 Red-Black Tree Operations 512

11.6.2 Java Implementation 522

11.7 Exercises 525

12 Sorting and Selection 531

12.1 Merge-Sort 532

12.1.1 Divide-and-Conquer 532

12.1.2 Array-Based Implementation of Merge-Sort 537

12.1.3 The Running Time of Merge-Sort 538

12.1.4 Merge-Sort and Recurrence Equations ⋆ 540

12.1.5 Alternative Implementations of Merge-Sort 541

12.2 Quick-Sort 544

12.2.1 Randomized Quick-Sort 551

12.2.2 Additional Optimizations for Quick-Sort 553

12.3 Studying Sorting through an Algorithmic Lens 556

12.3.1 Lower Bound for Sorting 556

12.3.2 Linear-Time Sorting: Bucket-Sort and Radix-Sort 558

12.4 Comparing Sorting Algorithms 561

12.5 Selection 563

12.5.1 Prune-and-Search 563

12.5.2 Randomized Quick-Select 564

12.5.3 Analyzing Randomized Quick-Select 565

12.6 Exercises 566

13 Text Processing 573

13.1 Abundance of Digitized Text 574

13.1.1 Notations for Character Strings 575

13.2 Pattern-Matching Algorithms 576

13.2.1 Brute Force 576

13.2.2 The Boyer-Moore Algorithm 578

13.2.3 The Knuth-Morris-Pratt Algorithm 582

13.3 Tries 586

13.3.1 Standard Tries 586

13.3.2 Compressed Tries 590

13.3.3 Suffix Tries 592

13.3.4 Search Engine Indexing 594

13.4 Text Compression and the Greedy Method 595

13.4.1 The Huffman Coding Algorithm 596

13.4.2 The Greedy Method 597

13.5 Dynamic Programming 598

13.5.1 Matrix Chain-Product 598

13.5.2 DNA and Text Sequence Alignment 601

13.6 Exercises 605

14 Graph Algorithms 611

14.1 Graphs 612

14.1.1 The Graph ADT 618

14.2 Data Structures for Graphs 619

14.2.1 Edge List Structure 620

14.2.2 Adjacency List Structure 622

14.2.3 Adjacency Map Structure 624

14.2.4 Adjacency Matrix Structure 625

14.2.5 Java Implementation 626

14.3 Graph Traversals 630

14.3.1 Depth-First Search 631

14.3.2 DFS Implementation and Extensions 636

14.3.3 Breadth-First Search 640

14.4 Transitive Closure 643

14.5 Directed Acyclic Graphs 647

14.5.1 Topological Ordering 647

14.6 Shortest Paths 651

14.6.1 Weighted Graphs 651

14.6.2 Dijkstra’s Algorithm 653

14.7 Minimum Spanning Trees 662

14.7.1 Prim-Jarn´ýk Algorithm 664

14.7.2 Kruskal’s Algorithm 667

14.7.3 Disjoint Partitions and Union-Find Structures 672

14.8 Exercises 677

15 Memory Management and B-Trees 687

15.1 Memory Management 688

15.1.1 Stacks in the Java Virtual Machine 688

15.1.2 Allocating Space in the Memory Heap 691

15.1.3 Garbage Collection 693

15.2 Memory Hierarchies and Caching 695

15.2.1 Memory Systems 695

15.2.2 Caching Strategies 696

15.3 External Searching and B-Trees 701

15.3.1 (a,b) Trees 702

15.3.2 B-Trees 704

15.4 External-Memory Sorting 705

15.4.1 Multiway Merging 706

15.5 Exercises 707

Bibliography 710

Index 714