Object-oriented data structures using Java

Thoroughly revised and updated, Object Oriented Data Structures using Java, Second Edition presents classic data structure topics with an emphasis on problem solving, theory, and software engineering principles. Beginning early and continuing throughout the text, the authors carefully introduce and expand on the use of many Java features such as packages, interfaces, abstract classes, inheritance, and exceptions. Chapters have been rearranged to get to the heart of the textbook material more quickly and additional exercises and example applications are included throughout.

1 Getting Organized	p. 1
1.1 Software Engineering	p. 2
Software Life Cycles	p. 3
Agile Methods	p. 5
Goals of Quality Software	p. 6
1.2 Object Orientation	p. 8
Benefits	p. 9
The Unified Method	p. 9
1.3 Classes, Objects, and Applications	p. 10
Classes	p. 10
Objects	p. 16
Applications	p. 18
1.4 Organizing Classes	p. 20
Inheritance	p. 21
Packages	p. 26
1.5 Data Structures	p. 28
Implementation-Dependent Structures	p. 29
Implementation-Independent Structures	p. 30
What Is a Data Structure?	p. 33
1.6 Basic Structuring Mechanisms	p. 33
References	p. 33
Arrays	p. 37
1.7 Comparing Algorithms: Big-O Analysis	p. 41
Big-O Notation	p. 44
Common Orders of Magnitude	p. 46
Example 1 Sum of Consecutive Integers	p. 47
Example 2 Finding a Number in a Phone Book	p. 49
Summary	p. 51
Exercises	p. 52
2 Abstract Data Types	p. 61
2.1 Abstraction	p. 62
Information Hiding	p. 62
Data Abstraction	p. 63
Data Levels	p. 64
Preconditions and Postconditions	p. 65
Java Interfaces	p. 66
2.2 The StringLog ADT Specification	p. 70
Constructors	p. 70
Transformers	p. 71
Observers	p. 71
The StringLogInterface	p. 71
Using the StringLogInterface	p. 73
2.3 Array-Based StringLog ADT Implementation	p. 75
Instance Variables	p. 75
Constructors	p. 77
Transformers	p. 78
Observers	p. 80
2.4 Software Testing	p. 89
Identifying Test Cases	p. 90
Test Plans	p. 92
Testing ADT Implementations	p. 92
2.5 Introduction to Linked Lists	p. 100
Array versus Linked Lists	p. 100
The LLStringNode Class	p. 101
Operations on Linked Lists	p. 105
2.6 Linked List StringLog ADT Implementation	p. 111
Instance Variables	p. 113
Constructors	p. 113
Transformers	p. 114
Observers	p. 117
2.7 Software Design: Identification of Classes	p. 122
Brainstorm	p. 122
Filter	p. 123
Scenario Analysis	p. 123
Nouns and Verbs	p. 123
Cohesive Designs	p. 124
Summation of Our Approach	p. 124
Design Choices	p. 126
2.8 Case Study: A Trivia Game	p. 126
The Source of the Trivia Game	p. 127
Identifying Support Classes	p. 129
Implementing the Support Classes	p. 131
The Trivia Game Application	p. 138
Case Study Summation	p. 143
Summary	p. 144
Exercises	p. 144
3 The Stack ADT	p. 155
3.1 Stacks	p. 156
Operations on Stacks	p. 157
Using Stacks	p. 157
3.2 Collection Elements	p. 159
Generally Usable Collections	p. 160
3.3 Exceptional Situations	p. 163
Handling Exceptional Situations	p. 163
Exceptions and ADTs: An Example	p. 164
Error Situations and ADTs	p. 169
3.4 Formal Specification	p. 171
Exceptional Situations	p. 172
The Interfaces	p. 175
3.5 Application: Well-Formed Expressions	p. 179
The Balanced Class	p. 180
The Application	p. 185
3.6 Array-Based Implementations	p. 188
The ArrayStack Class	p. 188
Definitions of Stack Operations	p. 190
Test Plan	p. 192
3.7 Link-Based Implementation	p. 195
The LLObject Node Class	p. 196
The LinkedStack Class	p. 197
The push Operation	p. 198
The pop Operation	p. 202
The Other Stack Operations	p. 204
Comparing Stack Implementations	p. 206
3.8 Case Study: Postfix Expression Evaluator	p. 207
Discussion	p. 207
Evaluating Postfix Expressions	p. 208
Postfix Expression Evaluation Algorithm	p. 210
Specification: Program Postfix Evaluation	p. 212
Brainstorming and Filtering	p. 214
The PostFixEvaluator Class	p. 215
The PFixConsole Class	p. 218
Testing the Postfix Evaluator	p. 220
Summary	p. 222
Exercises	p. 222
4 A Recursion	p. 235
4.1 Recursive Definitions, Algorithms, and Programs	p. 236
Recursive Definitions	p. 236
Recursive Algorithms	p. 237
Recursive Programs	p. 240
4.2 The Three Questions	p. 243
Verifying Recursive Algorithms	p. 243
Writing Recursive Methods	p. 245
Debugging Recursive Methods	p. 245
4.3 Towers of Hanoi	p. 246
The Algorithm	p. 246
The Method	p. 248
The Program	p. 249
4.4 Counting Blobs	p. 252
Generating Blobs	p. 253
The Counting Algorithm	p. 254
The Marking Algorithm	p. 255
The Grid Class	p. 256
The Program	p. 259
4.5 Recursive Linked-List Processing	p. 261
Reverse Printing	p. 261
4.6 Removing Recursion	p. 265
How Recursion Works	p. 266
Iteration	p. 270
Stacking	p. 271
4.7 Deciding Whether to Use a Recursive Solution	p. 273
Recursion Overhead	p. 274
Inefficient Algorithms	p. 274
Clarity	p. 277
Summary	p. 277
Exercises	p. 278
5 The Queue ADT	p. 289
5.1 Queues	p. 290
Operations on the Queues	p. 291
Using Queues	p. 291
5.2 Formal Specification	p. 292
5.3 Application: Palindromes	p. 296
The Palindrome Class	p. 296
The Application	p. 299
5.4 Array-Based Implementations	p. 301
The ArrayBndQueue Class	p. 301
The ArrayUnbndQueue Class	p. 308
5.5 Application: The Card Game of War	p. 311
The RankCardDeck Class	p. 312
The WarGame Class	p. 313
The WarGameApp Class	p. 318
5.6 Link-Based Implementations	p. 321
The Enqueue Operation	p. 323
The Dequeue Operation	p. 324
The Queue Implementation	p. 326
A Circular Linked Queue Design	p. 327
Comparing Queue Implementations	p. 328
5.7 Case Study: Average Waiting Time	p. 330
Problem Discussion	p. 331
Program Design	p. 333
Program Details	p. 336
Testing Considerations	p. 346
Summary	p. 347
Exercises	p. 349
6 The List ADT	p. 357
6.1 Comparing Objects Revisited	p. 358
The equals Method	p. 358
The Comparable Interface	p. 360
6.2 Lists	p. 362
Varieties of Lists	p. 363
Assumptions for Our Lists	p. 364
6.3 Formal Specification	p. 364
The ListInterface	p. 364
The Specialized Interfaces	p. 367
Example Use	p. 370
6.4 Array-Based Implementations	p. 373
The List Class	p. 374
The ArrayUnsortedList Class	p. 379
The ArraySortedList Class	p. 382
The ArrayIndexedList Class	p. 389
6.5 Applications: Poker, Golf, and Music	p. 393
Poker	p. 394
Golf	p. 397
Music	p. 400
6.6 The Binary Search Algorithm	p. 404
Improving Linear Search in a Sorted List	p. 405
Binary Search Algorithm	p. 405
Recursive Binary Search	p. 410
Efficiency Analysis	p. 413
6.7 Reference-Based Implementations	p. 414
The RefList Class	p. 414
The RefUnsortedList Class	p. 421
The RefSortedList Class	p. 422
6.8 Storing Objects and Structures in Files	p. 427
Saving Object Data in Text Files	p. 428
Serialization of Objects	p. 429
Serializing Structures	p. 433
Application: Song Lists	p. 433
Summary	p. 441
Exercises	p. 441
7 More Lists	p. 455
7.1 Circular Linked Lists	p. 456
An Unsorted Circular List	p. 457
The CrefList Class	p. 459
The CrefUnsorted List Class	p. 464
Circular versus Linear Linked Lists	p. 465
7.2 Doubly Linked Lists	p. 466
The Add and Remove Operations	p. 468
7.3 Linked Lists with Headers and Trailers	p. 470
7.4 A Linked List as an Array of Nodes	p. 471
Why Use an Array?	p. 472
How Is an Array Used?	p. 472
7.5 A Specialized List ADT	p. 480
The Specification	p. 481
The Implementation	p. 482
7.6 Case Study: Large Integers	p. 487
The LargeInt Class	p. 491
Addition and Subtraction	p. 493
Test Plan	p. 501
The LargeIntApp Program	p. 502
Summary	p. 506
Exercises	p. 506
8 Binary Search Trees	p. 515
8.1 Trees	p. 516
Binary Trees	p. 518
Binary Search Trees	p. 520
Binary Tree Traversals	p. 522
8.2 The Logical Level	p. 524
Tree Elements	p. 524
The Binary Search Tree Specification	p. 525
8.3 The Application Level	p. 527
8.4 The Implementation Level: Basics	p. 529
8.5 Iterative versus Recursive Method Implementations	p. 532
Recursive Approach to the size Method	p. 533
Iterative Approach to the size Method	p. 537
Recursion or Iteration?	p. 539
8.6 The Implementation Level: Remaining Operations	p. 539
The contains and get Operations	p. 539
The add Operation	p. 543
The remove Operation	p. 548
Iteration	p. 555
Testing Binary Search Tree Operations	p. 559
8.7 Comparing Binary Search Tree and Linear Lists	p. 561
Big-O Comparisons	p. 561
8.8 Balancing a Binary Search Tree	p. 562
8.9 A Nonlinked Representation of Binary Trees	p. 568
8.10 Case Study: Word Frequency Generator	p. 572
Problem	p. 572
Discussion	p. 572
Brainstorming	p. 572
Filtering	p. 573
The User Interface	p. 573
Error Handling	p. 574
Scenario Analysis	p. 574
The WordFreq Class	p. 576
The Word Frequency Generator Program	p. 578
Testing	p. 580
Summary	p. 582
Exercises	p. 582
9 Priority Queues, Heaps, and Graphs	p. 597
9.1 Priority Queues	p. 598
Logical Level	p. 598
Application Level	p. 600
Implementation Level	p. 600
9.2 Heaps	p. 601
Heap Implementation	p. 605
The enqueue Method	p. 607
The dequeue Method	p. 610
Heaps versus Other Representations of Priority Queues	p. 614
9.3 Introduction to Graphs	p. 615
9.4 Formal Specification of a Graph ADT	p. 620
9.5 Graph Applications	p. 622
Depth-First Searching	p. 622
Breadth-First Searching	p. 626
The Single-Source Shortest-Paths Problem	p. 629
9.6 Implementations of Graphs	p. 635
Array-Based Implementation	p. 635
Linked Implementation	p. 640
Summary	p. 642
Exercises	p. 643
10 Sorting and Searching Algorithms	p. 653
10.1 Sorting	p. 654
A Test Harness	p. 655
10.2 Simple Sorts	p. 658
Straight Selection Sort	p. 658
Bubble Sort	p. 664
Insertion Sort	p. 668
10.3 O(N log[subscript 2]N) Sorts	p. 672
Merge Sort	p. 672
Quick Sort	p. 680
Heap Sort	p. 686
10.4 More Sorting Considerations	p. 692
Testing	p. 692
Efficiency	p. 692
Objects and References	p. 694
Using the Comparable Interface	p. 694
Using the Comparator Interface	p. 695
Stability	p. 701
10.5 Searching	p. 702
Linear Searching	p. 702
High Probability Ordering	p. 703
Sorted Lists	p. 704
10.6 Hashing	p. 704
Collisions	p. 707
Choosing a Good Hash Function	p. 716
Complexity	p. 719
Summary	p. 719
Exercises	p. 720
Appendix A Java Reserved Words	p. 729
Appendix B Operator Precedence	p. 730
Appendix C Primitive Data Types	p. 731
Appendix D ASCII Subset of Unicode	p. 732
Appendix E Application of Programmer Interfaces for the Java Classes and Interfaces Used in This Book	p. 733
Appendix F A Generic Stack	p. 749
F.1 The Bounded Stack Interface	p. 750
F.2 The Bounded Stack Class	p. 751
F.3 The SampleApp Class	p. 754
Index	p. 757

Available:*

On Order

Summary

Summary

Table of Contents