Data structures and abstractions with Java

Cover......Page 1
Contents......Page 14
Introduction......Page 24
Chapter 1 Java Classes......Page 28
 Objects and Classes......Page 29
 Using the Methods in a Java Class......Page 31
  References and Aliases......Page 32
 Defining a Java Class......Page 33
  Method Definitions......Page 34
  Arguments and Parameters......Page 36
  Passing Arguments......Page 37
  A Definition of the Class Name......Page 41
  Constructors......Page 42
  The Method toString......Page 44
  Methods That Call Other Methods......Page 45
  Methods That Return an Instance of Their Class......Page 46
  Static Fields and Methods......Page 47
  Overloading Methods......Page 48
 Enumeration as a Class......Page 49
 Packages......Page 52
  The Java Class Library......Page 53
Chapter 2 Creating Classes from Other Classes......Page 62
 Composition......Page 63
  Generic Types......Page 66
  Adapters......Page 68
 Inheritance......Page 69
  Invoking Constructors from Within Constructors......Page 72
  Private Fields and Methods of the Base Class......Page 74
  Overriding and Overloading Methods......Page 75
  Multiple Inheritance......Page 80
 Type Compatibility and Base Classes......Page 81
  The Class Object......Page 82
  Abstract Classes and Methods......Page 84
 Polymorphism......Page 86
Chapter 3 Designing Classes......Page 100
 Encapsulation......Page 101
 Specifying Methods......Page 103
  Assertions......Page 105
  Writing an Interface......Page 107
  Implementing an Interface......Page 109
  An Interface as a Data Type......Page 110
  Generic Types Within an Interface......Page 111
  The Interface Comparable......Page 112
  Extending an Interface......Page 114
  Interfaces Versus Abstract Classes......Page 115
  Named Constants......Page 116
 Choosing Classes......Page 118
  Identifying Classes......Page 119
  CRC Cards......Page 120
 Reusing Classes......Page 123
Chapter 4 Lists......Page 130
 Specifications for the ADT List......Page 131
  Refining the Specifications......Page 136
 Using the ADT List......Page 139
 Using a List Is Like Using a Vending Machine......Page 143
 Java Class Library: The Interface List......Page 145
Chapter 5 List Implementations That Use Arrays......Page 150
  An Analogy......Page 151
  The Java Implementation......Page 153
  Expanding an Array......Page 161
  A New Implementation of a List......Page 163
 Java Class Library: The Classes ArrayList and Vector......Page 165
  Using a Vector to Implement the ADT List......Page 166
 The Pros and Cons of Using an Array to Implement the ADT List......Page 169
Chapter 6 A List Implementation That Links Data......Page 174
 Linked Data......Page 175
  Forming a Chain by Adding to Its Beginning......Page 176
  Forming a Chain by Adding to Its End......Page 178
  Forming a Chain by Adding at Various Positions......Page 180
  The Private Class Node......Page 183
  The Data Fields and Constructor......Page 185
  Choosing a Core Group of Methods to Implement......Page 186
  Adding to the End of the List......Page 187
  Adding at a Given Position Within the List......Page 189
  The Private Method getNodeAt......Page 193
  Assertions and the Method isEmpty......Page 194
  The Method display......Page 195
 Testing the Incomplete Implementation......Page 196
Chapter 7 Completing the Linked Implementation of a List......Page 202
 Removing an Item from a Linked Chain......Page 203
  The Method remove......Page 206
  The Method getEntry......Page 209
  The Remaining Methods......Page 210
 A Class Node That Has Set and Get Methods......Page 211
 Tail References......Page 214
  A Revised Implementation of the List......Page 215
 Java Class Library: The Class LinkedList......Page 219
