Data Structures and Abstractions with Java

Introduction 1

Chapter 1 Bags 5
The Bag 6
A Bag's Behaviors 6
Specifying a Bag 7
An Interface 13
Using the ADT Bag 15
Using an ADT Is Like Using a Vending Machine 20
Java Class Library: The Interface Set 21

Chapter 2 Bag Implementations That Use Arrays 27
Using a Fixed-Size Array to Implement the ADT Bag 28
An Analogy 28
A Group of Core Methods 29
Implementing the Core Methods 30
Testing the Core Methods 37
Implementing More Methods 40
Methods That Remove Entries 42
Using Array Resizing to Implement the ADT Bag 50
Resizing an Array 50
A New Implementation of a Bag 53
The Pros and Cons of Using an Array to Implement the ADT Bag 55

Chapter 3 A Bag Implementation That Links Data 61
Linked Data 62
Forming a Chain by Adding to Its Beginning 63
A Linked Implementation of the ADT Bag 65
The Private Class Node 65
An Outline of the Class LinkedBag 66
Defining Some Core Methods 67
Testing the Core Methods 71
The Method getFrequencyOf 72
The Method contains 73
Removing an Item from a Linked Chain 74
The Methods remove and clear 75
A Class Node That Has Set and Get Methods 78
The Pros and Cons of Using a Chain to Implement the ADT Bag 81

Chapter 4 The Efficiency of Algorithms 87
Motivation 88
Measuring an Algorithm's Efficiency 89
Counting Basic Operations 91
Best, Worst, and Average Cases 93
Big Oh Notation 94
The Complexities of Program Constructs 97
Picturing Efficiency 98
The Efficiency of Implementations of the ADT Bag 102
An Array-Based Implementation 102
A Linked Implementation 103
Comparing the Implementations 104

Chapter 5 Stacks 113
Specifications of the ADT Stack 114
Using a Stack to Process Algebraic Expressions 118
A Problem Solved: Checking for Balanced Delimiters in an
Infix Algebraic Expression 119
A Problem Solved: Transforming an Infix Expression
to a Postfix Expression 123
A Problem Solved: Evaluating Postfix Expressions 128
A Problem Solved: Evaluating Infix Expressions 130
The Program Stack 132
Java Class Library: The Class Stack 133

Chapter 6 Stack Implementations 141
A Linked Implementation 141
An Array-Based Implementation 145
A Vector-Based Implementation 149
Java Class Library: The Class Vector 150
Using a Vector to Implement the ADT Stack 150

Chapter 7 Recursion 157
What Is Recursion? 158
Tracing a Recursive Method 162
Recursive Methods That Return a Value 166
Recursively Processing an Array 168
Recursively Processing a Linked Chain 171
The Time Efficiency of Recursive Methods 172
The Time Efficiency of countDown 172
The Time Efficiency of Computing xn 174
A Simple Solution to a Difficult Problem 175
A Poor Solution to a Simple Problem 180
Tail Recursion 182
Indirect Recursion 184
Using a Stack Instead of Recursion 185

Chapter 8 An Introduction to Sorting 195
Organizing Java Methods That Sort an Array 196
Selection Sort 198
Iterative Selection Sort 199
Recursive Selection Sort 201
The Efficiency of Selection Sort 202
Insertion Sort 203
Iterative Insertion Sort 204
Recursive Insertion Sort 206
The Efficiency of Insertion Sort 208
Insertion Sort of a Chain of Linked Nodes 208
Shell Sort 211
The Java Code 213
The Efficiency of Shell Sort 214
Comparing the Algorithms 214

Chapter 9 Faster Sorting Methods 221
Merge Sort 222
Merging Arrays 222
Recursive Merge Sort 223
The Efficiency of Merge Sort 225
Iterative Merge Sort 227
Merge Sort in the Java Class Library 227
Quick Sort 228
The Efficiency of Quick Sort 228
Creating the Partition 229
Java Code for Quick Sort 232
Quick Sort in the Java Class Library 234
Radix Sort 235
Pseudocode for Radix Sort 236
The Efficiency of Radix Sort 237
Comparing the Algorithms 237

Chapter 10 Queues, Deques, and Priority Queues 245
The ADT Queue 246
A Problem Solved: Simulating a Waiting Line 250
A Problem Solved: Computing the Capital Gain in a Sale of Stock 256
Java Class Library: The Interface Queue 259
The ADT Deque 260
A Problem Solved: Computing the Capital Gain in a Sale of Stock 262
Java Class Library: The Interface Deque 263
Java Class Library: The Class ArrayDeque 264
The ADT Priority Queue 265
A Problem Solved: Tracking Your Assignments 266
Java Class Library: The Class PriorityQueue 268

