Tabs for Contents, notes, highlights

Contents
Notes
Highlights

Detailed Table of Contents

Hide Contents, Notes, and Highlights

Search TermsShow Hide

« Back to eTextbook

Copyright, iv
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, 13
2.1. Algorithm Efficiency, 14
2.2. Growth Functions and Big-OH Notation, 15
2.3. Comparing Growth Functions, 17
2.4. Determining Time Complexity, 19
Analyzing Loop Execution, 19
Nested Loops, 20
Method Calls, 21
Chapter 3. Collections, 27
3.1. Introduction to Collections, 28
Abstract Data Types, 29
The Java Collections API, 31
3.2. A Stack Collection, 31
3.3. Crucial OO Concepts, 33
Inheritance, 34
Class Hierarchies, 36
The Object Class, 37
Polymorphism, 38
References and Class Hierarchies, 38
Generics, 40
3.4. A Stack ADT, 41
Interfaces, 41
3.5. Using Stacks: Evaluating Postfix Expressions, 44
3.6. Exceptions, 51
Exception Messages, 52
The try Statement, 53
Exception Propagation, 54
3.7. Implementing a Stack: With Arrays, 55
Managing Capacity, 56
3.8. The ArrayStack Class, 57
The Constructors, 58
The push Operation, 59
The pop Operation, 61
The peek Operation, 62
Other Operations, 63
Chapter 4. Linked Structures, 71
4.1. References as Links, 72
4.2. Managing Linked Lists, 74
Accessing Elements, 74
Inserting Nodes, 75
Deleting Nodes, 76
Sentinel Nodes, 77
4.3. Elements Without Links, 78
Doubly Linked Lists, 78
4.4. Implementing a Stack: With Links, 79
The LinkedStack Class, 79
The push Operation, 83
The pop Operation, 85
Other Operations, 86
4.5. Using Stacks: Traversing a Maze, 86
4.6. Implementing Stacks: The java.util.Stack Class, 93
Unique Operations, 93
Inheritance and Implementation, 94
Chapter 5. Queues, 99
5.1. A Queue ADT, 100
5.2. Using Queues: Code Keys, 103
5.3. Using Queues: Ticket Counter Simulation, 107
5.4. Implementing Queues: With Links, 112
The enqueue Operation, 114
The dequeue Operation, 115
Other Operations, 117
5.5. Implementing Queues: With Arrays, 117
The enqueue Operation, 123
The dequeue Operation, 124
Other Operations, 125
Chapter 6. Lists, 131
6.1. A List ADT, 132
Iterators, 134
Adding Elements to a List, 135
Interfaces and Polymorphism, 137
6.2. Using Ordered Lists: Tournament Maker, 140
6.3. Using Indexed Lists: The Josephus Problem, 150
6.4. Implementing Lists: With Arrays, 152
The remove Operation, 155
The contains Operation, 157
The iterator Operation, 158
The add Operation for an Ordered List, 158
Operations Particular to Unordered Lists, 161
The addAfter Operation for an Unordered List, 162
6.5. Implementing Lists: With Links, 163
The remove Operation, 163
Doubly Linked Lists, 165
The iterator Operation, 168
6.6. Lists in the Java Collections API, 171
Cloneable, 172
Serializable, 172
RandomAccess, 172
Java.util.Vector, 173
Java.util.ArrayList, 173
Java.util.LinkedList, 176
Chapter 7. Recursion, 185
7.1. Recursive Thinking, 186
Infinite Recursion, 186
Recursion in Math, 187
7.2. Recursive Programming, 188
Recursion versus Iteration, 190
Direct versus Indirect Recursion, 191
7.3. Using Recursion, 192
Traversing a Maze, 192
The Towers of Hanoi, 197
7.4. Analyzing Recursive Algorithms, 201
Chapter 8. Sorting and Searching, 209
8.1. Searching, 210
Static Methods, 211
Generic Methods, 211
Linear Search, 212
Binary Search, 213
Comparing Search Algorithms, 216
8.2. Sorting, 217
Selection Sort, 220
Insertion Sort, 222
Bubble Sort, 224
Quick Sort, 226
Merge Sort, 229
8.3. Radix Sort, 231
Chapter 9. Trees, 241
9.1. Trees, 242
Tree Classifications, 243
9.2. Strategies for Implementing Trees, 245
Computational Strategy for Array Implementation of Trees, 245
Simulated Link Strategy for Array Implementation of Trees, 246
Analysis of Trees, 247
9.3. Tree Traversals, 248
Preorder Traversal, 248
Inorder Traversal, 249
Postorder Traversal, 249
Level-Order Traversal, 250
9.4. A Binary Tree ADT, 251
9.5. Using Binary Trees: Expression Trees, 255
9.6. Implementing Binary Trees with Links, 262
The find Method, 269
The iteratorInOrder Method, 270
9.7. Implementing Binary Trees with Arrays, 271
The find Method, 273
The iteratorInOrder Method, 274
Chapter 10. Binary Search Trees, 281
10.1. A Binary Search Tree, 282
10.2. Implementing Binary Search Trees: With Links, 284
The addElement Operation, 286
The removeElement Operation, 288
The removeAllOccurrences Operation, 291
The removeMin Operation, 292
10.3. Implementing Binary Search Trees: With Arrays, 294
The addElement Operation, 295
The removeElement Operation, 296
The removeAllOccurrences Operation, 302
The removeMin Operation, 303
10.4. Using Binary Search Trees: Implementing Ordered Lists, 304
Analysis of the BinarySearchTreeList Implementation, 308
10.5. Balanced Binary Search Trees, 309
Right Rotation, 310
Left Rotation, 310
Rightleft Rotation, 311
Leftright Rotation, 311
10.6. Implementing Binary Search Trees: AVL Trees, 312
Right Rotation in an AVL Tree, 313
Left Rotation in an AVL Tree, 315
Rightleft Rotation in an AVL Tree, 315
Leftright Rotation in an AVL Tree, 315
10.7. Implementing Binary Search Trees: Red/Black Trees, 315
Insertion into a Red/Black Tree, 316
Element Removal from a Red/Black Tree, 319
10.8. Implementing Binary Search Trees: The Java Collections API, 321
10.9. A Philosophical Quandary, 325
Chapter 11. Priority Queues and Heaps, 333
11.1. A Heap, 334
The addElement Operation, 334
The removeMin Operation, 337
The findMin Operation, 338
11.2. Using Heaps: Priority Queues, 339
11.3. Implementing Heaps: With Links, 343
The addElement Operation, 343
The removeMin Operation, 346
The findMin Operation, 349
11.4. Implementing Heaps: With Arrays, 350
The addElement Operation, 350
The removeMin Operation, 352
The findMin Operation, 353
11.5. Using Heaps: Heap Sort, 354
Chapter 12. Multi-way Search Trees, 361
12.1. Combining Tree Concepts, 362
12.2. 2-3 Trees, 362
Inserting Elements into a 2-3 Tree, 362
Removing Elements from a 2-3 Tree, 365
12.3. 2-4 Trees, 369
12.4. B-Trees, 369
B*-trees, 371
B+-trees, 372
Analysis of B-trees, 372
12.5. Implementation Strategies for B-Trees, 373
Chapter 13. Graphs, 377
13.1. Undirected Graphs, 378
13.2. Directed Graphs, 380
13.3. Networks, 381
13.4. Common Graph Algorithms, 382
Traversals, 383
Testing for Connectivity, 387
Minimum Spanning Trees, 388
Determining the Shortest Path, 391
13.5. Strategies for Implementing Graphs, 392
Adjacency Lists, 392
Adjacency Matrices, 393
13.6. Implementing Undirected Graphs with an Adjacency Matrix, 395
The addEdge Method, 399
The addVertex Method, 400
The extendCapacity Method, 401
Other Methods, 401
Chapter 14. Hashing, 407
14.1. Hashing, 408
14.2. Hashing Functions, 410
The Division Method, 410
The Folding Method, 411
The Mid-Square Method, 411
The Radix Transformation Method, 412
The Digit Analysis Method, 412
The Length-Dependent Method, 412
Hashing Functions in the Java Language, 413
14.3. Resolving Collisions, 413
Chaining, 413
Open Addressing, 416
14.4. Deleting Elements from a Hash Table, 419
Deleting from a Chained Implementation, 420
Deleting from an Open Addressing Implementation, 420
14.5. Hash Tables in the Java Collections API, 421
The Hashtable Class, 422
The HashSet Class, 424
The HashMap Class, 424
The IdentityHashMap Class, 424
The WeakHashMap Class, 425
LinkedHashSet and LinkedHashMap, 428
Chapter 15. Sets and Maps, 435
15.1. A Set Collection, 436
15.2. Using a Set: Bingo, 439
15.3. Implementing a Set: With Arrays, 443
The add Operation, 445
The addAll Operation, 447
The removeRandom Operation, 448
The remove Operation, 449
The union Operation, 450
The contains Operation, 451
The equals Operation, 452
Other Operations, 453
UML Description, 453
15.4. Implementing a Set: With Links, 455
The add Operation, 456
The removeRandom Operation, 457
The remove Operation, 458
Other Operations, 459
15.5. Maps and the Java Collections API, 459
Appendix A. UML, 467
The Unified Modeling Language (UML), 468
UML Class Diagrams, 468
UML Relationships, 469
Appendix B. Object-Oriented Design, 475
B.1. Overview of Object-Orientation, 476
B.2. Using Objects, 476
Abstraction, 477
Creating Objects, 478
B.3. Class Libraries and Packages, 480
The import Declaration, 480
B.4. State and Behavior, 481
B.5. Classes, 482
Instance Data, 485
B.6. Encapsulation, 486
Visibility Modifiers, 486
Local Data, 488
B.7. Constructors, 488
B.8. Method Overloading, 489
B.9. References Revisited, 490
The null Reference, 490
The this Reference, 491
Aliases, 493
Garbage Collection, 494
Passing Objects as Parameters, 495
B.10. The static Modifier, 495
Static Variables, 495
Static Methods, 496
B.11. Wrapper Classes, 497
B.12. Interfaces, 498
The Comparable Interface, 499
The Iterator Interface, 500
B.13. Inheritance, 500
Derived Classes, 501
The protected Modifier, 503
The super Reference, 503
Overriding Methods, 504
B.14. Class Hierarchies, 504
The Object Class, 505
Abstract Classes, 506
Interface Hierarchies, 508
B.15. Polymorphism, 508
References and Class Hierarchies, 509
Polymorphism via Inheritance, 510
Polymorphism via Interfaces, 512
B.16. Generic Types, 514
B.17. Exceptions, 515
Exception Messages, 515
The try Statement, 516
Exception Propagation, 517
The Exception Class Hierarchy, 517
Index, 527

Search Results

« Back to eTextbook


PAGE	Description

58	...