Java Structures Data Structures in Java for the Principled Programmer

Java Structures......Page 1
Copyright (c) 2005-2007 Duane A. Bailey......Page 2
Table of Contents......Page 3
  Preface to First Edition......Page 11
  Preface to the Second Edition......Page 13
  Preface to the ``Root 7'' Edition......Page 15
0.1 Read Me......Page 17
0.2 He Can't Say That, Can He?......Page 18
1 The Object-Oriented Method......Page 21
1.1 Data Abstraction and Encapsulation......Page 22
1.2 The Object Model......Page 23
1.3 Object-Oriented Terminology......Page 24
1.4 A Special-Purpose Class: A Bank Account......Page 27
1.5 A General-Purpose Class: An Association......Page 30
1.6 Sketching an Example: A Word List......Page 34
1.7 Sketching an Example: A Rectangle Class......Page 36
1.8 Interfaces......Page 38
1.9 Who Is the User?......Page 40
1.10 Conclusions......Page 41
1.11 Laboratory: The Day of the Week Calculator......Page 45
2 Comments, Conditions, and Assertions......Page 49
2.2 Assertions......Page 50
2.3 Craftsmanship......Page 52
2.4 Conclusions......Page 53
2.5 Laboratory: Using Javadoc Commenting......Page 55
3 Vectors......Page 59
3.1 The Interface......Page 61
3.2 Example: The Word List Revisited......Page 63
3.3 Example: Word Frequency......Page 64
3.4 The Implementation......Page 66
3.5 Extensibility: A Feature......Page 69
3.6 Example: L-Systems......Page 72
3.7 Example: Vector-Based Sets......Page 73
3.8 Example: The Matrix Class......Page 76
3.9 Conclusions......Page 80
3.10 Laboratory: The Silver Dollar Game......Page 83
4 Generics......Page 85
4.1 Motivation (in case we need some)......Page 86
4.1.1 Possible Solution: Specialization......Page 87
4.2.1 Generic Associations......Page 88
4.2.2 Parameterizing the Vector Class......Page 90
4.2.3 Restricting Parameters......Page 95
4.3 Conclusions......Page 96
5.1 Asymptotic Analysis Tools......Page 97
5.1.1 Time and Space Complexity......Page 98
5.1.2 Examples......Page 101
5.1.3 The Trading of Time and Space......Page 107
5.1.4 Back-of-the-Envelope Estimations......Page 108
5.2.1 Recursion......Page 110
5.2.2 Mathematical Induction......Page 117
5.3.1 Symmetry......Page 124
5.4 Conclusions......Page 126
5.5 Laboratory: How Fast Is Java?......Page 131
6.1 Approaching the Problem......Page 135
6.2 Selection Sort......Page 138
6.3 Insertion Sort......Page 141
6.4 Mergesort......Page 143
6.5 Quicksort......Page 147
6.6 Radix Sort......Page 150
6.7 Sorting Objects......Page 154
6.8 Ordering Objects Using Comparators......Page 156
6.9 Vector-Based Sorting......Page 159
6.10 Conclusions......Page 160
6.11 Laboratory: Sorting with Comparators......Page 163
7.1 The Interface-Based Approach......Page 165
7.1.1 Design of the Interface......Page 166
7.1.2 Development of an Abstract Implementation......Page 167
7.2 Example: Development of Generators......Page 168
7.3 Example: Playing Cards......Page 171
7.4 Conclusions......Page 176
8.1 Java's Enumeration Interface......Page 177
8.2 The Iterator Interface......Page 179
8.3 Example: Vector Iterators......Page 181
8.4 Example: Rethinking Generators......Page 183
8.5 Example: Filtering Iterators......Page 186
8.6 Conclusions......Page 188
8.7 Laboratory: The Two-Towers Problem......Page 191
9 Lists......Page 195
9.1 Example: A Unique Program......Page 198
9.2 Example: Free Lists......Page 199
9.3 Partial Implementation: Abstract Lists......Page 202
9.4 Implementation: Singly Linked Lists......Page 204
9.5 Implementation: Doubly Linked Lists......Page 217
9.6 Implementation: Circularly Linked Lists......Page 222
9.8 List Iterators......Page 225
9.9 Conclusions......Page 227
9.10 Laboratory: Lists with Dummy Nodes......Page 231
10 Linear Structures......Page 235
10.1 Stacks......Page 237
10.1.1 Example: Simulating Recursion......Page 238
10.1.2 Vector-Based Stacks......Page 241
10.1.3 List-Based Stacks......Page 243
10.1.4 Comparisons......Page 244
10.2 Queues......Page 245
10.2.1 Example: Solving a Coin Puzzle......Page 247
10.2.2 List-Based Queues......Page 250
10.2.3 Vector-Based Queues......Page 251
10.2.4 Array-Based Queues......Page 254
10.3 Example: Solving Mazes......Page 258
10.4 Conclusions......Page 260
10.5 Laboratory: A Stack-Based Language......Page 263
10.6 Laboratory: The Web Crawler......Page 267
11.1 Comparable Objects Revisited......Page 269
11.1.1 Example: Comparable Ratios......Page 270
11.1.2 Example: Comparable Associations......Page 272
11.2.1 The OrderedStructure Interface......Page 274
11.2.2 The Ordered Vector and Binary Search......Page 275
11.2.3 Example: Sorting Revisited......Page 280
11.2.4 A Comparator-based Approach......Page 281
11.2.5 The Ordered List......Page 283
11.2.6 Example: The Modified Parking Lot......Page 286
11.3 Conclusions......Page 288
11.4 Laboratory: Computing the ``Best Of''......Page 291
12.1 Terminology......Page 293
12.2 Example: Pedigree Charts......Page 296
12.3 Example: Expression Trees......Page 297
12.4 Implementation......Page 298
12.4.1 The BinaryTree Implementation......Page 300
12.5 Example: An Expert System......Page 303
12.6 Traversals of Binary Trees......Page 306
12.6.1 Preorder Traversal......Page 307
12.6.2 In-order Traversal......Page 309
12.6.3 Postorder Traversal......Page 311
12.6.4 Level-order Traversal......Page 312
12.6.5 Recursion in Iterators......Page 313
12.7 Property-Based Methods......Page 315
12.8 Example: Huffman Compression......Page 319
12.9 Example Implementation: Ahnentafel......Page 323
12.10 Conclusions......Page 325
12.11 Laboratory: Playing Gardner's Hex-a-Pawn......Page 329
13.1 The Interface......Page 331
13.2 Example: Improving the Huffman Code......Page 333
13.3 A Vector-Based Implementation......Page 334
13.4 A Heap Implementation......Page 335
13.4.1 Vector-Based Heaps......Page 336
13.4.2 Example: Heapsort......Page 342
13.4.3 Skew Heaps......Page 345
13.5 Example: Circuit Simulation......Page 349
13.6 Conclusions......Page 353
13.7 Laboratory: Simulating Business......Page 357
14.1 Binary Search Trees......Page 359
14.3 Example: Associative Structures......Page 361
14.4 Implementation......Page 364
14.5 Splay Trees......Page 370
14.6 Splay Tree Implementation......Page 373
14.7 An Alternative: Red-Black Trees......Page 377
14.8 Conclusions......Page 379
14.9 Laboratory: Improving the BinarySearchTree......Page 383
15.1 Example Revisited: The Symbol Table......Page 385
15.2 The Interface......Page 386
15.3 Simple Implementation: MapList......Page 388
15.4 Constant Time Maps: Hash Tables......Page 390
15.4.1 Open Addressing......Page 391
15.4.2 External Chaining......Page 399
15.4.3 Generation of Hash Codes......Page 401
15.4.4 Hash Codes for Collection Classes......Page 407
15.5 Ordered Maps and Tables......Page 408
15.6 Example: Document Indexing......Page 411
15.7 Conclusions......Page 414
15.8 Laboratory: The Soundex Name Lookup System......Page 417
16.1 Terminology......Page 419
16.2 The Graph Interface......Page 420
16.3.1 Abstract Classes Reemphasized......Page 424
16.3.2 Adjacency Matrices......Page 426
16.3.3 Adjacency Lists......Page 432
16.4.1 Reachability......Page 438
16.4.2 Topological Sorting......Page 440
16.4.3 Transitive Closure......Page 443
16.4.4 All Pairs Minimum Distance......Page 444
16.4.5 Greedy Algorithms......Page 445
16.5 Conclusions......Page 450
16.6 Laboratory: Converting Between Units......Page 455
A.1 Solutions to Self Check Problems......Page 457
A.2 Solutions to Odd-Numbered Problems......Page 467
B.1 A First Program......Page 505
B.2.1 Primitive Types......Page 507
B.2.2 Reference Types......Page 509
B.3.1 The structure.ReadStream Class......Page 510
B.3.2 The java.util.Scanner Class......Page 511
B.3.3 The PrintStream Class......Page 512
B.3.4 Strings......Page 513
B.4.1 Conditional Statements......Page 514
B.4.2 Loops......Page 515
B.6.1 Inheritance......Page 518
B.6.2 Subtyping......Page 519
B.6.3 Interfaces and Abstract Classes......Page 520
B.7 Use of the Assert Command......Page 522
B.8 Use of the Keyword Protected......Page 523
C.2 Parallel Features......Page 527
C.3 Conversion......Page 528
D.1 Structure Package Hierarchy......Page 529
D.2 Principles......Page 531
  Index......Page 533
Colophon......Page 542