Chapter 11 Queue, Deque, and Priority Queue Implementations 273
A Linked Implementation of a Queue 274
An Array-Based Implementation of a Queue 278
A Circular Array 278
A Circular Array with One Unused Location 281
A Vector-Based Implementation of a Queue 286
Circular Linked Implementations of a Queue 288
A Two-Part Circular Linked Chain 289
Java Class Library: The Class AbstractQueue 294
A Doubly Linked Implementation of a Deque 295
Possible Implementations of a Priority Queue 299

Chapter 12 Lists 305
Specifications for the ADT List 306
Using the ADT List 312
Java Class Library: The Interface List 316
Java Class Library: The Class ArrayList 316

Chapter 13 List Implementations That Use Arrays 321
Using an Array to Implement the ADT List 322
An Analogy 322
The Java Implementation 324
The Efficiency of Using an Array to Implement the ADT List 331
Using a Vector to Implement the ADT List 332

Chapter 14 A List Implementation That Links Data 339
Operations on a Chain of Linked Nodes 340
Adding a Node at Various Positions 340
Removing a Node from Various Positions 344
The Private Method getNodeAt 345
Beginning the Implementation 346
The Data Fields and Constructor 347
Adding to the End of the List 348
Adding at a Given Position Within the List 349
The Methods isEmpty and toArray 350
Testing the Core Methods 353
Continuing the Implementation 354
A Refined Implementation 356
The Tail Reference 357
The Efficiency of Using a Chain to Implement the ADT List 360
Java Class Library: The Class LinkedList 362

Chapter 15 Iterators 369
What Is an Iterator? 370
The Interface Iterator 371
Using the Interface Iterator 372
A Separate Class Iterator 377
An Inner Class Iterator 381
A Linked Implementation 381
An Array-Based Implementation 385
Why Are Iterator Methods in Their Own Class? 388
The Interface ListIterator 390
Using the Interface ListIterator 393
An Array-Based Implementation of the Interface ListIterator 395
The Inner Class 397
Java Class Library: The Interface Iterable 402
Iterable and for-each loops 403
The Interface List Revisited 403

Chapter 16 Sorted Lists 411
Specifications for the ADT Sorted List 412
Using the ADT Sorted List 415
A Linked Implementation 416
The Method add 417
The Efficiency of the Linked Implementation 424
An Implementation That Uses the ADT List 424
Efficiency Issues 427

Chapter 17 Inheritance and Lists 433
Using Inheritance to Implement a Sorted List 434
Designing a Base Class 436
Creating an Abstract Base Class 441
An Efficient Implementation of a Sorted List 443
The Method add 443

Chapter 18 Searching 447
The Problem 448
Searching an Unsorted Array 448
An Iterative Sequential Search of an Unsorted Array 449
A Recursive Sequential Search of an Unsorted Array 450
The Efficiency of a Sequential Search of an Array 452
Searching a Sorted Array 452
A Sequential Search of a Sorted Array 452
A Binary Search of a Sorted Array 453
Java Class Library: The Method binarySearch 458
The Efficiency of a Binary Search of an Array 458
Searching an Unsorted Chain 460
An Iterative Sequential Search of an Unsorted Chain 460
A Recursive Sequential Search of an Unsorted Chain 461
The Efficiency of a Sequential Search of a Chain 462
Searching a Sorted Chain 462
A Sequential Search of a Sorted Chain 462
A Binary Search of a Sorted Chain 462
Choosing a Search Method 463

Chapter 19 Dictionaries 471
Specifications for the ADT Dictionary 472
A Java Interface 476
Iterators 477
Using the ADT Dictionary 478
A Problem Solved: A Directory of Telephone Numbers 479
A Problem Solved: The Frequency of Words 484
A Problem Solved: A Concordance of Words 488
Java Class Library: The Interface Map 490

Chapter 20 Dictionary Implementations 497
Array-Based Implementations 498
An Unsorted Array-Based Dictionary 498
A Sorted Array-Based Dictionary 503
Vector-Based Implementations 508
Linked Implementations 512
An Unsorted Linked Dictionary 514
A Sorted Linked Dictionary 514

