Data Structures with Java

Contents......Page 10
Software Design and Development......Page 18
Object-Oriented Design......Page 19
Abstract Data Types......Page 20
Java Interfaces......Page 21
Classes and Objects......Page 22
Modifiers......Page 25
Composition, Aggregation, and Inheritance......Page 27
The Unified Modeling Language......Page 30
Polymorphism......Page 31
Javadoc......Page 33
Properties of Arrays......Page 43
Duplicating an Array......Page 45
The java.util.Arrays Class......Page 46
The Sequential Search Algorithm......Page 47
The Binary Search Algorithm......Page 48
Maintaining an Ordered Array......Page 63
Indirect Reference......Page 64
Linked Nodes......Page 67
Inserting an Element into a Linked List......Page 72
Inserting at the Front of the List......Page 75
Nested Classes......Page 76
The Inheritance Hierarchy......Page 86
The Collection Interface......Page 87
The HashSet Class......Page 89
Generic Collections......Page 91
Generic Wildcards......Page 93
Iterators......Page 94
The TreeSet Class......Page 96
The EnumSet Class......Page 100
The List Interface......Page 102
The LinkedList Class......Page 103
The Queue Interface......Page 104
The PriorityQueue Class......Page 107
The Deque Interface and ArrayDeque Class......Page 108
The Map Interface and Its Implementing Classes......Page 109
The Arrays Class......Page 112
The Collections Class......Page 113
Autoboxing......Page 114
The JCF Stack Class......Page 120
An Indexed Implementation......Page 121
A Linked Implementation......Page 123
Abstracting the Common Code......Page 125
Application: An RPN Calculator......Page 126
The JCF Queue Interface......Page 134
A Simple Queue Interface......Page 135
An Indexed Implementation......Page 136
An Indexed Implementation......Page 137
Application: A Client-Server System......Page 138
The JCF List Interface......Page 148
The Range-View Operation sublist()......Page 149
List Iterators......Page 150
Other List Types......Page 153
Application: The Josephus Problem......Page 157
Application: A Polynomial Class......Page 158
The Java Map Interface......Page 165
The HashMap Class......Page 166
Java Hash Codes......Page 167
Hash Tables......Page 168
Hash Table Performance......Page 170
Collision Resolution Algorithms......Page 171
Separate Chaining......Page 173
Applications......Page 174
The TreeMap Class......Page 176
Simple Recursive Functions......Page 182
Basis and Recursive Parts......Page 183
Tracing A Recursive Call......Page 184
The Recursive Binary Search......Page 185
Binomial Coefficients......Page 186
Inductive Proof of Correctness......Page 188
Complexity Analysis......Page 189
The Towers of Hanoi......Page 190
Mutual Recursion......Page 192
Tree Definitions......Page 203
Decision Trees......Page 205
Transition Diagrams......Page 206
Ordered Trees......Page 208
Traversal Algorithms......Page 209
Definitions......Page 217
Counting Binary Trees......Page 218
Full Binary Trees......Page 219
Identity, Equality, and Isomorphism......Page 220
Complete Binary Trees......Page 222
Binary Tree Traversal Algorithms......Page 224
Expression Trees......Page 226
A BinaryTree Class......Page 228
Implementations of The Traversal Algorithms......Page 233
Forests......Page 236
Multiway Search Trees......Page 247
B-trees......Page 249
Binary Search Trees......Page 251
Performance of Binary Search Trees......Page 253
AVL Trees......Page 254
The Natural Mapping......Page 262
Insertion Into A Heap......Page 263
Priority Queues......Page 264
The JCF PriorityQueue Class......Page 265
Code Preliminaries......Page 272
The Bubble Sort......Page 273
The Selection Sort......Page 274
The Insertion Sort......Page 275
The Shell Sort......Page 276
The Merge Sort......Page 277
The Quick Sort......Page 280
The Heap Sort......Page 282
The Speed Limit For Comparison Sorts......Page 286
The Radix Sort......Page 287
The Bucket Sort......Page 288
Graph Terminology......Page 302
Paths and Cycles......Page 303
Isomorphic Graphs......Page 305
The Adjacency Matrix for a Graph......Page 307
The Adjacency List for a Graph......Page 308
Digraphs......Page 309
Paths in a Digraph......Page 311
Euler Paths and Hamiltonian Cycles......Page 312
Dijkstra’s Algorithm......Page 314
Graph Traversal Algorithms......Page 317
Logarithms......Page 336
Asymptotic Complexity Classes......Page 337
The First Principle of Mathematical Induction......Page 338
The Second Principle of Mathematical Induction......Page 339
Other Summation Formulas......Page 340
Stirling’s Formula......Page 341
Fibonacci Numbers......Page 342
C......Page 346
G......Page 347
M......Page 348
R......Page 349
W......Page 350