Table of Contents

1. Getting Organized
   1.1    Software Engineering
   1.2    Object Orientation
   1.3    Classes, Objects, and Applications
   1.4    Organizing Classes
   1.5    Data Structures
   1.6    Basic Structuring Mechanisms
   1.7    Comparing Algorithms:  Big-O Analysis
2. Abstract Data Types
   2.1    Abstraction
   2.2    The StringLog ADT Specification
   2.3    Array-Based StringLog ADT Implementation
   2.4    Software Testing
   2.5    Introduction to linked Lists
   2.6    Linked List StringLog ADT Implementation
   2.7    Software Design:  Identification of Classes
   2.8    Case Study:  A Trivia Game
3. The Stack ADT
   3.1    Stacks
   3.2    Collection Elements
   3.3    Exceptional Situations
   3.4    Formal Specification
   3.5    Application:  Well-Formed Expressions
   3.6    Array-Based Implementation
   3.7    Link-Based Implementation
   3.8    Case Study:  Postfix Expression Evaluator
4. Recursion
   4.1    Recursive Definitions, Algorithms, and Programs
   4.2    The Three Questions
   4.3    Towers of Hanoi
   4.4     Counting Blobs
   4.5    Recursive Linked-List Processing
   4.6    Removing Recursion
   4.7    Deciding whether to Use a Recursive Solution
5. The Queue ADT
   5.1    Queues
   5.2    Formal Specification
   5.3    Application:  Palindromes
   5.4    Array-Based Implementations
   5.5    Application:  The Card Game of War
   5.6    Link-Based Implementations
   5.7    Case Study:  Average Waiting Time
6. The List ADT
   6.1    Comparing Objects Revisited
   6.2    Lists
   6.3    Formal Specification
   6.4    Array-Based Implementation
   6.5    Applications:  Poker, Golf, and Music
   6.6    The Binary Search Algorithm
   6.7    Reference-Based Implementations
   6.8    Storing Objects and Structures in Files
7. More Lists
   7.1    Circular Linked Lists
   7.2    Doubly Linked Lists
   7.3    Linked Lists with Headers and Trailers
   7.4    A Linked List as an Array of Nodes
   7.5    A Specialized List ADT
   7.6    Case Study:  Large Integers
8. Binary Search Trees
   8.1      Trees
   8.2      The Logical Level
   8.3      The Application Level
   8.4      The Implementation Level:  Basic
   8.5      Iterative verses Recursive Method Implementation
   8.6      The Implementation Level:  Remaining Operations
   8.7      Comparing Binary Search Tree and Linear Lists
   8.8      Balancing a Binary Search Tree
   8.9      A Nonlinked Representation of Binary Trees
   8.10 Case Study:  Word Frequency Generator
9. Priority Queues, Heaps, and Graphs
   9.1    Priority Queues
   9.2    Heaps
   9.3    Introduction to Graphs
   9.4    Formal Specification of Graph ADT
   9.5    Graph Applications
   9.6    Implementations of Graphs
10. Sorting and Search Algorithms
    10.1      Sorting
    10.2      Simple Sorts
    10.3      O{N log2N} Sorts
    10.4      More Sorting Considerations
    10.5      Searching
    10.6      Hashing

     Appendix A:  Java Reserved Words

     Appendix B:  Operator Precedence

     Appendix C:  Primitive Data Types
    Appendix D:  ASCII Subset of Unicode

Appendix E:  Application of Programmer Interfaces for the Java Classes and Interfaces   Used in This Book

Appendix F:    The Generic Stack