Data Structures
Abstraction and Design Using Java
3rd Edition
Book
Paperback/Softback
684 pages
978-1-119-23914-7 (ISBN)
Description
Data Structures: Abstraction and Design Using Java, 3rd Edition, combines a strong emphasis on problem solving and software design with the study of data structures. The authors discuss applications of each data structure to motivate its study. After providing the specification (interface) and the implementation (a Java class), case studies that use the data structure to solve a significant problem are introduced.
More details
Other editions
New editions
Book
03/2021
4th Edition
Wiley
€137.50
Shipment within 15-20 days
Persons
Content
Preface iii
Chapter 1 Object-Oriented Programming and Class Hierarchies 1
1.1 ADTs, Interfaces, and the Java API 2
Interfaces 2
The implements Clause 5
Declaring a Variable of an Interface Type 6
Exercises for Section 1.1 6
1.2 Introduction to Object-Oriented Programming (OOP) 7
A Superclass and Subclass Example 8
Use of this. 9
Initializing Data Fields in a Subclass 10
The No-Parameter Constructor 11
Protected Visibility for Superclass Data Fields 11
Is-a versus Has-a Relationships 12
Exercises for Section 1.2 12
1.3 Method Overriding, Method Overloading, and Polymorphism 13
Method Overriding 13
Method Overloading 15
Polymorphism 17
Methods with Class Parameters 17
Exercises for Section 1.3 18
1.4 Abstract Classes 19
Referencing Actual Objects 21
Initializing Data Fields in an Abstract Class 21
Abstract Class Number and the Java Wrapper Classes 21
Summary of Features of Actual Classes, Abstract Classes, and Interfaces 22
Implementing Multiple Interfaces 23
Extending an Interface 23
Exercises for Section 1.4 23
1.5 Class Object and Casting 24
The Method toString 24
Operations Determined by Type of Reference Variable 25
Casting in a Class Hierarchy 26
Using instanceof to Guard a Casting Operation 27
The Class Class 29
Exercises for Section 1.5 29
1.6 A Java Inheritance Example-The Exception Class Hierarchy 29
Division by Zero 29
Array Index Out of Bounds 30
Null Pointer 31
The Exception Class Hierarchy 31
The Class Throwable 31
Checked and Unchecked Exceptions 32
Handling Exceptions to Recover from Errors 34
Using try-catch to Recover from an Error 34
Throwing an Exception When Recovery Is Not Obvious 35
Exercises for Section 1.6 36
1.7 Packages and Visibility 36
Packages 36
The No-Package-Declared Environment 37
Package Visibility 38
Visibility Supports Encapsulation 38
Exercises for Section 1.7 39
1.8 A Shape Class Hierarchy 39
Case Study: Processing Geometric Figures 40
Exercises for Section 1.8 45
Java Constructs Introduced in This Chapter 46
Java API Classes Introduced in This Chapter 46
User-Defined Interfaces and Classes in This Chapter 47
Quick-Check Exercises 47
Review Questions 47
Programming Projects 48
Answers to Quick-Check Exercises 51
Chapter 2 Lists and the Collections Framework 53
2.1 Algorithm Efficiency and Big-O 54
Big-O Notation 56
Formal Definition of Big-O 57
Summary of Notation 60
Comparing Performance 60
Algorithms with Exponential and Factorial Growth Rates 62
Exercises for Section 2.1 62
2.2 The List Interface and ArrayList Class 63
The ArrayList Class 64
Generic Collections 66
Exercises for Section 2.2 68
2.3 Applications of ArrayList 68
A Phone Directory Application 69
Exercises for Section 2.3 69
2.4 Implementation of an ArrayList Class 70
The Constructor for Class KWArrayList 71
The add(E anEntry) Method 72
The add(int index, E anEntry) Method 73
The set and get Methods 73
The remove Method 74
The reallocate Method 74
Performance of the KWArrayList Algorithms 74
Exercises for Section 2.4 75
2.5 Single-Linked Lists 75
A List Node 77
Connecting Nodes 78
A Single-Linked List Class 79
Inserting a Node in a List 79
Removing a Node 80
Completing the SingleLinkedList Class 81
The get and set Methods 82
The add Methods 82
Exercises for Section 2.5 83
2.6 Double-Linked Lists and Circular Lists 84
The Node Class 85
Inserting into a Double-Linked List 86
Removing from a Double-Linked List 86
A Double-Linked List Class 86
Circular Lists 87
Exercises for Section 2.6 88
2.7 The LinkedList Class and the Iterator, ListIterator, and Iterable Interfaces 89
The LinkedList Class 89
The Iterator 89
The Iterator Interface 90
The Enhanced for Loop 92
The ListIterator Interface 92
Comparison of Iterator and ListIterator 94
Conversion between a ListIterator and an Index 95
The Iterable Interface 95
Exercises for Section 2.7 95
2.8 Application of the LinkedList Class 96
Case Study: Maintaining an Ordered List 96
Testing Class OrderedList 101
Exercises for Section 2.8 103
2.9 Implementation of a Double-Linked List Class 103
Implementing the KWLinkedList Methods 104
A Class that Implements the ListIterator Interface 104
The Constructor 105
The hasNext and next Methods 106
The hasPrevious and previous Methods 107
The add Method 107
Inner Classes: Static and Nonstatic 111
Exercises for Section 2.9 111
2.10 The Collections Framework Design 112
The Collection Interface 112
Common Features of Collections 113
The AbstractCollection, AbstractList, and AbstractSequentialList Classes 113
The List and RandomAccess Interfaces (Advanced) 114
Exercises for Section 2.10 114
Java API Interfaces and Classes Introduced in this Chapter 116
User-Defined Interfaces and Classes in this Chapter 116
Quick-Check Exercises 116
Review Questions 117
Programming Projects 117
Answers to Quick-Check Exercises 119
Chapter 3 Testing and Debugging 121
3.1 Types of Testing 122
Preparations for Testing 124
Testing Tips for Program Systems 124
Exercises for Section 3.1 125
3.2 Specifying the Tests 125
Testing Boundary Conditions 125
Exercises for Section 3.2 126
3.3 Stubs and Drivers 127
Stubs 127
Preconditions and Postconditions 127
Drivers 128
Exercises for Section 3.3 128
3.4 The JUnit Test Framework 128
Exercises for Section 3.4 132
3.5 Test-Driven Development 132
Exercises for Section 3.5 136
3.6 Testing Interactive Programs in JUnit 137
ByteArrayInputStream 138
ByteArrayOutputStream 138
Exercises for Section 3.6 139
3.7 Debugging a Program 139
Using a Debugger 140
Exercises for Section 3.7 142
Java API Classes Introduced in This Chapter 144
User-Defined Interfaces and Classes in This Chapter 144
Quick-Check Exercises 144
Review Questions 144
Programming 144
Answers to Quick-Check Exercises 146
Chapter 4 Stacks and Queues 147
4.1 Stack Abstract Data Type 148
Specification of the Stack Abstract Data Type 148
Exercises for Section 4.1 150
4.2 Stack Applications 151
Case Study: Finding Palindromes 151
Exercises for Section 4.2 155
4.3 Implementing a Stack 155
Implementing a Stack with an ArrayList Component 155
Implementing a Stack as a Linked Data Structure 157
Comparison of Stack Implementations 158
Exercises for Section 4.3 159
4.4 Additional Stack Applications 159
Case Study: Evaluating Postfix Expressions 160
Case Study: Converting From Infix To Postfix 165
Case Study: Converting Expressions with Parentheses 173
Tying the Case Studies Together 176
Exercises for Section 4.4 176
4.5 Queue Abstract Data Type 177
A Print Queue 177
The Unsuitability of a "Print Stack" 178
A Queue of Customers 178
Using a Queue for Traversing a Multi-Branch Data Structure 178
Specification for a Queue Interface 179
Class LinkedList Implements the Queue Interface 179
Exercises for Section 4.5 180
4.6 Queue Applications 181
Case Study: Maintaining a Queue 181
Exercises for Section 4.6 186
4.7 Implementing the Queue Interface 187
Using a Double-Linked List to Implement the Queue Interface 187
Using a Single-Linked List to Implement the Queue Interface 187
Using a Circular Array to Implement the Queue Interface 189
Exercises for Section 4.7 196
4.8 The Deque Interface 196
Classes that Implement Deque 198
Using a Deque as a Queue 198
Using a Deque as a Stack 198
Exercises for Section 4.8 199
Java API Classes Introduced in This Chapter 200
User-Defined Interfaces and Classes in This Chapter 200
Quick-Check Exercises 201
Review Questions 202
Programming Projects 203
Answers to Quick-Check Exercises 207
Chapter 5 Recursion 211
5.1 Recursive Thinking 212
Steps to Design a Recursive Algorithm 214
Proving that a Recursive Method Is Correct 216
Tracing a Recursive Method 216
The Run-Time Stack and Activation Frames 217
Exercises for Section 5.1 218
5.2 Recursive Definitions of Mathematical Formulas 219
Tail Recursion versus Iteration 222
Efficiency of Recursion 223
Exercises for Section 5.2 225
5.3 Recursive Array Search 226
Design of a Recursive Linear Search Algorithm 226
Implementation of Linear Search 227
Design of a Binary Search Algorithm 228
Efficiency of Binary Search 229
The Comparable Interface 230
Implementation of Binary Search 230
Testing Binary Search 232
Method Arrays.binarySearch 233
Exercises for Section 5.3 233
5.4 Recursive Data Structures 233
Recursive Definition of a Linked List 234
Class LinkedListRec 234
Removing a List Node 236
Exercises for Section 5.4 237
5.5 Problem Solving with Recursion 238
Case Study: Towers of Hanoi 238
Case Study: Counting Cells in a Blob 243
Exercises for Section 5.5 247
5.6 Backtracking 247
Case Study: Finding a Path through a Maze 248
Exercises for Section 5.6 252
User-Defined Classes in This Chapter 253
Quick-Check Exercises 253
Review Questions 253
Programming Projects 254
Answers to Quick-Check Exercises 255
Chapter 6 Trees 257
6.1 Tree Terminology and Applications 258
Tree Terminology 258
Binary Trees 259
Some Types of Binary Trees 260
Full, Perfect, and Complete Binary Trees 263
General Trees 263
Exercises for Section 6.1 264
6.2 Tree Traversals 265
Visualizing Tree Traversals 266
Traversals of Binary Search Trees and Expression Trees 266
Exercises for Section 6.2 267
6.3 Implementing a BinaryTree Class 268
The Node Class 268
The BinaryTree Class 269
Exercises for Section 6.3 275
6.4 Java 8 Lambda Expressions and Functional Interfaces 276
Functional Interfaces 277
Passing a Lambda Expression as an Argument 279
A General Preorder Traversal Method 280
Using preOrderTraverse 280
Exercises for Section 6.4 281
6.5 Binary Search Trees 282
Overview of a Binary Search Tree 282
Performance 283
Interface SearchTree 283
The BinarySearchTree Class 283
Insertion into a Binary Search Tree 285
Removal from a Binary Search Tree 288
Testing a Binary Search Tree 293
Case Study: Writing an Index for a Term Paper 294
Exercises for Section 6.5 297
6.6 Heaps and Priority Queues 297
Inserting an Item into a Heap 298
Removing an Item from a Heap 298
Implementing a Heap 299
Priority Queues 302
The PriorityQueue Class 303
Using a Heap as the Basis of a Priority Queue 303
The Other Methods 306
Using a Comparator 306
The compare Method 306
Exercises for Section 6.6 307
6.7 Huffman Trees 308
Case Study: Building a Custom Huffman Tree 310
Exercises for Section 6.6 315
Java API Interfaces and Classes Introduced in This Chapter 316
User-Defined Interfaces and Classes in This Chapter 317
Quick-Check Exercises 317
Review Questions 318
Programming Projects 318
Answers to Quick-Check Exercises 320
Chapter 7 Sets and Maps 323
7.1 Sets and the Set Interface 324
The Set Abstraction 324
The Set Interface and Methods 325
Comparison of Lists and Sets 327
Exercises for Section 7.1 328
7.2 Maps and the Map Interface 329
The Map Hierarchy 330
The Map Interface 330
Exercises for Section 7.2 332
7.3 Hash Tables 333
Hash Codes and Index Calculation 333
Methods for Generating Hash Codes 334
Open Addressing 335
Table Wraparound and Search Termination 335
Traversing a Hash Table 337
Deleting an Item Using Open Addressing 337
Reducing Collisions by Expanding the Table Size 338
Reducing Collisions Using Quadratic Probing 338
Problems with Quadratic Probing 339
Chaining 340
Performance of Hash Tables 340
Exercises for Section 7.3 342
7.4 Implementing the Hash Table 344
Interface KWHashMap 344
Class Entry 344
Class HashtableOpen 345
Class HashtableChain 350
Testing the Hash Table Implementations 353
Exercises for Section 7.4 354
7.5 Implementation Considerations for Maps and Sets 354
Methods hashCode and equals 354
Implementing HashSetOpen 355
Writing HashSetOpen as an Adapter Class 355
Implementing the Java Map and Set Interfaces 356
Interface Map.Entry and Class AbstractMap.SimpleEntry 356
Creating a Set View of a Map 357
Method entrySet and Classes EntrySet and SetIterator 357
Classes TreeMap and TreeSet 358
Exercises for Section 7.5 359
7.6 Additional Applications of Maps 359
Case Study: Implementing a Cell Phone Contact List 359
Case Study: Completing the Huffman Coding Problem 361
Encoding the Huffman Tree 365
Exercises for Section 7.6 366
7.7 Navigable Sets and Maps 366
Application of a NavigableMap 368
Exercises for Section 7.7 370
Java API Interfaces and Classes Introduced in This Chapter 372
User-Defined Interfaces and Classes in This Chapter 372
Quick-Check Exercises 372
Review Questions 372
Programming Projects 373
Answers to Quick-Check Exercises 374
Chapter 8 Sorting 375
8.1 Using Java Sorting Methods 376
Exercises for Section 8.1 380
8.2 Selection Sort 380
Analysis of Selection Sort 381
Code for Selection Sort 381
Exercises for Section 8.2 383
8.3 Insertion Sort 383
Analysis of Insertion Sort 384
Code for Insertion Sort 385
Exercises for Section 8.3 386
8.4 Comparison of Quadratic Sorts 386
Comparisons versus Exchanges 387
Exercises for Section 8.4 388
8.5 Shell Sort: A Better Insertion Sort 388
Analysis of Shell Sort 389
Code for Shell Sort 390
Exercises for Section 8.5 391
8.6 Merge Sort 391
Analysis of Merge 392
Code for Merge 392
Algorithm for Merge Sort 394
Trace of Merge Sort Algorithm 394
Analysis of Merge Sort 394
Code for Merge Sort 395
Exercises for Section 8.6 396
8.7 Timsort 397
Merging Adjacent Sequences 400
Implementation 400
8.8 Heapsort 405
First Version of a Heapsort Algorithm 405
Revising the Heapsort Algorithm 405
Algorithm to Build a Heap 407
Analysis of Revised Heapsort Algorithm 407
Code for Heapsort 407
Exercises for Section 8.8 409
8.9 Quicksort 409
Algorithm for Quicksort 410
Analysis of Quicksort 411
Code for Quicksort 411
Algorithm for Partitioning 412
Code for partition 413
A Revised partition Algorithm 415
Code for Revised partition Method 416
Exercises for Section 8.9 417
8.10 Testing the Sort Algorithms 417
Exercises for Section 8.10 419
8.11 The Dutch National Flag Problem (Optional Topic) 419
Case Study: The Problem of the Dutch National Flag 419
Exercises for Section 8.11 422
Java Classes Introduced in This Chapter 423
User-Defined Interfaces and Classes in This Chapter 423
Quick-Check Exercises 424
Review Questions 424
Programming Projects 424
Answers to Quick-Check Exercises 425
Chapter 9 Self-Balancing Search Trees 427
9.1 Tree Balance and Rotation 428
Why Balance Is Important 428
Rotation 428
Algorithm for Rotation 429
Implementing Rotation 430
Exercises for Section 9.1 432
9.2 AVL Trees 432
Balancing a Left-Left Tree 432
Balancing a Left-Right Tree 433
Four Kinds of Critically Unbalanced Trees 434
Implementing an AVL Tree 436
Inserting into an AVL Tree 438
Removal from an AVL Tree 443
Performance of the AVL Tree 444
Exercises for Section 9.2 444
9.3 Red-Black Trees 445
Insertion into a Red-Black Tree 445
Removal from a Red-Black Tree 455
Performance of a Red-Black Tree 455
The TreeMap and TreeSet Classes 455
Exercises for Section 9.3 456
9.4 2-3 Trees 456
Searching a 2-3 Tree 457
Inserting an Item into a 2-3 Tree 457
Analysis of 2-3 Trees and Comparison with Balanced Binary Trees 461
Removal from a 2-3 Tree 461
Exercises for Section 9.4 462
9.5 B-Trees and 2-3-4 Trees 463
B-Trees 463
Implementing the B-Tree 464
Code for the insert Method 466
The insertIntoNode Method 467
The splitNode Method 468
Removal from a B-Tree 470
B+ Trees 471
2-3-4 Trees 471
Relating 2-3-4 Trees to Red-Black Trees 473
Exercises for Section 9.5 474
9.6 Skip-Lists 475
Skip-List Structure 475
Searching a Skip-List 476
Performance of a Skip-List Search 477
Inserting into a Skip-List 477
Increasing the Height of a Skip-List 477
Implementing a Skip-List 477
Searching a Skip-List 478
Insertion 479
Determining the Size of the Inserted Node 480
Completing the Insertion Process 480
Performance of a Skip-List 480
Exercises for Section 9.6 480
Java Classes Introduced in This Chapter 482
User-Defined Interfaces and Classes in This Chapter 482
Quick-Check Exercises 482
Review Questions 483
Programming Projects 484
Answers to Quick-Check Exercises 486
Chapter 10 Graphs 489
10.1 Graph Terminology 490
Visual Representation of Graphs 490
Directed and Undirected Graphs 491
Paths and Cycles 491
Relationship between Graphs and Trees 493
Graph Applications 493
Exercises for Section 10.1 494
10.2 The Graph ADT and Edge Class 494
Representing Vertices and Edges 495
Exercises for Section 10.2 496
10.3 Implementing the Graph ADT 496
Adjacency List 497
Adjacency Matrix 497
Overview of the Hierarchy 499
Class AbstractGraph 499
The ListGraph Class 501
The MatrixGraph Class 503
Comparing Implementations 504
The MapGraph Class 505
Exercises for Section 10.3 505
10.4 Traversals of Graphs 506
Breadth-First Search 506
Algorithm for Breadth-First Search 508
Depth-First Search 511
Exercises for Section 10.4 517
10.5 Applications of Graph Traversals 517
Case Study: Shortest Path through a Maze 517
Case Study: Topological Sort of a Graph 521
Exercises for Section 10.5 524
10.6 Algorithms Using Weighted Graphs 524
Finding the Shortest Path from a Vertex to All Other Vertices 524
Minimum Spanning Trees 528
Exercises for Section 10.6 531
User-Defined Classes and Interfaces in This Chapter 533
Quick-Check Exercises 533
Review Questions 534
Programming Projects 534
Answers to Quick-Check Exercises 536
Appendix A Introduction to Java 541
A.1 The Java Environment and Classes 542
The Java Virtual Machine 543
The Java Compiler 543
Classes and Objects 543
The Java API 543
The import Statement 544
Method main 544
Execution of a Java Program 545
Exercises for Section A.1 545
A.2 Primitive Data Types and Reference Variables 545
Primitive Data Types 545
Primitive-Type Variables 547
Primitive-Type Constants 547
Operators 547
Postfix and Prefix Increment 549
Type Compatibility and Conversion 549
Referencing Objects 550
Creating Objects 550
Exercises for Section A.2 551
A.3 Java Control Statements 551
Sequence and Compound Statements 551
Selection and Repetition Control 551
Nested if Statements 553
The switch Statement 555
Exercises for Section A.3 555
A.4 Methods and Class Math 555
The Instance Methods println and print 556
Call-by-Value Arguments 557
The Class Math 557
Escape Sequences 558
Exercises for Section A.4 559
A.5 The String, StringBuilder, StringBuffer, and StringJoiner Classes 559
The String Class 559
Strings Are Immutable 562
The Garbage Collector 562
Comparing Objects 562
The String.format Method 564
The Formatter Class 565
The String.split Method 565
Introduction to Regular Expressions 565
Matching One of a Group of Characters 566
Qualifiers 566
Defined Character Groups 567
Unicode Character Class Support 567
The StringBuilder and StringBuffer Classes 567
Java 8 StringJoiner Class 569
Exercises for Section A.5 570
A.6 Wrapper Classes for Primitive Types 571
Exercises for Section A.6 572
A.7 Defining Your Own Classes 573
Private Data Fields, Public Methods 576
Constructors 577
The No-Parameter Constructor 577
Modifier and Accessor Methods 578
Use of this. in a Method 578
The Method toString 578
The Method equals 579
Declaring Local Variables in Class Person 580
An Application that Uses Class Person 580
Objects as Arguments 581
Classes as Components of Other Classes 582
Java Documentation Style for Classes and Methods 582
Exercises for Section A.7 585
A.8 Arrays 585
Data Field length 587
Method Arrays.copyOf 588
Method System.arrayCopy 588
Array Data Fields 589
Array Results and Arguments 590
Arrays of Arrays 590
Exercises for Section A.8 593
A.9 Enumeration Types 594
Using Enumeration Types 595
Assigning Values to Enumeration Types 596
Exercises for Section A.9 596
A.10 I/O Using Streams, Class Scanner, and Class JOptionPane 596
The Scanner 597
Using a Scanner to Read from a File 599
Exceptions 599
Tokenized Input 599
Extracting Tokens Using Scanner.findInLine 600
Using a BufferedReader to Read from an Input Stream 600
Output Streams 600
Passing Arguments to Method main 600
Closing Streams 601
Try with Resources 601
A Complete File-Processing Application 601
Class InputStream and Character Codes (Optional) 603
The Default Character Coding (Optional) 603
UTF-8 (Optional) 604
Specifying a Character Encoding (Optional) 605
Input/Output Using Class JOptionPane 605
Converting Numeric Strings to Numbers 606
GUI Menus Using Method showOptionDialog 607
Exercises for Section A.10 607
A.11 Catching Exceptions 608
Catching and Handling Exceptions 608
Exercises for Section A.11 614
A.12 Throwing Exceptions 614
The throws Clause 615
The throw Statement 616
Exercises for Section A.12 619
Java Constructs Introduced in This Appendix 621
Java API Classes Introduced in This Appendix 622
User-Defined Interfaces and Classes in This Appendix 622
Quick-Check Exercises 622
Review Questions 622
Programming Projects 623
Answer to Quick-Check Exercises 624
Appendix B Overview of UML 625
B.1 The Class Diagram 626
Representing Classes and Interfaces 626
Generalization 629
Inner or Nested Classes 629
Association 629
Aggregation and Composition 630
Generic Classes 631
B.2 Sequence Diagrams 631
Time Axis 632
Objects 633
Life Lines 633
Activation Bars 633
Messages 633
Use of Notes 633
Glossary 635
Index 643
Chapter 1 Object-Oriented Programming and Class Hierarchies 1
1.1 ADTs, Interfaces, and the Java API 2
Interfaces 2
The implements Clause 5
Declaring a Variable of an Interface Type 6
Exercises for Section 1.1 6
1.2 Introduction to Object-Oriented Programming (OOP) 7
A Superclass and Subclass Example 8
Use of this. 9
Initializing Data Fields in a Subclass 10
The No-Parameter Constructor 11
Protected Visibility for Superclass Data Fields 11
Is-a versus Has-a Relationships 12
Exercises for Section 1.2 12
1.3 Method Overriding, Method Overloading, and Polymorphism 13
Method Overriding 13
Method Overloading 15
Polymorphism 17
Methods with Class Parameters 17
Exercises for Section 1.3 18
1.4 Abstract Classes 19
Referencing Actual Objects 21
Initializing Data Fields in an Abstract Class 21
Abstract Class Number and the Java Wrapper Classes 21
Summary of Features of Actual Classes, Abstract Classes, and Interfaces 22
Implementing Multiple Interfaces 23
Extending an Interface 23
Exercises for Section 1.4 23
1.5 Class Object and Casting 24
The Method toString 24
Operations Determined by Type of Reference Variable 25
Casting in a Class Hierarchy 26
Using instanceof to Guard a Casting Operation 27
The Class Class 29
Exercises for Section 1.5 29
1.6 A Java Inheritance Example-The Exception Class Hierarchy 29
Division by Zero 29
Array Index Out of Bounds 30
Null Pointer 31
The Exception Class Hierarchy 31
The Class Throwable 31
Checked and Unchecked Exceptions 32
Handling Exceptions to Recover from Errors 34
Using try-catch to Recover from an Error 34
Throwing an Exception When Recovery Is Not Obvious 35
Exercises for Section 1.6 36
1.7 Packages and Visibility 36
Packages 36
The No-Package-Declared Environment 37
Package Visibility 38
Visibility Supports Encapsulation 38
Exercises for Section 1.7 39
1.8 A Shape Class Hierarchy 39
Case Study: Processing Geometric Figures 40
Exercises for Section 1.8 45
Java Constructs Introduced in This Chapter 46
Java API Classes Introduced in This Chapter 46
User-Defined Interfaces and Classes in This Chapter 47
Quick-Check Exercises 47
Review Questions 47
Programming Projects 48
Answers to Quick-Check Exercises 51
Chapter 2 Lists and the Collections Framework 53
2.1 Algorithm Efficiency and Big-O 54
Big-O Notation 56
Formal Definition of Big-O 57
Summary of Notation 60
Comparing Performance 60
Algorithms with Exponential and Factorial Growth Rates 62
Exercises for Section 2.1 62
2.2 The List Interface and ArrayList Class 63
The ArrayList Class 64
Generic Collections 66
Exercises for Section 2.2 68
2.3 Applications of ArrayList 68
A Phone Directory Application 69
Exercises for Section 2.3 69
2.4 Implementation of an ArrayList Class 70
The Constructor for Class KWArrayList 71
The add(E anEntry) Method 72
The add(int index, E anEntry) Method 73
The set and get Methods 73
The remove Method 74
The reallocate Method 74
Performance of the KWArrayList Algorithms 74
Exercises for Section 2.4 75
2.5 Single-Linked Lists 75
A List Node 77
Connecting Nodes 78
A Single-Linked List Class 79
Inserting a Node in a List 79
Removing a Node 80
Completing the SingleLinkedList Class 81
The get and set Methods 82
The add Methods 82
Exercises for Section 2.5 83
2.6 Double-Linked Lists and Circular Lists 84
The Node Class 85
Inserting into a Double-Linked List 86
Removing from a Double-Linked List 86
A Double-Linked List Class 86
Circular Lists 87
Exercises for Section 2.6 88
2.7 The LinkedList Class and the Iterator, ListIterator, and Iterable Interfaces 89
The LinkedList Class 89
The Iterator 89
The Iterator Interface 90
The Enhanced for Loop 92
The ListIterator Interface 92
Comparison of Iterator and ListIterator 94
Conversion between a ListIterator and an Index 95
The Iterable Interface 95
Exercises for Section 2.7 95
2.8 Application of the LinkedList Class 96
Case Study: Maintaining an Ordered List 96
Testing Class OrderedList 101
Exercises for Section 2.8 103
2.9 Implementation of a Double-Linked List Class 103
Implementing the KWLinkedList Methods 104
A Class that Implements the ListIterator Interface 104
The Constructor 105
The hasNext and next Methods 106
The hasPrevious and previous Methods 107
The add Method 107
Inner Classes: Static and Nonstatic 111
Exercises for Section 2.9 111
2.10 The Collections Framework Design 112
The Collection Interface 112
Common Features of Collections 113
The AbstractCollection, AbstractList, and AbstractSequentialList Classes 113
The List and RandomAccess Interfaces (Advanced) 114
Exercises for Section 2.10 114
Java API Interfaces and Classes Introduced in this Chapter 116
User-Defined Interfaces and Classes in this Chapter 116
Quick-Check Exercises 116
Review Questions 117
Programming Projects 117
Answers to Quick-Check Exercises 119
Chapter 3 Testing and Debugging 121
3.1 Types of Testing 122
Preparations for Testing 124
Testing Tips for Program Systems 124
Exercises for Section 3.1 125
3.2 Specifying the Tests 125
Testing Boundary Conditions 125
Exercises for Section 3.2 126
3.3 Stubs and Drivers 127
Stubs 127
Preconditions and Postconditions 127
Drivers 128
Exercises for Section 3.3 128
3.4 The JUnit Test Framework 128
Exercises for Section 3.4 132
3.5 Test-Driven Development 132
Exercises for Section 3.5 136
3.6 Testing Interactive Programs in JUnit 137
ByteArrayInputStream 138
ByteArrayOutputStream 138
Exercises for Section 3.6 139
3.7 Debugging a Program 139
Using a Debugger 140
Exercises for Section 3.7 142
Java API Classes Introduced in This Chapter 144
User-Defined Interfaces and Classes in This Chapter 144
Quick-Check Exercises 144
Review Questions 144
Programming 144
Answers to Quick-Check Exercises 146
Chapter 4 Stacks and Queues 147
4.1 Stack Abstract Data Type 148
Specification of the Stack Abstract Data Type 148
Exercises for Section 4.1 150
4.2 Stack Applications 151
Case Study: Finding Palindromes 151
Exercises for Section 4.2 155
4.3 Implementing a Stack 155
Implementing a Stack with an ArrayList Component 155
Implementing a Stack as a Linked Data Structure 157
Comparison of Stack Implementations 158
Exercises for Section 4.3 159
4.4 Additional Stack Applications 159
Case Study: Evaluating Postfix Expressions 160
Case Study: Converting From Infix To Postfix 165
Case Study: Converting Expressions with Parentheses 173
Tying the Case Studies Together 176
Exercises for Section 4.4 176
4.5 Queue Abstract Data Type 177
A Print Queue 177
The Unsuitability of a "Print Stack" 178
A Queue of Customers 178
Using a Queue for Traversing a Multi-Branch Data Structure 178
Specification for a Queue Interface 179
Class LinkedList Implements the Queue Interface 179
Exercises for Section 4.5 180
4.6 Queue Applications 181
Case Study: Maintaining a Queue 181
Exercises for Section 4.6 186
4.7 Implementing the Queue Interface 187
Using a Double-Linked List to Implement the Queue Interface 187
Using a Single-Linked List to Implement the Queue Interface 187
Using a Circular Array to Implement the Queue Interface 189
Exercises for Section 4.7 196
4.8 The Deque Interface 196
Classes that Implement Deque 198
Using a Deque as a Queue 198
Using a Deque as a Stack 198
Exercises for Section 4.8 199
Java API Classes Introduced in This Chapter 200
User-Defined Interfaces and Classes in This Chapter 200
Quick-Check Exercises 201
Review Questions 202
Programming Projects 203
Answers to Quick-Check Exercises 207
Chapter 5 Recursion 211
5.1 Recursive Thinking 212
Steps to Design a Recursive Algorithm 214
Proving that a Recursive Method Is Correct 216
Tracing a Recursive Method 216
The Run-Time Stack and Activation Frames 217
Exercises for Section 5.1 218
5.2 Recursive Definitions of Mathematical Formulas 219
Tail Recursion versus Iteration 222
Efficiency of Recursion 223
Exercises for Section 5.2 225
5.3 Recursive Array Search 226
Design of a Recursive Linear Search Algorithm 226
Implementation of Linear Search 227
Design of a Binary Search Algorithm 228
Efficiency of Binary Search 229
The Comparable Interface 230
Implementation of Binary Search 230
Testing Binary Search 232
Method Arrays.binarySearch 233
Exercises for Section 5.3 233
5.4 Recursive Data Structures 233
Recursive Definition of a Linked List 234
Class LinkedListRec 234
Removing a List Node 236
Exercises for Section 5.4 237
5.5 Problem Solving with Recursion 238
Case Study: Towers of Hanoi 238
Case Study: Counting Cells in a Blob 243
Exercises for Section 5.5 247
5.6 Backtracking 247
Case Study: Finding a Path through a Maze 248
Exercises for Section 5.6 252
User-Defined Classes in This Chapter 253
Quick-Check Exercises 253
Review Questions 253
Programming Projects 254
Answers to Quick-Check Exercises 255
Chapter 6 Trees 257
6.1 Tree Terminology and Applications 258
Tree Terminology 258
Binary Trees 259
Some Types of Binary Trees 260
Full, Perfect, and Complete Binary Trees 263
General Trees 263
Exercises for Section 6.1 264
6.2 Tree Traversals 265
Visualizing Tree Traversals 266
Traversals of Binary Search Trees and Expression Trees 266
Exercises for Section 6.2 267
6.3 Implementing a BinaryTree Class 268
The Node Class 268
The BinaryTree Class 269
Exercises for Section 6.3 275
6.4 Java 8 Lambda Expressions and Functional Interfaces 276
Functional Interfaces 277
Passing a Lambda Expression as an Argument 279
A General Preorder Traversal Method 280
Using preOrderTraverse 280
Exercises for Section 6.4 281
6.5 Binary Search Trees 282
Overview of a Binary Search Tree 282
Performance 283
Interface SearchTree 283
The BinarySearchTree Class 283
Insertion into a Binary Search Tree 285
Removal from a Binary Search Tree 288
Testing a Binary Search Tree 293
Case Study: Writing an Index for a Term Paper 294
Exercises for Section 6.5 297
6.6 Heaps and Priority Queues 297
Inserting an Item into a Heap 298
Removing an Item from a Heap 298
Implementing a Heap 299
Priority Queues 302
The PriorityQueue Class 303
Using a Heap as the Basis of a Priority Queue 303
The Other Methods 306
Using a Comparator 306
The compare Method 306
Exercises for Section 6.6 307
6.7 Huffman Trees 308
Case Study: Building a Custom Huffman Tree 310
Exercises for Section 6.6 315
Java API Interfaces and Classes Introduced in This Chapter 316
User-Defined Interfaces and Classes in This Chapter 317
Quick-Check Exercises 317
Review Questions 318
Programming Projects 318
Answers to Quick-Check Exercises 320
Chapter 7 Sets and Maps 323
7.1 Sets and the Set Interface 324
The Set Abstraction 324
The Set Interface and Methods 325
Comparison of Lists and Sets 327
Exercises for Section 7.1 328
7.2 Maps and the Map Interface 329
The Map Hierarchy 330
The Map Interface 330
Exercises for Section 7.2 332
7.3 Hash Tables 333
Hash Codes and Index Calculation 333
Methods for Generating Hash Codes 334
Open Addressing 335
Table Wraparound and Search Termination 335
Traversing a Hash Table 337
Deleting an Item Using Open Addressing 337
Reducing Collisions by Expanding the Table Size 338
Reducing Collisions Using Quadratic Probing 338
Problems with Quadratic Probing 339
Chaining 340
Performance of Hash Tables 340
Exercises for Section 7.3 342
7.4 Implementing the Hash Table 344
Interface KWHashMap 344
Class Entry 344
Class HashtableOpen 345
Class HashtableChain 350
Testing the Hash Table Implementations 353
Exercises for Section 7.4 354
7.5 Implementation Considerations for Maps and Sets 354
Methods hashCode and equals 354
Implementing HashSetOpen 355
Writing HashSetOpen as an Adapter Class 355
Implementing the Java Map and Set Interfaces 356
Interface Map.Entry and Class AbstractMap.SimpleEntry 356
Creating a Set View of a Map 357
Method entrySet and Classes EntrySet and SetIterator 357
Classes TreeMap and TreeSet 358
Exercises for Section 7.5 359
7.6 Additional Applications of Maps 359
Case Study: Implementing a Cell Phone Contact List 359
Case Study: Completing the Huffman Coding Problem 361
Encoding the Huffman Tree 365
Exercises for Section 7.6 366
7.7 Navigable Sets and Maps 366
Application of a NavigableMap 368
Exercises for Section 7.7 370
Java API Interfaces and Classes Introduced in This Chapter 372
User-Defined Interfaces and Classes in This Chapter 372
Quick-Check Exercises 372
Review Questions 372
Programming Projects 373
Answers to Quick-Check Exercises 374
Chapter 8 Sorting 375
8.1 Using Java Sorting Methods 376
Exercises for Section 8.1 380
8.2 Selection Sort 380
Analysis of Selection Sort 381
Code for Selection Sort 381
Exercises for Section 8.2 383
8.3 Insertion Sort 383
Analysis of Insertion Sort 384
Code for Insertion Sort 385
Exercises for Section 8.3 386
8.4 Comparison of Quadratic Sorts 386
Comparisons versus Exchanges 387
Exercises for Section 8.4 388
8.5 Shell Sort: A Better Insertion Sort 388
Analysis of Shell Sort 389
Code for Shell Sort 390
Exercises for Section 8.5 391
8.6 Merge Sort 391
Analysis of Merge 392
Code for Merge 392
Algorithm for Merge Sort 394
Trace of Merge Sort Algorithm 394
Analysis of Merge Sort 394
Code for Merge Sort 395
Exercises for Section 8.6 396
8.7 Timsort 397
Merging Adjacent Sequences 400
Implementation 400
8.8 Heapsort 405
First Version of a Heapsort Algorithm 405
Revising the Heapsort Algorithm 405
Algorithm to Build a Heap 407
Analysis of Revised Heapsort Algorithm 407
Code for Heapsort 407
Exercises for Section 8.8 409
8.9 Quicksort 409
Algorithm for Quicksort 410
Analysis of Quicksort 411
Code for Quicksort 411
Algorithm for Partitioning 412
Code for partition 413
A Revised partition Algorithm 415
Code for Revised partition Method 416
Exercises for Section 8.9 417
8.10 Testing the Sort Algorithms 417
Exercises for Section 8.10 419
8.11 The Dutch National Flag Problem (Optional Topic) 419
Case Study: The Problem of the Dutch National Flag 419
Exercises for Section 8.11 422
Java Classes Introduced in This Chapter 423
User-Defined Interfaces and Classes in This Chapter 423
Quick-Check Exercises 424
Review Questions 424
Programming Projects 424
Answers to Quick-Check Exercises 425
Chapter 9 Self-Balancing Search Trees 427
9.1 Tree Balance and Rotation 428
Why Balance Is Important 428
Rotation 428
Algorithm for Rotation 429
Implementing Rotation 430
Exercises for Section 9.1 432
9.2 AVL Trees 432
Balancing a Left-Left Tree 432
Balancing a Left-Right Tree 433
Four Kinds of Critically Unbalanced Trees 434
Implementing an AVL Tree 436
Inserting into an AVL Tree 438
Removal from an AVL Tree 443
Performance of the AVL Tree 444
Exercises for Section 9.2 444
9.3 Red-Black Trees 445
Insertion into a Red-Black Tree 445
Removal from a Red-Black Tree 455
Performance of a Red-Black Tree 455
The TreeMap and TreeSet Classes 455
Exercises for Section 9.3 456
9.4 2-3 Trees 456
Searching a 2-3 Tree 457
Inserting an Item into a 2-3 Tree 457
Analysis of 2-3 Trees and Comparison with Balanced Binary Trees 461
Removal from a 2-3 Tree 461
Exercises for Section 9.4 462
9.5 B-Trees and 2-3-4 Trees 463
B-Trees 463
Implementing the B-Tree 464
Code for the insert Method 466
The insertIntoNode Method 467
The splitNode Method 468
Removal from a B-Tree 470
B+ Trees 471
2-3-4 Trees 471
Relating 2-3-4 Trees to Red-Black Trees 473
Exercises for Section 9.5 474
9.6 Skip-Lists 475
Skip-List Structure 475
Searching a Skip-List 476
Performance of a Skip-List Search 477
Inserting into a Skip-List 477
Increasing the Height of a Skip-List 477
Implementing a Skip-List 477
Searching a Skip-List 478
Insertion 479
Determining the Size of the Inserted Node 480
Completing the Insertion Process 480
Performance of a Skip-List 480
Exercises for Section 9.6 480
Java Classes Introduced in This Chapter 482
User-Defined Interfaces and Classes in This Chapter 482
Quick-Check Exercises 482
Review Questions 483
Programming Projects 484
Answers to Quick-Check Exercises 486
Chapter 10 Graphs 489
10.1 Graph Terminology 490
Visual Representation of Graphs 490
Directed and Undirected Graphs 491
Paths and Cycles 491
Relationship between Graphs and Trees 493
Graph Applications 493
Exercises for Section 10.1 494
10.2 The Graph ADT and Edge Class 494
Representing Vertices and Edges 495
Exercises for Section 10.2 496
10.3 Implementing the Graph ADT 496
Adjacency List 497
Adjacency Matrix 497
Overview of the Hierarchy 499
Class AbstractGraph 499
The ListGraph Class 501
The MatrixGraph Class 503
Comparing Implementations 504
The MapGraph Class 505
Exercises for Section 10.3 505
10.4 Traversals of Graphs 506
Breadth-First Search 506
Algorithm for Breadth-First Search 508
Depth-First Search 511
Exercises for Section 10.4 517
10.5 Applications of Graph Traversals 517
Case Study: Shortest Path through a Maze 517
Case Study: Topological Sort of a Graph 521
Exercises for Section 10.5 524
10.6 Algorithms Using Weighted Graphs 524
Finding the Shortest Path from a Vertex to All Other Vertices 524
Minimum Spanning Trees 528
Exercises for Section 10.6 531
User-Defined Classes and Interfaces in This Chapter 533
Quick-Check Exercises 533
Review Questions 534
Programming Projects 534
Answers to Quick-Check Exercises 536
Appendix A Introduction to Java 541
A.1 The Java Environment and Classes 542
The Java Virtual Machine 543
The Java Compiler 543
Classes and Objects 543
The Java API 543
The import Statement 544
Method main 544
Execution of a Java Program 545
Exercises for Section A.1 545
A.2 Primitive Data Types and Reference Variables 545
Primitive Data Types 545
Primitive-Type Variables 547
Primitive-Type Constants 547
Operators 547
Postfix and Prefix Increment 549
Type Compatibility and Conversion 549
Referencing Objects 550
Creating Objects 550
Exercises for Section A.2 551
A.3 Java Control Statements 551
Sequence and Compound Statements 551
Selection and Repetition Control 551
Nested if Statements 553
The switch Statement 555
Exercises for Section A.3 555
A.4 Methods and Class Math 555
The Instance Methods println and print 556
Call-by-Value Arguments 557
The Class Math 557
Escape Sequences 558
Exercises for Section A.4 559
A.5 The String, StringBuilder, StringBuffer, and StringJoiner Classes 559
The String Class 559
Strings Are Immutable 562
The Garbage Collector 562
Comparing Objects 562
The String.format Method 564
The Formatter Class 565
The String.split Method 565
Introduction to Regular Expressions 565
Matching One of a Group of Characters 566
Qualifiers 566
Defined Character Groups 567
Unicode Character Class Support 567
The StringBuilder and StringBuffer Classes 567
Java 8 StringJoiner Class 569
Exercises for Section A.5 570
A.6 Wrapper Classes for Primitive Types 571
Exercises for Section A.6 572
A.7 Defining Your Own Classes 573
Private Data Fields, Public Methods 576
Constructors 577
The No-Parameter Constructor 577
Modifier and Accessor Methods 578
Use of this. in a Method 578
The Method toString 578
The Method equals 579
Declaring Local Variables in Class Person 580
An Application that Uses Class Person 580
Objects as Arguments 581
Classes as Components of Other Classes 582
Java Documentation Style for Classes and Methods 582
Exercises for Section A.7 585
A.8 Arrays 585
Data Field length 587
Method Arrays.copyOf 588
Method System.arrayCopy 588
Array Data Fields 589
Array Results and Arguments 590
Arrays of Arrays 590
Exercises for Section A.8 593
A.9 Enumeration Types 594
Using Enumeration Types 595
Assigning Values to Enumeration Types 596
Exercises for Section A.9 596
A.10 I/O Using Streams, Class Scanner, and Class JOptionPane 596
The Scanner 597
Using a Scanner to Read from a File 599
Exceptions 599
Tokenized Input 599
Extracting Tokens Using Scanner.findInLine 600
Using a BufferedReader to Read from an Input Stream 600
Output Streams 600
Passing Arguments to Method main 600
Closing Streams 601
Try with Resources 601
A Complete File-Processing Application 601
Class InputStream and Character Codes (Optional) 603
The Default Character Coding (Optional) 603
UTF-8 (Optional) 604
Specifying a Character Encoding (Optional) 605
Input/Output Using Class JOptionPane 605
Converting Numeric Strings to Numbers 606
GUI Menus Using Method showOptionDialog 607
Exercises for Section A.10 607
A.11 Catching Exceptions 608
Catching and Handling Exceptions 608
Exercises for Section A.11 614
A.12 Throwing Exceptions 614
The throws Clause 615
The throw Statement 616
Exercises for Section A.12 619
Java Constructs Introduced in This Appendix 621
Java API Classes Introduced in This Appendix 622
User-Defined Interfaces and Classes in This Appendix 622
Quick-Check Exercises 622
Review Questions 622
Programming Projects 623
Answer to Quick-Check Exercises 624
Appendix B Overview of UML 625
B.1 The Class Diagram 626
Representing Classes and Interfaces 626
Generalization 629
Inner or Nested Classes 629
Association 629
Aggregation and Composition 630
Generic Classes 631
B.2 Sequence Diagrams 631
Time Axis 632
Objects 633
Life Lines 633
Activation Bars 633
Messages 633
Use of Notes 633
Glossary 635
Index 643