Chapter 21 Introducing Hashing 523
What Is Hashing? 524
Hash Functions 527
Computing Hash Codes 527
Compressing a Hash Code into an Index for the Hash Table 530
Resolving Collisions 531
Open Addressing with Linear Probing 531
Open Addressing with Quadratic Probing 537
Open Addressing with Double Hashing 537
A Potential Problem with Open Addressing 539
Separate Chaining 539

Chapter 22 Hashing as a Dictionary Implementation 547
The Efficiency of Hashing 548
The Load Factor 548
The Cost of Open Addressing 549
The Cost of Separate Chaining 551
Rehashing 552
Comparing Schemes for Collision Resolution 553
A Dictionary Implementation That Uses Hashing 554
Entries in the Hash Table 554
Data Fields and Constructors 555
The Methods getValue, remove, and add 557
Iterators 562
Java Class Library: The Class HashMap 564
Java Class Library: The Class HashSet 564

Chapter 23 Trees 569
Tree Concepts 570
Hierarchical Organizations 570
Tree Terminology 572
Traversals of a Tree 576
Traversals of a Binary Tree 576
Traversals of a General Tree 579
Java Interfaces for Trees 579
Interfaces for All Trees 580
An Interface for Binary Trees 580
Examples of Binary Trees 582
Expression Trees 582
Decision Trees 584
Binary Search Trees 588
Heaps 590
Examples of General Trees 593
Parse Trees 593
Game Trees 593

Chapter 24 Tree Implementations 603
The Nodes in a Binary Tree 604
An Interface for a Node 605
An Implementation of BinaryNode 606
An Implementation of the ADT Binary Tree 607
Creating a Basic Binary Tree 608
The Method privateSetTree 609
Accessor and Mutator Methods 612
Computing the Height and Counting Nodes 613
Traversals 614
An Implementation of an Expression Tree 619
General Trees 621
A Node for a General Tree 621
Using a Binary Tree to Represent a General Tree 622

Chapter 25 A Binary Search Tree Implementation 629
Getting Started 630
An Interface for the Binary Search Tree 631
Duplicate Entries 633
Beginning the Class Definition 634
Searching and Retrieving 635
Traversing 637
Adding an Entry 637
A Recursive Implementation 638
An Iterative Implementation 642
Removing an Entry 643
Removing an Entry Whose Node Is a Leaf 644
Removing an Entry Whose Node Has One Child 644
Removing an Entry Whose Node Has Two Children 645
Removing an Entry in the Root 648
A Recursive Implementation 649
An Iterative Implementation 652
The Efficiency of Operations 656
The Importance of Balance 657
The Order in Which Nodes Are Added 658
An Implementation of the ADT Dictionary 659

Chapter 26 A Heap Implementation 673
Reprise: The ADT Heap 674
Using an Array to Represent a Heap 674
Adding an Entry 677
Removing the Root 680
Creating a Heap 683
Heap Sort 686

Chapter 27 Balanced Search Trees 695
AVL Trees 696
Single Rotations 696
Double Rotations 699
Implementation Details 703
2-3 Trees 707
Searching a 2-3 Tree 708
Adding Entries to a 2-3 Tree 709
Splitting Nodes During Addition 711
2-4 Trees 712
Adding Entries to a 2-4 Tree 713
Comparing AVL, 2-3, and 2-4 Trees 715
Red-Black Trees 716
Properties of a Red-Black Tree 717
Adding Entries to a Red-Black Tree 718
Java Class Library: The Class TreeMap 724
B-Trees 724

Chapter 28 Graphs 731
Some Examples and Terminology 732
Road Maps 732
Airline Routes 735
Mazes 736
Course Prerequisites 736
Trees 737
Traversals 737
Breadth-First Traversal 738
Depth-First Traversal 740
Topological Order 741
Paths 744
Finding a Path 744
The Shortest Path in an Unweighted Graph 744
The Shortest Path in a Weighted Graph 747
Java Interfaces for the ADT Graph 751

Chapter 29 Graph Implementations 761
An Overview of Two Implementations 762
The Adjacency Matrix 762
The Adjacency List 763
Vertices and Edges 764
Specifying the Class Vertex 765
The Inner Class Edge 767
Implementing the Class Vertex 768
An Implementation of the ADT Graph 772
Basic Operations 772
Graph Algorithms 775

