The fourth edition of Java Software Structuresembraces the enhancements of the latest version of Java, where all structures and collections are based on generics. The framework of the text walks the reader through three main areas: conceptualization, explanation, and implementation, allowing for a consistent and coherent introduction to data structures. Readers will learn how to develop high-quality software systems using well-designed collections and algorithms.

Table of Contents:
  Preface vii Chapter 1 Introduction 1 1.1 Software Quality 2 Correctness 3 Reliability 3 Robustness 4 Usability 4 Maintainability 5 Reusability 5 Portability 6 Efficiency 6 Quality Issues 6 1.2 Data Structures 7 A Physical Example 7 Containers as Objects 10   Chapter 2 Analysis of Algorithms 15 2.1 Algorithm Efficiency 16 2.2 Growth Functions and Big-Oh Notation 17 2.3 Comparing Growth Functions 19 2.4 Determining Time Complexity 22 Analyzing Loop Execution 22 Nested Loops 22 Method Calls 23   Chapter 3 Introduction to Collections — Stacks 29 3.1 Collections 30 Abstract Data Types 31 The Java Collections API 33 3.2 A Stack Collection 33 3.3 Crucial OO Concepts 35 Inheritance and Polymorphism 36 Generics 37 3.4 Using Stacks: Evaluating Postfix Expressions 38 Javadoc 45 3.5 Exceptions 46 3.6 A Stack ADT 48 3.7 Implementing a Stack: With Arrays 51 Managing Capacity 52 3.8 The ArrayStack Class 53 The Constructors 54 The push Operation 56 The pop Operation 57 The peek Operation 59 Other Operations 59 The EmptyCollectionException Class 59 Other Implementations 60   Chapter 4 Linked Structures — Stacks 67 4.1 R eferences as Links 68 4.2 Managing Linked Lists 70 Accessing Elements 70 Inserting Nodes 71 Deleting Nodes 72 4.3 Elements without Links 73 Doubly Linked Lists 73 4.4 Stacks in the Java API 74 4.5 Using Stacks: Traversing a Maze 75 4.6 Implementing a Stack: With Links 84 The LinkedStack Class 84 The push Operation 88 The pop Operation 90 Other Operations 91   Chapter 5 Queues 97 5.1 A Conceptual Queue 98 5.2 Queues in the Java API 99 5.3 Using Queues: Code Keys 100 5.4 Using Queues: Ticket Counter Simulation 104 5.5 A Queue ADT 109 5.6 A Linked Implementation of a Queue 111 The enqueue Operation 113 The dequeue Operation 115 Other Operations 116 5.7 Implementing Queues: With Arrays 117 The enqueue Operation 121 The dequeue Operation 123 Other Operations 124 5.8 Double-Ended Queues (Deque) 124   Chapter 6 Lists 129 6.1 A List Collection 130 6.2 Lists in the Java Collections API 132 6.3 Using Unordered Lists: Program of Study 133 6.4 Using Indexed Lists: Josephus 144 6.5 A List ADT 146 Adding Elements to a List 147 6.6 Implementing Lists with Arrays 152 The remove Operation 154 The contains Operation 156 The add Operation for an Ordered List 157 Operations Particular to Unordered Lists 159 The addAfter Operation for an Unordered List 159 6.7 Implementing Lists with Links 160 The remove Operation 161   Chapter 7 Iterators 169 7.1 What’s an Iterator? 170 Other Iterator Issues 172 7.2 Using Iterators: Program of Study Revisited 172 Printing Certain Courses 176 Removing Courses 177 7.3 Implementing Iterators: With Arrays 179 7.4 Implementing Iterators: With Links 181   Chapter 8 Recursion 187 8.1 Recursive Thinking 188 Infinite Recursion 188 Recursion in Math 189 8.2 Recursive Programming 190 Recursion versus Iteration 193 Direct versus Indirect Recursion 193 8.3 Using Recursion 194 Traversing a Maze 194 The Towers of Hanoi 202 8.4 Analyzing Recursive Algorithms 207 Chapter 9 Searching and Sorting 215 9.1 Searching 216 Static Methods 217 Generic Methods 217 Linear Search 218 Binary Search 220 Comparing Search Algorithms 222 9.2 Sorting 223 Selection Sort 226 Insertion Sort 228 Bubble Sort 230 Quick Sort 232 Merge Sort 236 9.3 Radix Sort 239   Chapter 10 Trees 249 10.1 Trees 250 Tree Classifications 251 10.2 Strategies for Implementing Trees 253 Computational Strategy for Array Implementation of Trees 253 Simulated Link Strategy for Array Implementation of Trees 253 Analysis of Trees 255 10.3 Tree Traversals 256 Preorder Traversal 256 Inorder Traversal 257 Postorder Traversal 257 Level-Order Traversal 258 10.4 A Binary Tree ADT 259 10.5 Using Binary Trees: Expression Trees 263 10.6 A Back Pain Analyzer 275 10.7 Implementing Binary Trees with Links 279 The find Method 284 The iteratorInOrder Method 286   Chapter 11 Binary Search Trees 293 11.1 A Binary Search Tree 294 11.2 Implementing Binary Search Trees: With Links 296 The addElement Operation 297 The removeElement Operation 300 The removeAllOccurrences Operation 303 The removeMin Operation 304 Implementing Binary Search Trees: With Arrays 306 11.3 Using Binary Search Trees: Implementing Ordered Lists 306 Analysis of the BinarySearchTreeList Implementation 309 11.4 Balanced Binary Search Trees 310 Right Rotation 311 Left Rotation 312 Rightleft Rotation 313 Leftright Rotation 313 11.5 Implementing BSTs: AVL Trees 314 Right Rotation in an AVL Tree 315 Left Rotation in an AVL Tree 315 Rightleft Rotation in an AVL Tree 315 Leftright Rotation in an AVL Tree 317 11.6 Implementing BSTs: Red/Black Trees 317 Insertion into a Red/Black Tree 318 Element Removal from a Red/Black Tree 321   Chapter 12 Heaps and Priority Queues 331 12.1 A Heap 332 The addElement Operation 334 The removeMin Operation 335 The findMin Operation 336 12.2 Using Heaps: Priority Queues 336 12.3 Implementing Heaps: With Links 340 The addElement Operation 342 The removeMin Operation 344 The findMin Operation 347 12.4 Implementing Heaps: With Arrays 347 The addElement Operation 349 The removeMin Operation 350 The findMin Operation 352 12.5 Using Heaps: Heap Sort 352 Chapter 13 Sets and Maps 359 13.1 Set and Map Collections 360 13.2 Sets and Maps in the Java API 360 13.3 Using Sets: Domain Blocker 363 13.4 Using Maps: Product Sales 366 13.5 Using Maps: User Management 370 13.6 Implementing Sets and Maps Using Trees 375 13.7 Implementing Sets and Maps Using Hashing 375   Chapter 14 Multi-way Search Trees 383 14.1 Combining Tree Concepts 384 14.2 2-3 Trees 384 Inserting Elements into a 2-3 Tree 385 Removing Elements from a 2-3 Tree 387 14.3 2-4 Trees 390 14.4 B-Trees 392 B*-Trees 393 B+-Trees 393 Analysis of B-Trees 394 14.5 Implementation Strategies for B-Trees 394   Chapter 15 Graphs 401 15.1 Undirected Graphs 402 15.2 Directed Graphs 403 15.3 Networks 405 15.4 Common Graph Algorithms 406 Traversals 406 Testing for Connectivity 410 Minimum Spanning Trees 412 Determining the Shortest Path 415 15.5 Strategies for Implementing Graphs 415 Adjacency Lists 416 Adjacency Matrices 416 15.6 Implementing Undirected Graphs with an Adjacency Matrix 417 The addEdge Method 422 The addVertex Method 422 The expandCapacity Method 423 Other Methods 424   Appendix A UML 429 The Unified Modeling Language (UML) 430 UML Class Diagrams 430 UML Relationships 432 Appendix B Object-Oriented Design 437 B.1 Overview of Object-Orientation 438 B.2 Using Objects 438 Abstraction 439 Creating Objects 440 B.3 C lass Libraries and Packages 442 The import Declaration 442 B.4 State and Behavior 443 B.5 Classes 444 Instance Data 447 B.6 Encapsulation 448 Visibility Modifiers 448 Local Data 450 B.7 Constructors 450 B.8 Method Overloading 451 B.9 R eferences Revisited 452 The Null Reference 452 The this Reference 453 Aliases 455 Garbage Collection 456 Passing Objects as Parameters 457 B.10 The static Modifier 457 Static Variables 458 Static Methods 458 B.11 Wrapper Classes 459 B.12 Interfaces 460 The Comparable Interface 461 B.13 Inheritance 462 Derived Classes 462 The protected Modifier 464 The super Reference 465 Overriding Methods 465 B.14 C lass Hierarchies 466 The Object Class 467 Abstract Classes 468 Interface Hierarchies 470 B.15 Polymorphism 470 References and Class Hierarchies 471 Polymorphism via Inheritance 472 Polymorphism via Interfaces 472 B.16 Exceptions 475 Exception Messages 476 The try Statement 476 Exception Propagation 477 The Exception Class Hierarchy 478 Appendix C         Java Graphics 489 C.1 Pixels and Coordinates 490 C.2 Representing Color 491 C.3 Drawing Shapes 492 C.4 Polygons and Polylines 501 The Polygon Class 504 Appendix D Graphical User Interfaces 511 D.1 GUI Elements 512 Frames and Panels 513 Buttons and Action Events 517 Determining Event Sources 519 D.2 More Components 522 Text Fields 522 Check Boxes 525 Radio Buttons 529 Sliders 533 Combo Boxes 538 Timers 543 D.3 Layout Managers 548 Flow Layout 550 Border Layout 553 Grid Layout 557 Box Layout 560 Containment Hierarchies 563 D.4 Mouse and Key Events 563 Mouse Events 563 Key Events 572 Extending Adapter Classes 578 D.5 Dialog Boxes 579 File Choosers 582 Color Choosers 585 D.6 Some Important Details 586 Borders 586 Tool Tips and Mnemonics 590 D.7 GUI Design 597 Appendix E Hashing 607 E.1 Hashing 608 E.2 Hashing Functions 610 The Division Method 610 The Folding Method 611 The Mid-Square Method 611 The Radix Transformation Method 612 The Digit Analysis Method 612 The Length-Dependent Method 612 Hashing Functions in the Java Language 613 E.3 Resolving Collisions 613 Chaining 613 Open Addressing 616 E.4 Deleting Elements from a Hash Table 620 Deleting from a Chained Implementation 620 Deleting from an Open Addressing Implementation 621 E.5 Hash Tables in the Java Collections API 622 The Hashtable Class 622 The HashSet Class 624 The HashMap Class 624 The IdentityHashMap Class 625 The WeakHashMap Class 626 LinkedHashSet and Product 627 Appendix F Regular Expressions 635 Index 639