TABLE OF CONTENTS
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