Chapter 30 Mutable, Immutable, and Cloneable Objects Online
Mutable and Immutable Objects 30-2
Creating a Read-Only Class 30-4
Companion Classes 30-6
Cloneable Objects 30-8
Cloning an Array 30-14
Cloning a Chain 30-16
A Sorted List of Clones 30-19

Appendices
A. Java Essentials A-1
Introduction A-2
Applications and Applets A-2
Objects and Classes A-3
A First Java Application Program A-3
Java Basics A-5
Identifiers A-5
Reserved Words A-6
Variables A-6
Primitive Types A-7
Constants A-7
Assignment Statements A-8
Assignment Compatibilities A-9
Type Casting A-9
Arithmetic Operators and Expressions A-10
Parentheses and Precedence Rules A-11
Increment and Decrement Operators A-12
Special Assignment Operators A-13
Named Constants A-14
The Class Math A-15
Simple Input and Output Using the Keyboard and Screen A-15
Screen Output A-15
Keyboard Input Using the Class Scanner A-17
The if-else Statement A-19
Boolean Expressions A-20
Nested Statements A-23
Multiway if-else Statements A-24
The Conditional Operator (Optional) A-25
The switch Statement A-26
Enumerations A-28
Scope A-30
Loops A-30
The while Statement A-31
The for Statement A-32
The do-while Statement A-34
Additional Loop Information A-35
The Class String A-36
Characters Within Strings A-36
Concatenation of Strings A-37
String Methods A-38
The Class StringBuilder A-40
Using Scanner to Extract Pieces of a String A-42
Arrays A-44
Array Parameters and Returned Values A-46
Initializing Arrays A-47
Array Index Out of Bounds A-47
Use of = and == with Arrays A-47
Arrays and the For-Each Loop A-48
Multidimensional Arrays A-49
Wrapper Classes A-51

B. Java Classes B-1
Objects and Classes B-1
Using the Methods in a Java Class B-3
References and Aliases B-4
Defining a Java Class B-5
Method Definitions B-7
Arguments and Parameters B-9
Passing Arguments B-9
A Definition of the Class Name B-13
Constructors B-15
The Method toString B-17
Methods That Call Other Methods B-17
Methods That Return an Instance of Their Class B-19
Static Fields and Methods B-19
Overloading Methods B-21
Enumeration as a Class B-22
Packages B-25
The Java Class Library B-25
Generic Data Types B-26

C. Creating Classes from Other Classes C-1
Composition C-2
Adapters C-4
Inheritance C-5
Invoking Constructors from Within Constructors C-9
Private Fields and Methods of the Superclass C-10
Protected Access C-11
Overriding and Overloading Methods C-11
Multiple Inheritance C-16
Type Compatibility and Superclasses C-16
The Class Object C-18
Abstract Classes and Methods C-19
Polymorphism C-21

D. Designing Classes D-1
Encapsulation D-2
Specifying Methods D-4
Comments D-4
Preconditions and Postconditions D-5
Assertions D-6
Java Interfaces D-7
Writing an Interface D-8
Implementing an Interface D-10
An Interface as a Data Type D-11
Generic Types Within an Interface D-12
Extending an Interface D-14
Interfaces Versus Abstract Classes D-15
Named Constants Within an Interface D-17
Choosing Classes D-18
Identifying Classes D-20
CRC Cards D-20
The Unified Modeling Language D-21
Reusing Classes D-23

E. Handling Exceptions E-1
The Basics E-2
Handling an Exception E-4
Postpone Handling: The throws Clause E-4
Handle It Now: The try-catch Blocks E-5
Multiple catch Blocks E-6
Throwing an Exception E-8
Programmer-Defined Exception Classes E-9
Inheritance and Exceptions E-14
The finally Block E-15

F. File Input and Output F-1
Preliminaries F-2
Why Files? F-2
Streams F-2
The Kinds of Files F-3
File Names F-3
Text Files F-3
Creating a Text File F-3
Reading a Text File F-8
Changing Existing Data in a Text File F-12
Defining a Method to Open a Stream F-13
Binary Files F-13
Creating a Binary File of Primitive Data F-14
Reading a Binary File of Primitive Data F-18
Strings in a Binary File F-20
Object Serialization F-23

G. Documentation and Programming Style G-1
Naming Variables and Classes G-1
Indenting G-2
Comments G-2
Single-Line Comments G-3
Comment Blocks G-3
When to Write Comments G-3
Java Documentation Comments G-3
Running javadoc G-5
Glossary Online
Index I-1