Data Structures

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