This is the eBook of the printed book and may not include any media, website access codes, or print supplements that may come packaged with the bound book.
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