Chapter 8 Iterators......Page 224
 What Is an Iterator?......Page 225
 The Interface Iterator......Page 226
  Using the Interface Iterator......Page 227
 A Separate Class Iterator......Page 233
  A Linked Implementation......Page 236
  An Array-Based Implementation......Page 240
 Why Are Iterator Methods in Their Own Class?......Page 244
 The Interface ListIterator......Page 245
  Using the Interface ListIterator......Page 249
 An Array-Based Implementation of the Interface ListIterator......Page 251
  The Inner Class......Page 252
 Java Class Library: The Interface Iterable......Page 258
  Iterable and for-each loops......Page 259
  The Interface List Revisited......Page 260
Chapter 9 The Efficiency of Algorithms......Page 266
 Motivation......Page 267
 Measuring an Algorithm’s Efficiency......Page 269
  Big Oh Notation......Page 272
 Formalities......Page 275
 Picturing Efficiency......Page 278
  An Array-Based Implementation......Page 281
  A Linked Implementation......Page 283
  Comparing the Implementations......Page 285
Chapter 10 Recursion......Page 292
 What Is Recursion?......Page 293
 Tracing a Recursive Method......Page 298
 Recursive Methods That Return a Value......Page 300
 Recursively Processing an Array......Page 303
 Recursively Processing a Linked Chain......Page 305
  The Time Efficiency of countDown......Page 307
  The Time Efficiency of Computing x[sup(n)]......Page 308
 A Simple Solution to a Difficult Problem......Page 310
 A Poor Solution to a Simple Problem......Page 315
 Tail Recursion......Page 317
 Mutual Recursion......Page 319
Chapter 11 An Introduction to Sorting......Page 328
 Organizing Java Methods That Sort an Array......Page 329
 Selection Sort......Page 331
  Iterative Selection Sort......Page 332
  The Efficiency of Selection Sort......Page 335
 Insertion Sort......Page 336
  Iterative Insertion Sort......Page 337
  Recursive Insertion Sort......Page 339
  Insertion Sort of a Chain of Linked Nodes......Page 341
 Shell Sort......Page 345
  The Java Code......Page 346
  The Efficiency of Shell Sort......Page 347
 Comparing the Algorithms......Page 348
Chapter 12 Faster Sorting Methods......Page 354
  Merging Arrays......Page 355
  Recursive Merge Sort......Page 356
  The Efficiency of Merge Sort......Page 359
  Iterative Merge Sort......Page 360
 Quick Sort......Page 361
  The Efficiency of Quick Sort......Page 362
  Creating the Partition......Page 363
  Java Code for Quick Sort......Page 366
 Radix Sort......Page 369
  The Efficiency of Radix Sort......Page 371
 Comparing the Algorithms......Page 372
Chapter 13 Sorted Lists......Page 378
 Specifications for the ADT Sorted List......Page 379
  Using the ADT Sorted List......Page 382
 A Linked Implementation......Page 383
  The Method add......Page 384
 An Implementation That Uses the ADT List......Page 391
  Efficiency Issues......Page 395
Chapter 14 Inheritance and Lists......Page 400
 Using Inheritance to Implement a Sorted List......Page 401
 Designing a Base Class......Page 403
  Creating an Abstract Base Class......Page 408
  The Method add......Page 410
Chapter 15 Mutable, Immutable, and Cloneable Objects......Page 414
 Mutable and Immutable Objects......Page 415
  Creating a Read-Only Class......Page 418
  Companion Classes......Page 419
 Cloneable Objects......Page 421
  Cloning an Array......Page 427
  Cloning a Chain......Page 430
  A Sorted List of Clones......Page 433
Chapter 16 Searching......Page 440
 The Problem......Page 441
  An Iterative Sequential Search of an Unsorted Array......Page 442
  A Recursive Sequential Search of an Unsorted Array......Page 443
  A Sequential Search of a Sorted Array......Page 445
  A Binary Search of a Sorted Array......Page 446
  The Efficiency of a Binary Search of an Array......Page 451
 Searching an Unsorted Chain......Page 452
  A Recursive Sequential Search of an Unsorted Chain......Page 453
  The Efficiency of a Sequential Search of a Chain......Page 454
  A Binary Search of a Sorted Chain......Page 455
 Choosing a Search Method......Page 456
