Data Structures 3rd edition

Preface iii Chapter 1 Object-Oriented Programming and Class Hierarchies 1 1.1 ADTs, Interfaces, and the Java API 2 Interfaces 3 The implements Clause 6 Declaring a Variable of an Interface Type 7 Exercises for Section 1.1 7 1.2 Introduction to Object-Oriented Programming 8 A Superclass and Subclass Example 9 Use of this 10 Initializing Data Fields in a Subclass 11 The No-Parameter Constructor 12 Protected Visibility for Superclass Data Fields 13 Is-a Versus Has-a Relationships 13 Exercises for Section 1.2 14 1.3 Method Overriding, Method Overloading, and Polymorphism 14 Method Overriding 14 Method Overloading 16 Polymorphism 19 Methods with Class Parameters 20 Exercises for Section 1.3 20 1.4 Abstract Classes 21 Referencing Actual Objects 24 Initializing Data Fields in an Abstract Class 24 Abstract Class Number and the Java Wrapper Classes 24 Summary of Features of Actual Classes, Abstract Classes, and Interfaces 25 Implementing Multiple Interfaces 26 Extending an Interface 26 Exercises for Section 1.4 27 1.5 Class Object and Casting 27 The Method to String 28 Operations Determined by Type of Reference Variable 28 Casting in a Class Hierarchy 29 Using instance of to Guard a Casting Operation 31 The Class Class 33 Exercises for Section 1.5 33 1.6 A Java Inheritance Example The Exception Class Hierarchy 34 Division by Zero 34 Array Index Out of Bounds 35 Null Pointer 35 The Exception Class Hierarchy 36 The Class Throwable 36 Checked and Unchecked Exceptions 37 Handling Exceptions to Recover from Errors 39 Using try-catch to Recover from an Error 40 Throwing an Exception When Recovery Is Not Obvious 41 Exercises for Section 1.6 42 1.7 Packages and Visibility 42 Packages 42 The No-Package-Declared Environment 43 Package Visibility 43 Visibility Supports Encapsulation 44 Exercises for Section 1.7 45 1.8 A Shape Class Hierarchy 46 Case Study: Processing Geometric Figures 46 Exercises for Section 1.8 52 Chapter Review, Exercises, and Programming Projects 52 Chapter 2 Lists and the Collections Framework 61 2.1 The List Interface and ArrayList Class 62 The ArrayList Class 63 Generic Collections 66 Specification of the ArrayList Class 68 Exercises for Section 2.1 69 2.2 Applications of ArrayList 69 A Phone Directory Application 70 Exercises for Section 2.2 70 2.3 Implementation of an ArrayList Class 71 The Constructor for Class KWArrayList 72 The add(E anEntry) Method 73 The add(int index, E anEntry) Method 74 The set and get Methods 75 The remove Method 75 The reallocate Method 76 Implementing KWArray List as a Collection of Objects 76 The Vector Class 77 Exercises for Section 2.3 77 2.4 Algorithm Efficiency and Big-O 77 Big-O Notation 80 Formal Definition of Big-O 81 Summary of Notation 83 Comparing Performance 84 Algorithms with Exponential and Factorial Growth Rates 86 Performance of the KWArray List Algorithms 86 Exercises for Section 2.4 87 2.5 Single-Linked Lists 88 A List Node 90 Connecting Nodes 92 A Single-Linked List Class 92 Inserting a Node in a List 93 Removing a Node 93 Traversing a Single-Linked List 95 Completing the SingleLinked List Class 95 The get and set Methods 96 The add Methods 97 Exercises for Section 2.5 98 2.6 Double-Linked Lists and Circular Lists 99 Inserting into a Double-Linked List 101 Removing from a Double-Linked List 101 A Double-Linked List Class 102 Circular Lists 102 Exercises for Section 2.6 103 2.7 The Linked List Class and the Iterator, ListIterator, and Iterable Interfaces 104 The LinkedList Class 104 The Iterator 105 The Iterator Interface 106 The ListIterator Interface 108 Comparison of Iterator and ListIterator 110 Conversion between a ListIterator and an Index 110 The Enhanced for Statement 110 The Iterable Interface 111 Exercises for Section 2.7 112 2.8 Implementation of a Double-Linked List Class 112 Implementing the KWLinkedList Methods 113 A Class that Implements the ListIterator Interface 114 The Constructor 114 The hasNext and next Methods 115 The hasPrevious and previous Methods 116 The add Method 117 Inner Classes: Static and Nonstatic 120 Exercises for Section 2.8 121 2.9 The Collections Framework Design 121 The Collection Interface 121 Common Features of Collections 122 The AbstractCollection, AbstractList, and AbstractSequentialList Classes 123 The List and RandomAccess Interfaces (Advanced) 124 Exercises for Section 2.9 124 2.10 Application of the LinkedList Class 125 Case Study: Maintaining an Ordered List 125 Exercises for Section 2.10 130 2.11 Testing 130 Preparations for Testing 132 Testing Tips for Program Systems 133 Developing the Test Data 133 Testing Boundary Conditions 134 Stubs 136 Preconditions and Postconditions 137 Drivers 137 Using JUnit and Debuggers 138 Testing Class OrderedList 138 Case Study: Maintaining an Ordered List (continued) 138 Exercises for Section 2.11 140 Chapter Review, Exercises, and Programming Projects 141 Chapter 3 Stacks 149 3.1 Stack Abstract Data Type 150 Specification of the Stack Abstract Data Type 150 Exercises for Section 3.1 152 3.2 Stack Applications 153 Case Study: Finding Palindromes 153 Case Study: Testing Expressions for Balanced Parentheses 156 Exercises for Section 3.2 161 3.3 Implementing a Stack 162 Implementing a Stack as an Extension of Vector 162 Implementing a Stack with a List Component 163 Implementing a Stack Using an Array 165 Implementing a Stack as a Linked Data Structure 167 Comparison of Stack Implementations 169 Exercises for Section 3.3 169 3.4 Additional Stack Applications 170 Case Study: Evaluating Postfix Expressions 171 Case Study: Converting from Infix to Postfix 176 Case Study: Converting Expressions with Parentheses 185 Tying the Case Studies Together 188 Exercises for Section 3.4 188 Chapter Review, Exercises, and Programming Projects 189 Chapter 4 Queues 195 4.1 Queue Abstract Data Type 196 A Print Queue 196 The Unsuitability of a Print Stack 197 A Queue of Customers 197 Using a Queue for Traversing a Multi-Branch Data Structure 197 Specification for a Queue Interface 198 Class LinkedList Implements the Queue Interface 199 Exercises for Section 4.1 199 4.2 Maintaining a Queue of Customers 200 Case Study: Maintaining a Queue 200 Exercises for Section 4.2 205 4.3 Implementing the Queue Interface 206 Using a Double-Linked List to Implement the Queue Interface 206 Using a Single-Linked List to Implement the Queue Interface 207 Using a Circular Array to Implement the Queue Interface 209 Comparing the Three Implementations 216 Exercises for Section 4.3 217 4.4 The Deque Interface 217 Classes that Implement Deque 217 Using a Deque as a Queue 219 Using a Deque as a Stack 219 Exercises for Section 4.4 220 4.5 Simulating Waiting Lines Using Queues 221 Case Study: Simulate a Strategy for Serving Airline Passengers 221 Exercises for Section 4.5 236 Chapter Review, Exercises, and Programming Projects 237 Chapter 5 Recursion 243 5.1 Recursive Thinking 244 Steps to Design a Recursive Algorithm 246 Proving that a Recursive Method Is Correct 248 Tracing a Recursive Method 249 The Run-Time Stack and Activation Frames 249 Exercises for Section 5.1 251 5.2 Recursive Definitions of Mathematical Formulas 252 Recursion versus Iteration 255 Efficiency of Recursion 256 Exercises for Section 5.2 259 5.3 Recursive Array Search 259 Design of a Recursive Linear Search Algorithm 260 Implementation of Linear Search 260 Design of a Binary Search Algorithm 262 Efficiency of Binary Search 262 The Comparable Interface 263 Implementation of Binary Search 264 Testing Binary Search 265 Method Arrays.binarySearch 265 Exercises for Section 5.3 267 5.4 Recursive Data Structures 267 Recursive Definition of a Linked List 267 Class LinkedListRec 268 Removing a List Node 271 Exercises for Section 5.4 272 5.5 Problem Solving with Recursion 273 Case Study: Towers of Hanoi 273 Case Study: Counting Cells in a Blob 278 Exercises for Section 5.5 283 5.6 Backtracking 283 Case Study: Finding a Path through a Maze 284 Exercises for Section 5.6 288 Chapter Review, Exercises, and Programming Projects 289 Chapter 6 Trees 295 6.1 Tree Terminology and Applications 297 Tree Terminology 297 Binary Trees 298 Some Types of Binary Trees 298 Full, Perfect, and Complete Binary Trees 301 General Trees 301 Exercises for Section 6.1 303 6.2 Tree Traversals 304 Visualizing Tree Traversals 304 Traversals of Binary Search Trees and Expression Trees 305 Exercises for Section 6.2 306 6.3 Implementing a BinaryTree Class 307 The Node Class 307 The BinaryTree Class 308 Exercises for Section 6.3 314 6.4 Binary Search Trees 315 Overview of a Binary Search Tree 315 Performance 316 Interface SearchTree 317 The BinarySearchTree Class 317 Insertion into a Binary Search Tree 319 Removal from a Binary Search Tree 323 Testing a Binary Search Tree 328 Case Study: Writing an Index for a Term Paper 329 Exercises for Section 6.4 331 6.5 Heaps and Priority Queues 332 Inserting an Item into a Heap 333 Removing an Item from a Heap 333 Implementing a Heap 334 Priority Queues 337 The PriorityQueue Class 338 Using a Heap as the Basis of a Priority Queue 338 The Other Methods 341 Using a Comparator 342 The compare Method 342 Exercises for Section 6.5 344 6.6 Huffman Trees 345 Case Study: Building a Custom Huffman Tree 346 Exercises for Section 6.6 353 Chapter Review, Exercises, and Programming Projects 354 Chapter 7 Sets and Maps 361 7.1 Sets and the Set Interface 362 The Set Abstraction 363 The Set Interface and Methods 364 Comparison of Lists and Sets 366 Exercises for Section 7.1 366 7.2 Maps and the Map Interface 367 The Map Hierarchy 368 The Map Interface 369 Exercises for Section 7.2 371 7.3 Hash Tables 372 Hash Codes and Index Calculation 372 Methods for Generating Hash Codes 373 Open Addressing 374 Table Wraparound and Search Termination 375 Traversing a Hash Table 376 Deleting an Item Using Open Addressing 377 Reducing Collisions by Expanding the Table Size 377 Reducing Collisions Using Quadratic Probing 378 Problems with Quadratic Probing 378 Chaining 379 Performance of Hash Tables 380 Exercises for Section 7.3 382 7.4 Implementing the Hash Table 384 Interface KWHashMap 384 Class Entry 384 Class HashtableOpen 386 Class HashtableChain 391 Testing the Hash Table Implementations 394 Exercises for Section 7.4 395 7.5 Implementation Considerations for Maps and Sets 396 Methods hashCode and equals 396 Implementing HashSetOpen 396 Writing HashSetOpen as an Adapter Class 397 Implementing the Java Map and Set Interfaces 398 Nested Interface Map.Entry 398 Creating a Set View of a Map 399 Method entrySet and Classes EntrySet and SetIterator 399 Classes TreeMap and TreeSet 400 Exercises for Section 7.5 401 7.6 Additional Applications of Maps 401 Case Study: Implementing a Cell Phone Contact List 401 Case Study: Completing the Huffman Coding Problem 404 Exercises for Section 7.6 408 7.7 Navigable Sets and Maps 408 Application of a NavigableMap 410 Exercises for Section 7.7 412 Chapter Review, Exercises, and Programming Projects 413 Chapter 8 Sorting 419 8.1 Using Java Sorting Methods 420 Exercises for Section 8.1 424 8.2 Selection Sort 425 Analysis of Selection Sort 426 Code for Selection Sort 426 Exercises for Section 8.2 427 8.3 Bubble Sort 428 Analysis of Bubble Sort 429 Code for Bubble Sort 430 Exercises for Section 8.3 431 8.4 Insertion Sort 431 Analysis of Insertion Sort 433 Code for Insertion Sort 434 Exercises for Section 8.4 435 8.5 Comparison of Quadratic Sorts 435 Comparisons versus Exchanges 436 Exercises for Section 8.5 436 8.6 Shell Sort: A Better Insertion Sort 437 Analysis of Shell Sort 438 Code for Shell Sort 439 Exercises for Section 8.6 440 8.7 Merge Sort 441 Analysis of Merge 442 Code for Merge 442 Algorithm for Merge Sort 443 Trace of Merge Sort Algorithm 444 Analysis of Merge Sort 444 Code for Merge Sort 445 Exercises for Section 8.7 446 8.8 Heapsort 446 First Version of a Heapsort Algorithm 446 Revising the Heapsort Algorithm 447 Algorithm to Build a Heap 449 Analysis of Revised Heapsort Algorithm 449 Code for Heapsort 449 Exercises for Section 8.8 451 8.9 Quicksort 451 Algorithm for Quicksort 452 Analysis of Quicksort 452 Code for Quicksort 453 Algorithm for Partitioning 454 Code for partition 455 A Revised Partition Algorithm 457 Code for Revised partition Method 458 Exercises for Section 8.9 460 8.10 Testing the Sort Algorithms 460 Exercises for Section 8.10 462 8.11 The Dutch National Flag Problem (Optional Topic) 462 Case Study: The Problem of the Dutch National Flag 462 Exercises for Section 8.11 466 Chapter Review, Exercises, and Programming Projects 466 Chapter 9 Self-Balancing Search Trees 471 9.1 Tree Balance and Rotation 472 Why Balance Is Important 472 Rotation 473 Algorithm for Rotation 473 Implementing Rotation 475 Exercises for Section 9.1 476 9.2 AVL Trees 477 Balancing a Left-Left Tree 477 Balancing a Left-Right Tree 478 Four Kinds of Critically Unbalanced Trees 479 Implementing an AVL Tree 481 Inserting into an AVL Tree 483 Removal from an AVL Tree 489 Performance of the AVL Tree 489 Exercises for Section 9.2 489 9.3 Red-Black Trees 490 Insertion into a Red-Black Tree 491 Removal from a Red-Black Tree 501 Performance of a Red-Black Tree 502 The TreeMap and TreeSet Classes 502 Exercises for Section 9.3 502 9.4 2-3 Trees 503 Searching a 2-3 Tree 503 Inserting an Item into a 2-3 Tree 504 Analysis of 2-3 Trees and Comparison with Balanced Binary Trees 508 Removal from a 2-3 Tree 508 Exercises for Section 9.4 510 9.5 B-Trees and 2-3-4 Trees 510 B-Trees 510 Implementing the B-Tree 512 Code for the insert Method 514 The insert Into Node Method 515 The split Node Method 516 Removal from a B-Tree 518 B+ Trees 520 2-3-4 Trees 520 Relating 2-3-4 Trees to Red-Black Trees 522 Exercises for Section 9.5 524 9.6 Skip-Lists 525 Skip-List Structure 525 Searching a Skip-List 526 Performance of a Skip-List Search 526 Inserting into a Skip-List 526 Increasing the Height of a Skip-List 527 Implementing a Skip-List 527 Searching a Skip-List 528 Insertion 529 Determining the Size of the Inserted Node 530 Completing the Insertion Process 530 Performance of a Skip-List 530 Exercises for Section 9.6 531 Chapter Review, Exercises, and Programming Projects 531 Chapter 10 Graphs 541 10.1 Graph Terminology 542 Visual Representation of Graphs 542 Directed and Undirected Graphs 543 Paths and Cycles 544 Relationship between Graphs and Trees 546 Graph Applications 546 Exercises for Section 10.1 547 10.2 The Graph ADT and Edge Class 547 Exercises for Section 10.2 549 10.3 Implementing the Graph ADT 550 Adjacency List 550 Adjacency Matrix 550 Overview of the Hierarchy 552 Class AbstractGraph 552 The ListGraph Class 555 The MatrixGraph Class 558 Comparing Implementations 558 Exercises for Section 10.3 559 10.4 Traversals of Graphs 560 Breadth-First Search 560 Depth-First Search 565 Exercises for Section 10.4 572 10.5 Applications of Graph Traversals 573 Case Study: Shortest Path through a Maze 573 Case Study: Topological Sort of a Graph 577 Exercises for Section 10.5 580 10.6 Algorithms Using Weighted Graphs 580 Finding the Shortest Path from a Vertex to All Other Vertices 580 Minimum Spanning Trees 584 Exercises for Section 10.6 588 Chapter Review, Exercises, and Programming Projects 589 Appendix A Introduction to Java 597 A.1 The Java Environment and Classes 598 The Java Virtual Machine 599 The Java Compiler 599 Classes and Objects 599 The Java API 600 The import Statement 600 Method main 600 Execution of a Java Program 601 Exercises for Section A.1 602 A.2 Primitive Data Types and Reference Variables 602 Primitive Data Types 602 Primitive-Type Variables 603 Primitive-Type Constants 604 Operators 604 Postfix and Prefix Increment 604 Type Compatibility and Conversion 606 Referencing Objects 607 Creating Objects 607 Exercises for Section A.2 608 A.3 Java Control Statements 608 Sequence and Compound Statements 608 Selection and Repetition Control 609 Nested if Statements 610 The switch Statement 612 Exercises for Section A.3 613 A.4 Methods and Class Math 613 The Instance Methods println and print 613 Call-by-Value Arguments 614 The Class Math 615 Escape Sequences 616 Exercises for Section A.4 617 A.5 The String, StringBuilder, and StringBuffer Classes 617 The String Class 617 Strings Are Immutable 620 The Garbage Collector 620 Comparing Objects 621 The String.format Method 622 The Formatter Class 623 The String.split Method 624 Introduction to Regular Expressions 624 Matching One of a Group of Characters 624 Qualifiers 624 Defined Character Groups 625 Unicode Character Class Support 626 The StringBuilder and StringBuffer Classes 627 Exercises for Section A.5 628 A.6 Wrapper Classes for Primitive Types 629 Exercises for Section A.6 630 A.7 Defining Your Own Classes 631 Private Data Fields, Public Methods 635 Constructors 635 The No-Parameter Constructor 636 Modifier and Accessor Methods 636 Use of this in a Method 637 The Method to String 637 The Method equals 637 Declaring Local Variables in Class Person 639 An Application that Uses Class Person 639 Objects as Arguments 640 Classes as Components of Other Classes 642 Java Documentation Style for Classes and Methods 642 Exercises for Section A.7 644 A.8 Arrays 645 Data Field length 647 Method Arrays.copyOf 648 Method System.arrayCopy 648 Array Data Fields 649 Array Results and Arguments 651 Arrays of Arrays 651 Exercises for Section A.8 653 A.9 Input/Output Using Class JOptionPane 655 Converting Numeric Strings to Numbers 656 GUI Menus Using Method showOptionDialog 657 Exercises for Section A.9 657 A.10 Input/Output Using Streams and the Scanner Class 658 Input Streams 658 Console Input 658 Output Streams 659 Passing Arguments to Method main 659 Closing Streams 659 Exceptions 660 A Complete File-Processing Application 660 The Scanner 662 Tokenized Input 664 Extracting Tokens Using Scanner.findInLine 664 Exercises for Section A.10 665 A.11 Catching Exceptions 665 Catching and Handling Exceptions 666 Exercises for Section A.11 672 A.12 Throwing Exceptions 672 The throws Clause 672 The throw Statement 674 Exercises for Section A.12 678 Appendix Review, Exercises, and Programming Projects 679 Appendix B Overview of UML 685 B.1 The Class Diagram 686 Representing Classes and Interfaces 686 Generalization 689 Inner or Nested Classes 690 Association 690 Aggregation and Composition 691 Generic Classes 692 B.2 Sequence Diagrams 692 Time Axis 692 Objects 693 Life Lines 694 Activation Bars 694 Messages 694 Use of Notes 694 Appendix C Event-Oriented Programming 695 C.1 Elements of an Event-Oriented Application 696 Components and Events 697 Event Listeners 698 The ActionListener Interface 698 Registering an Event Listener 699 Creating a User Interface 700 Exercises for Section C.1 703 C.2 Overview of the AWT and Swing Hierarchy 704 Example and Overview: TwoCircles 705 JFrame 709 JPanel 710 Graphics 711 Graphics Coordinates 712 Exercises for Section C.2 712 C.3 Layout Managers 712 Border Layout 713 Flow Layout 715 Box Layout 716 Grid Layout 717 Combining Layouts 718 Exercises for Section C.3 719 C.4 Components for Data Entry 719 Check Box 720 Radio Button 721 Combo Box 723 Text Field 724 Label 726 Text Area 726 Exercises for Section C.4 726 C.5 Using Data Entry Components in a GUI 727 Case Study: Liquid Volume Converter 727 Limiting the Number of Significant Digits 732 Formatting Currency for Different Locales 733 Exercises for Section C.5 734 C.6 Menus and Toolbars 735 The Classes JMenuItem, JMenu, and JMenuBar 735 Icons 737 Toolbars 737 Case Study: A Drawing Application 739 Exercises for Section C.6 747 C.7 Processing Mouse Events 747 MouseAdapter and MouseMotionAdapter 748 Case Study: A Drawing Application (continued) 749 Exercises for Section C.7 757 Appendix Review, Exercises, and Programming Projects 757 Appendix D Testing and Debugging 763 D.1 Testing Using the JUnit Framework 764 D.2 Debugging a Program 767 Using a Debugger 769 D.3 Visualizing Data Structures 772 Glossary 775 Index 785