Java Structures: Data Structures in Java for the Principled Programmer (2nd edition)

Java Structures......Page 4
Copyright (c) 2005-2007 Duane A. Bailey......Page 5
Table of Contents......Page 6
  Preface to First Edition......Page 14
  Preface to the Second Edition......Page 16
  Preface to the ``Root 7'' Edition......Page 18
0.1 Read Me......Page 20
0.2 He Can't Say That, Can He?......Page 21
1 The Object-Oriented Method......Page 24
1.1 Data Abstraction and Encapsulation......Page 25
1.2 The Object Model......Page 26
1.3 Object-Oriented Terminology......Page 27
1.4 A Special-Purpose Class: A Bank Account......Page 30
1.5 A General-Purpose Class: An Association......Page 33
1.6 Sketching an Example: A Word List......Page 37
1.7 Sketching an Example: A Rectangle Class......Page 39
1.8 Interfaces......Page 41
1.9 Who Is the User?......Page 43
1.10 Conclusions......Page 44
1.11 Laboratory: The Day of the Week Calculator......Page 48
2 Comments, Conditions, and Assertions......Page 52
2.2 Assertions......Page 53
2.3 Craftsmanship......Page 55
2.4 Conclusions......Page 56
2.5 Laboratory: Using Javadoc Commenting......Page 58
3 Vectors......Page 62
3.1 The Interface......Page 64
3.2 Example: The Word List Revisited......Page 66
3.3 Example: Word Frequency......Page 67
3.4 The Implementation......Page 69
3.5 Extensibility: A Feature......Page 72
3.6 Example: L-Systems......Page 75
3.7 Example: Vector-Based Sets......Page 76
3.8 Example: The Matrix Class......Page 79
3.9 Conclusions......Page 83
3.10 Laboratory: The Silver Dollar Game......Page 86
4 Generics......Page 88
4.1 Motivation (in case we need some)......Page 89
4.1.1 Possible Solution: Specialization......Page 90
4.2.1 Generic Associations......Page 91
4.2.2 Parameterizing the Vector Class......Page 93
4.2.3 Restricting Parameters......Page 98
4.3 Conclusions......Page 99
5.1 Asymptotic Analysis Tools......Page 100
5.1.1 Time and Space Complexity......Page 101
5.1.2 Examples......Page 104
5.1.3 The Trading of Time and Space......Page 110
5.1.4 Back-of-the-Envelope Estimations......Page 111
5.2.1 Recursion......Page 113
5.2.2 Mathematical Induction......Page 120
5.3.1 Symmetry......Page 127
5.4 Conclusions......Page 129
5.5 Laboratory: How Fast Is Java?......Page 134
6.1 Approaching the Problem......Page 138
6.2 Selection Sort......Page 141
6.3 Insertion Sort......Page 144
6.4 Mergesort......Page 146
6.5 Quicksort......Page 150
6.6 Radix Sort......Page 153
6.7 Sorting Objects......Page 157
6.8 Ordering Objects Using Comparators......Page 159
6.9 Vector-Based Sorting......Page 162
6.10 Conclusions......Page 163
6.11 Laboratory: Sorting with Comparators......Page 166
7.1 The Interface-Based Approach......Page 168
7.1.1 Design of the Interface......Page 169
7.1.2 Development of an Abstract Implementation......Page 170
7.2 Example: Development of Generators......Page 171
7.3 Example: Playing Cards......Page 174
7.4 Conclusions......Page 179
8.1 Java's Enumeration Interface......Page 180
8.2 The Iterator Interface......Page 182
8.3 Example: Vector Iterators......Page 184
8.4 Example: Rethinking Generators......Page 186
8.5 Example: Filtering Iterators......Page 189
8.6 Conclusions......Page 191
8.7 Laboratory: The Two-Towers Problem......Page 194
9 Lists......Page 198
9.1 Example: A Unique Program......Page 201
9.2 Example: Free Lists......Page 202
9.3 Partial Implementation: Abstract Lists......Page 205
9.4 Implementation: Singly Linked Lists......Page 207
9.5 Implementation: Doubly Linked Lists......Page 220
9.6 Implementation: Circularly Linked Lists......Page 225
9.8 List Iterators......Page 228
9.9 Conclusions......Page 230
9.10 Laboratory: Lists with Dummy Nodes......Page 234
10 Linear Structures......Page 238
10.1 Stacks......Page 240
10.1.1 Example: Simulating Recursion......Page 241
10.1.2 Vector-Based Stacks......Page 244
10.1.3 List-Based Stacks......Page 246
10.1.4 Comparisons......Page 247
10.2 Queues......Page 248
10.2.1 Example: Solving a Coin Puzzle......Page 250
10.2.2 List-Based Queues......Page 253
10.2.3 Vector-Based Queues......Page 254
10.2.4 Array-Based Queues......Page 257
10.3 Example: Solving Mazes......Page 261
10.4 Conclusions......Page 263
10.5 Laboratory: A Stack-Based Language......Page 266
10.6 Laboratory: The Web Crawler......Page 270
11.1 Comparable Objects Revisited......Page 272
11.1.1 Example: Comparable Ratios......Page 273
11.1.2 Example: Comparable Associations......Page 275
11.2.1 The OrderedStructure Interface......Page 277
11.2.2 The Ordered Vector and Binary Search......Page 278
11.2.3 Example: Sorting Revisited......Page 283
11.2.4 A Comparator-based Approach......Page 284
11.2.5 The Ordered List......Page 286
11.2.6 Example: The Modified Parking Lot......Page 289
11.3 Conclusions......Page 291
11.4 Laboratory: Computing the ``Best Of''......Page 294
12.1 Terminology......Page 296
12.2 Example: Pedigree Charts......Page 299
12.3 Example: Expression Trees......Page 300
12.4 Implementation......Page 301
12.4.1 The BinaryTree Implementation......Page 303
12.5 Example: An Expert System......Page 306
12.6 Traversals of Binary Trees......Page 309
12.6.1 Preorder Traversal......Page 310
12.6.2 In-order Traversal......Page 312
12.6.3 Postorder Traversal......Page 314
12.6.4 Level-order Traversal......Page 315
12.6.5 Recursion in Iterators......Page 316
12.7 Property-Based Methods......Page 318
12.8 Example: Huffman Compression......Page 322
12.9 Example Implementation: Ahnentafel......Page 326
12.10 Conclusions......Page 328
12.11 Laboratory: Playing Gardner's Hex-a-Pawn......Page 332
13.1 The Interface......Page 334
13.2 Example: Improving the Huffman Code......Page 336
13.3 A Vector-Based Implementation......Page 337
13.4 A Heap Implementation......Page 338
13.4.1 Vector-Based Heaps......Page 339
13.4.2 Example: Heapsort......Page 345
13.4.3 Skew Heaps......Page 348
13.5 Example: Circuit Simulation......Page 352
13.6 Conclusions......Page 356
13.7 Laboratory: Simulating Business......Page 360
14.1 Binary Search Trees......Page 362
14.3 Example: Associative Structures......Page 364
14.4 Implementation......Page 367
14.5 Splay Trees......Page 373
14.6 Splay Tree Implementation......Page 376
14.7 An Alternative: Red-Black Trees......Page 380
14.8 Conclusions......Page 382
14.9 Laboratory: Improving the BinarySearchTree......Page 386
15.1 Example Revisited: The Symbol Table......Page 388
15.2 The Interface......Page 389
15.3 Simple Implementation: MapList......Page 391
15.4 Constant Time Maps: Hash Tables......Page 393
15.4.1 Open Addressing......Page 394
15.4.2 External Chaining......Page 402
15.4.3 Generation of Hash Codes......Page 404
15.4.4 Hash Codes for Collection Classes......Page 410
15.5 Ordered Maps and Tables......Page 411
15.6 Example: Document Indexing......Page 414
15.7 Conclusions......Page 417
15.8 Laboratory: The Soundex Name Lookup System......Page 420
16.1 Terminology......Page 422
16.2 The Graph Interface......Page 423
16.3.1 Abstract Classes Reemphasized......Page 427
16.3.2 Adjacency Matrices......Page 429
16.3.3 Adjacency Lists......Page 435
16.4.1 Reachability......Page 441
16.4.2 Topological Sorting......Page 443
16.4.3 Transitive Closure......Page 446
16.4.4 All Pairs Minimum Distance......Page 447
16.4.5 Greedy Algorithms......Page 448
16.5 Conclusions......Page 453
16.6 Laboratory: Converting Between Units......Page 458
A.1 Solutions to Self Check Problems......Page 460
A.2 Solutions to Odd-Numbered Problems......Page 470
B.1 A First Program......Page 508
B.2.1 Primitive Types......Page 510
B.2.2 Reference Types......Page 512
B.3.1 The structure.ReadStream Class......Page 513
B.3.2 The java.util.Scanner Class......Page 514
B.3.3 The PrintStream Class......Page 515
B.3.4 Strings......Page 516
B.4.1 Conditional Statements......Page 517
B.4.2 Loops......Page 518
B.6.1 Inheritance......Page 521
B.6.2 Subtyping......Page 522
B.6.3 Interfaces and Abstract Classes......Page 523
B.7 Use of the Assert Command......Page 525
B.8 Use of the Keyword Protected......Page 526
C.2 Parallel Features......Page 530
C.3 Conversion......Page 531
D.1 Structure Package Hierarchy......Page 532
D.2 Principles......Page 534
  Index......Page 536
Colophon......Page 545