Chapter 17 Dictionaries......Page 462
 Specifications for the ADT Dictionary......Page 463
  A Java Interface......Page 467
  Iterators......Page 468
 Using the ADT Dictionary......Page 469
  A Directory of Telephone Numbers......Page 470
  The Frequency of Words......Page 475
  A Concordance of Words......Page 478
 Java Class Library: The Interface Map......Page 481
Chapter 18 Dictionary Implementations......Page 486
  An Unsorted Array-Based Dictionary......Page 487
  A Sorted Array-Based Dictionary......Page 492
 Vector-Based Implementations......Page 497
 Linked Implementations......Page 501
  An Unsorted Linked Dictionary......Page 502
  A Sorted Linked Dictionary......Page 503
Chapter 19 Introducing Hashing......Page 510
 What Is Hashing?......Page 511
  Computing Hash Codes......Page 514
  Compressing a Hash Code into an Index for the Hash Table......Page 517
  Open Addressing with Linear Probing......Page 518
  Open Addressing with Double Hashing......Page 524
  Separate Chaining......Page 526
Chapter 20 Hashing as a Dictionary Implementation......Page 534
  The Load Factor......Page 535
  The Cost of Open Addressing......Page 536
  The Cost of Separate Chaining......Page 538
 Rehashing......Page 539
 Comparing Schemes for Collision Resolution......Page 540
  Entries in the Hash Table......Page 541
  Data Fields and Constructors......Page 542
  The Methods getValue, remove, and add......Page 544
  Iterators......Page 550
 Java Class Library: The Class HashMap......Page 551
Chapter 21 Stacks......Page 556
 Specifications of the ADT Stack......Page 557
 Using a Stack to Process Algebraic Expressions......Page 561
  Checking for Balanced Parentheses, Brackets, and Braces in an Infix Algebraic Expression......Page 562
  Transforming an Infix Expression to a Postfix Expression......Page 567
  Evaluating Postfix Expressions......Page 574
  Evaluating Infix Expressions......Page 575
 The Program Stack......Page 578
  Recursive Methods......Page 579
  An Iterative Binary Search......Page 580
 Java Class Library: The Class Stack......Page 582
Chapter 22 Stack Implementations......Page 588
 A Linked Implementation......Page 589
 An Array-Based Implementation......Page 592
 A Vector-Based Implementation......Page 596
Chapter 23 Queues, Deques, and Priority Queues......Page 602
 Specifications of the ADT Queue......Page 603
 Using a Queue to Simulate a Waiting Line......Page 607
  The Classes WaitLine and Customer......Page 608
  The Classes StockLedger and StockPurchase......Page 613
 Java Class Library: The Interface Queue......Page 616
 Specifications of the ADT Deque......Page 617
 Using a Deque to Compute the Capital Gain in a Sale of Stock......Page 619
 Specifications of the ADT Priority Queue......Page 620
 Using a Priority Queue to Track Your Assignments......Page 621
Chapter 24 Queue, Deque, and Priority Queue Implementations......Page 628
 A Linked Implementation of a Queue......Page 629
  A Circular Array......Page 633
  A Circular Array with One Unused Location......Page 636
 A Vector-Based Implementation of a Queue......Page 642
 Circular Linked Implementations of a Queue......Page 643
  A Two-Part Circular Linked Chain......Page 644
 A Doubly Linked Implementation of a Deque......Page 651
 Possible Implementations of a Priority Queue......Page 655
 Java Class Library: The Class PriorityQueue......Page 656
Chapter 25 Trees......Page 662
  Hierarchical Organizations......Page 663
  Tree Terminology......Page 665
  Traversals of a Binary Tree......Page 670
 Java Interfaces for Trees......Page 673
  An Interface for Binary Trees......Page 674
  Expression Trees......Page 676
  Decision Trees......Page 678
  Binary Search Trees......Page 682
  Heaps......Page 684
 Examples of General Trees......Page 686
  Game Trees......Page 687
