Java software structures : designing and using data structures

Preface viiChapter 1 Introduction 11.1 Software Quality 2Correctness 3Reliability 3Robustness 4Usability 4Maintainability 5Reusability 5Portability 6Efficiency 6Quality Issues 61.2 Data Structures 7A Physical Example 7Containers as Objects 10 Chapter 2 Analysis of Algorithms 152.1 Algorithm Efficiency 162.2 Growth Functions and Big-Oh Notation 172.3 Comparing Growth Functions 192.4 Determining Time Complexity 22Analyzing Loop Execution 22Nested Loops 22Method Calls 23 Chapter 3 Introduction to Collections - Stacks 293.1 Collections 30Abstract Data Types 31The Java Collections API 333.2 A Stack Collection 333.3 Crucial OO Concepts 35Inheritance and Polymorphism 36Generics 373.4 Using Stacks: Evaluating Postfix Expressions 38Javadoc 453.5 Exceptions 463.6 A Stack ADT 483.7 Implementing a Stack: With Arrays 51Managing Capacity 523.8 The ArrayStack Class 53The Constructors 54The push Operation 56The pop Operation 57The peek Operation 59Other Operations 59The EmptyCollectionException Class 59Other Implementations 60 Chapter 4 Linked Structures - Stacks 674.1 R eferences as Links 684.2 Managing Linked Lists 70Accessing Elements 70Inserting Nodes 71Deleting Nodes 724.3 Elements without Links 73Doubly Linked Lists 734.4 Stacks in the Java API 744.5 Using Stacks: Traversing a Maze 754.6 Implementing a Stack: With Links 84The LinkedStack Class 84The push Operation 88The pop Operation 90Other Operations 91 Chapter 5 Queues 975.1 A Conceptual Queue 985.2 Queues in the Java API 995.3 Using Queues: Code Keys 1005.4 Using Queues: Ticket Counter Simulation 1045.5 A Queue ADT 1095.6 A Linked Implementation of a Queue 111The enqueue Operation 113The dequeue Operation 115Other Operations 1165.7 Implementing Queues: With Arrays 117The enqueue Operation 121The dequeue Operation 123Other Operations 1245.8 Double-Ended Queues (Deque) 124 Chapter 6 Lists 1296.1 A List Collection 1306.2 Lists in the Java Collections API 1326.3 Using Unordered Lists: Program of Study 1336.4 Using Indexed Lists: Josephus 1446.5 A List ADT 146Adding Elements to a List 1476.6 Implementing Lists with Arrays 152The remove Operation 154The contains Operation 156The add Operation for an Ordered List 157Operations Particular to Unordered Lists 159The addAfter Operation for an Unordered List 1596.7 Implementing Lists with Links 160The remove Operation 161 Chapter 7 Iterators 1697.1 What's an Iterator? 170Other Iterator Issues 1727.2 Using Iterators: Program of Study Revisited 172Printing Certain Courses 176Removing Courses 1777.3 Implementing Iterators: With Arrays 1797.4 Implementing Iterators: With Links 181 Chapter 8 Recursion 1878.1 Recursive Thinking 188Infinite Recursion 188Recursion in Math 1898.2 Recursive Programming 190Recursion versus Iteration 193Direct versus Indirect Recursion 1938.3 Using Recursion 194Traversing a Maze 194The Towers of Hanoi 2028.4 Analyzing Recursive Algorithms 207Chapter 9 Searching and Sorting 2159.1 Searching 216Static Methods 217Generic Methods 217Linear Search 218Binary Search 220Comparing Search Algorithms 2229.2 Sorting 223Selection Sort 226Insertion Sort 228Bubble Sort 230Quick Sort 232Merge Sort 2369.3 Radix Sort 239 Chapter 10 Trees 24910.1 Trees 250Tree Classifications 25110.2 Strategies for Implementing Trees 253Computational Strategy for ArrayImplementation of Trees 253Simulated Link Strategy for ArrayImplementation of Trees 253Analysis of Trees 25510.3 Tree Traversals 256Preorder Traversal 256Inorder Traversal 257Postorder Traversal 257Level-Order Traversal 25810.4 A Binary Tree ADT 25910.5 Using Binary Trees: Expression Trees 26310.6 A Back Pain Analyzer 27510.7 Implementing Binary Trees with Links 279The find Method 284The iteratorInOrder Method 286 Chapter 11 Binary Search Trees 29311.1 A Binary Search Tree 29411.2 Implementing Binary Search Trees: With Links 296The addElement Operation 297The removeElement Operation 300The removeAllOccurrences Operation 303The removeMin Operation 304Implementing Binary Search Trees: With Arrays 30611.3 Using Binary Search Trees: ImplementingOrdered Lists 306Analysis of the BinarySearchTreeListImplementation 30911.4 Balanced Binary Search Trees 310Right Rotation 311Left Rotation 312Rightleft Rotation 313Leftright Rotation 31311.5 Implementing BSTs: AVL Trees 314Right Rotation in an AVL Tree 315Left Rotation in an AVL Tree 315Rightleft Rotation in an AVL Tree 315Leftright Rotation in an AVL Tree 31711.6 Implementing BSTs: Red/Black Trees 317Insertion into a Red/Black Tree 318Element Removal from a Red/Black Tree 321 Chapter 12 Heaps and Priority Queues 33112.1 A Heap 332The addElement Operation 334The removeMin Operation 335The findMin Operation 33612.2 Using Heaps: Priority Queues 33612.3 Implementing Heaps: With Links 340The addElement Operation 342The removeMin Operation 344The findMin Operation 34712.4 Implementing Heaps: With Arrays 347The addElement Operation 349The removeMin Operation 350The findMin Operation 35212.5 Using Heaps: Heap Sort 352Chapter 13 Sets and Maps 35913.1 Set and Map Collections 36013.2 Sets and Maps in the Java API 36013.3 Using Sets: Domain Blocker 36313.4 Using Maps: Product Sales 36613.5 Using Maps: User Management 37013.6 Implementing Sets and Maps Using Trees 37513.7 Implementing Sets and Maps Using Hashing 375 Chapter 14 Multi-way Search Trees 38314.1 Combining Tree Concepts 38414.2 2-3 Trees 384Inserting Elements into a 2-3 Tree 385Removing Elements from a 2-3 Tree 38714.3 2-4 Trees 39014.4 B-Trees 392B*-Trees 393B+-Trees 393Analysis of B-Trees 39414.5 Implementation Strategies for B-Trees 394 Chapter 15 Graphs 40115.1 Undirected Graphs 40215.2 Directed Graphs 40315.3 Networks 40515.4 Common Graph Algorithms 406Traversals 406Testing for Connectivity 410Minimum Spanning Trees 412Determining the Shortest Path 41515.5 Strategies for Implementing Graphs 415Adjacency Lists 416Adjacency Matrices 41615.6 Implementing Undirected Graphs with an Adjacency Matrix 417The addEdge Method 422The addVertex Method 422The expandCapacity Method 423Other Methods 424 Appendix A UML 429The Unified Modeling Language (UML) 430UML Class Diagrams 430UML Relationships 432Appendix B Object-Oriented Design 437B.1 Overview of Object-Orientation 438B.2 Using Objects 438Abstraction 439Creating Objects 440B.3 C lass Libraries and Packages 442The import Declaration 442B.4 State and Behavior 443B.5 Classes 444Instance Data 447B.6 Encapsulation 448Visibility Modifiers 448Local Data 450B.7 Constructors 450B.8 Method Overloading 451B.9 R eferences Revisited 452The Null Reference 452The this Reference 453Aliases 455Garbage Collection 456Passing Objects as Parameters 457B.10 The static Modifier 457Static Variables 458Static Methods 458B.11 Wrapper Classes 459B.12 Interfaces 460The Comparable Interface 461B.13 Inheritance 462Derived Classes 462The protected Modifier 464The super Reference 465Overriding Methods 465B.14 C lass Hierarchies 466The Object Class 467Abstract Classes 468Interface Hierarchies 470B.15 Polymorphism 470References and Class Hierarchies 471Polymorphism via Inheritance 472Polymorphism via Interfaces 472B.16 Exceptions 475Exception Messages 476The try Statement 476Exception Propagation 477The Exception Class Hierarchy 478Appendix C    Java Graphics 489C.1 Pixels and Coordinates 490C.2 Representing Color 491C.3 Drawing Shapes 492C.4 Polygons and Polylines 501The Polygon Class 504Appendix D Graphical User Interfaces 511D.1 GUI Elements 512Frames and Panels 513Buttons and Action Events 517Determining Event Sources 519D.2 More Components 522Text Fields 522Check Boxes 525Radio Buttons 529Sliders 533Combo Boxes 538Timers 543D.3 Layout Managers 548Flow Layout 550Border Layout 553Grid Layout 557Box Layout 560Containment Hierarchies 563D.4 Mouse and Key Events 563Mouse Events 563Key Events 572Extending Adapter Classes 578D.5 Dialog Boxes 579File Choosers 582Color Choosers 585D.6 Some Important Details 586Borders 586Tool Tips and Mnemonics 590D.7 GUI Design 597Appendix E Hashing 607E.1 Hashing 608E.2 Hashing Functions 610The Division Method 610The Folding Method 611The Mid-Square Method 611The Radix Transformation Method 612The Digit Analysis Method 612The Length-Dependent Method 612Hashing Functions in the Java Language 613E.3 Resolving Collisions 613Chaining 613Open Addressing 616E.4 Deleting Elements from a Hash Table 620Deleting from a Chained Implementation 620Deleting from an Open AddressingImplementation 621E.5 Hash Tables in the Java Collections API 622The Hashtable Class 622The HashSet Class 624The HashMap Class 624The IdentityHashMap Class 625The WeakHashMap Class 626LinkedHashSet and LinkedHashMap 627Appendix F Regular Expressions 635Index 639