Data Structures: Abstraction and Design Using Java

TRY (FREE for 14 days), OR RENT this title: www.wileystudentchoice.com 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.

Table of Contents:
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 Linked List 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