Chapter 26 Tree Implementations......Page 694
 The Nodes in a Binary Tree......Page 695
  An Interface for a Node......Page 696
  An Implementation of BinaryNode......Page 697
 An Implementation of the ADT Binary Tree......Page 698
  Creating a Basic Binary Tree......Page 699
  The Method privateSetTree......Page 700
  Accessor and Mutator Methods......Page 703
  Computing the Height and Counting Nodes......Page 704
  Traversals......Page 705
 An Implementation of an Expression Tree......Page 710
  A Node for a General Tree......Page 712
  Using a Binary Tree to Represent a General Tree......Page 713
Chapter 27 A Binary Search Tree Implementation......Page 720
 Getting Started......Page 721
  An Interface for the Binary Search Tree......Page 722
  Duplicate Entries......Page 724
  Beginning the Class Definition......Page 725
 Searching and Retrieving......Page 726
 Adding an Entry......Page 728
  A Recursive Implementation......Page 729
  An Iterative Implementation......Page 733
  Removing an Entry Whose Node Is a Leaf......Page 735
  Removing an Entry Whose Node Has Two Children......Page 736
  A Recursive Implementation......Page 740
  An Iterative Implementation......Page 744
 The Efficiency of Operations......Page 748
  The Importance of Balance......Page 749
  The Order in Which Nodes Are Added......Page 750
 An Implementation of the ADT Dictionary......Page 751
Chapter 28 A Heap Implementation......Page 760
 Using an Array to Represent a Heap......Page 761
 Adding an Entry......Page 764
 Removing the Root......Page 767
 Creating a Heap......Page 770
 Heap Sort......Page 773
Chapter 29 Balanced Search Trees......Page 780
  Single Rotations......Page 781
  Double Rotations......Page 784
  Implementation Details......Page 788
 2-3 Trees......Page 793
  Searching a 2-3 Tree......Page 794
  Adding Entries to a 2-3 Tree......Page 795
  Splitting Nodes During Addition......Page 797
 2-4 Trees......Page 798
  Adding Entries to a 2-4 Tree......Page 799
  Comparing AVL, 2-3, and 2-4 Trees......Page 801
 Red-Black Trees......Page 802
  Properties of a Red-Black Tree......Page 803
  Adding Entries to a Red-Black Tree......Page 804
  Java Class Library: The Class TreeMap......Page 809
 B-Trees......Page 810
Chapter 30 Graphs......Page 814
  Road Maps......Page 815
  Airline Routes......Page 818
  Course Prerequisites......Page 819
 Traversals......Page 820
  Breadth-First Traversal......Page 821
  Depth-First Traversal......Page 823
 Topological Order......Page 824
  The Shortest Path in an Unweighted Graph......Page 826
  The Shortest Path in a Weighted Graph......Page 830
 Java Interfaces for the ADT Graph......Page 834
Chapter 31 Graph Implementations......Page 844
  The Adjacency Matrix......Page 845
  The Adjacency List......Page 846
 Vertices and Edges......Page 847
  Specifying the Class Vertex......Page 848
  The Inner Class Edge......Page 850
  Implementing the Class Vertex......Page 851
  Basic Operations......Page 855
  Graph Algorithms......Page 859
Appendix A: Java Essentials......Page 866
Appendix B: Exception Handling......Page 926
Appendix C: File Input and Output......Page 938
Appendix D: Documentation and Programming Style......Page 960
Appendix E: Answers to Self-Test Questions......Page 966
 A......Page 1006
 C......Page 1008
 D......Page 1010
 H......Page 1011
 I......Page 1012
 L......Page 1014
 M......Page 1015
 P......Page 1016
 R......Page 1017
 S......Page 1018
 T......Page 1019
 V......Page 1020
 W......Page 1021