Object-Oriented Data Structures Using Java

Cover......Page 1
Preface......Page 6
Contents......Page 12
Software Engineering......Page 20
1.1 The Software Process......Page 21
1.2 Program Design......Page 27
1.3 Verification of Software Correctness......Page 49
Data Design and Implementation......Page 88
2.1 Different Views of Data......Page 89
2.2 Java’s Built- In Types......Page 98
2.3 Class- Based Types......Page 117
ADTs Unsorted List and Sorted List......Page 158
3.1 Lists......Page 159
3.2 Abstract Data Type Unsorted List......Page 160
3.3 Abstract Classes......Page 181
3.4 Abstract Data Type Sorted List......Page 188
3.5 Comparison of Algorithms......Page 200
3.6 Comparison of Unsorted and Sorted List ADT Algorithms......Page 208
3.7 Generic ADTs......Page 212
ADTs Stack and Queue......Page 268
4.1 Formal ADT Specifications......Page 269
4.2 Stacks......Page 274
4.3 The Java Collections Framework......Page 300
4.4 Queues......Page 305
Linked Structures......Page 360
5.1 Implementing a Stack as a Linked Structure......Page 361
5.2 Implementing a Queue as a Linked Structure......Page 375
5.3 An Abstract Linked List Class......Page 385
5.4 Implementing the Unsorted List as a Linked Structure......Page 399
5.5 Implementing the Sorted List as a Linked Structure......Page 405
5.6 Our List Framework......Page 414
Lists Plus......Page 424
6.1 Circular Linked Lists......Page 425
6.2 Doubly Linked Lists......Page 436
6.3 Linked Lists with Headers and Trailers......Page 441
6.4 A Linked List as an Array of Nodes......Page 442
6.5 A Specialized List ADT......Page 453
Programming with Recursion......Page 494
7.1 What is Recursion?......Page 495
7.2 Programming Recursively......Page 499
7.3 Verifying Recursive Methods......Page 502
7.4 Writing Recursive Methods......Page 503
7.5 Using Recursion to Simplify Solutions— Two Examples......Page 507
7.6 A Recursive Version of Binary Search......Page 515
7.7 Recursive Linked- List Processing......Page 517
7.8 How Recursion Works......Page 524
7.9 Removing Recursion......Page 533
7.10 Deciding Whether to Use a Recursive Solution......Page 537
Binary Search Trees......Page 548
8.1 Trees......Page 549
8.2 The Logical Level......Page 557
8.3 The Application Level......Page 561
8.4 The Implementation Level— Declarations and Simple Operations......Page 563
8.5 Iterative Versus Recursive Method Implementations......Page 565
8.6 The Implementation Level— More Operations......Page 572
8.7 Comparing Binary Search Trees to Linear Lists......Page 593
8.8 Balancing a Binary Search Tree......Page 595
8.9 A Nonlinked Representation of Binary Trees......Page 600
Priority Queues, Heaps, and Graphs......Page 630
9.1 Priority Queues......Page 631
9.2 Heaps......Page 634
9.3 Introduction to Graphs......Page 648
9.4 Storing Objects/ Structures in Files......Page 673
Sorting and Searching Algorithms......Page 692
10.1 Sorting......Page 693
10.2 Simple Sorts......Page 696
10.3 O( N log N) Sorts......Page 708
10.4 More Sorting Considerations......Page 729
10.5 Searching......Page 739
10.6 Hashing......Page 742
Answers to Selected Exercises......Page 772
Index......Page 812