Object-Oriented Data Structures Using Java, 3rd Edition

Object-Oriented Data Structures Using Java, 3rd Edition

by Dale
Released February 2011
Publisher(s): Jones & Bartlett Learning
ISBN: 9781449613556

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

Continuing the success of the popular second edition, the updated and revised Object-Oriented Data Structures Using Java, Third Edition is sure to be an essential resource for students learning data structures using the Java programming language. It presents traditional data structures and object-oriented topics with an emphasis on problem-solving, theory, and software engineering principles. Beginning early and continuing throughout the text, the authors introduce and expand upon the use of many Java features including packages, interfaces, abstract classes, inheritance, and exceptions. Numerous case studies provide readers with real-world examples and demonstrate possible solutions to interesting problems. The authors' lucid writing style guides readers through the rigor of standard data structures and presents essential concepts from logical, applications, and implementation levels. Key concepts throughout the Third Edition have been clarified to increase student comprehension and retention, and end-of-chapter exercises have been updated and modified.

New and Key Features to the Third Edition:

-Includes the use of generics throughout the text, providing the dual benefits of allowing for a type safe use of data structures plus exposing students to modern approaches.
-This text is among the first data structures textbooks to address the topic of concurrency and synchonization, which are growing in the importance as computer systems move to using more cores and threads to obtain additional performance with each new generation. Concurrency and synchonization are introduced in the new Section 5.7, where it begins with the basics of Java threads.
-Provides numerous case studies and examples of the problem solving process. Each case study includes problem description, an analysis of the problem input and required output, and a discussion of the appropriate data structures to use.
-Expanded chapter exercises allow you as the instructor to reinforce topics for your students using both theoretical and practical questions.
-Chapters conclude with a chapter summary that highlights the most important topics of the chapter and ties together related topics.

Instructor Resources:
-Answers to the exercises in the text
-Glossary of terms
-PowerPoint Lecture Outlines
-Test bank

Table of contents

  1. Cover Page
  2. Title Page
  3. Copyright Page
  4. Dedication Page
  5. Table of Contents
  6. 1 - Getting Organized
    1. 1.1 - Software Engineering
      1. Software Life Cycles
      2. Agile Methods
      3. Goals of Quality Software
    2. 1.2 - Object Orientation
      1. The Unified Method
    3. 1.3 - Classes, Objects, and Applications
      1. Classes
      2. Objects
      3. Applications
    4. 1.4 - Organizing Classes
      1. Inheritance
      2. Packages
    5. 1.5 - Data Structures
      1. Implementation-Dependent Structures
      2. Implementation-Independent Structures
      3. What Is a Data Structure?
    6. 1.6 - Basic Structuring Mechanisms
      1. References
      2. Arrays
    7. 1.7 - Comparing Algorithms: Big-O Analysis
      1. Big-O Notation
      2. Common Orders of Magnitude
      3. Example 1: Sum of Consecutive Integers
      4. Example 2: Finding a Number in a Phone Book
    8. Summary
    9. Exercises
  7. 2 - Abstract Data Types
    1. 2.1 - Abstraction
      1. Information Hiding
      2. Data Abstraction
      3. Data Levels
      4. Preconditions and Postconditions
      5. Java Interfaces
    2. 2.2 - The StringLog ADT Specification
      1. Constructors
      2. Transformers
      3. Observers
      4. The StringLogInterface
      5. Using the StringLogInterface
    3. 2.3 - Array-Based StringLog ADT Implementation
      1. Instance Variables
      2. Constructors
      3. Transformers
      4. Observers
    4. 2.4 - Software Testing
      1. Identifying Test Cases
      2. Test Plans
      3. Testing ADT Implementations
    5. 2.5 - Introduction to Linked Lists
      1. Array Versus Linked Lists
      2. The LLStringNode Class
      3. Operations on Linked Lists
    6. 2.6 - Linked List StringLog ADT Implementation
      1. Instance Variables
      2. Constructors
      3. Transformers
      4. Observers
    7. 2.7 - Software Design: Identification of Classes
      1. Brainstorm
      2. Filter
      3. Scenario Analysis
      4. Nouns and Verbs
      5. Cohesive Designs
      6. Summation of Our Approach
      7. Design Choices
    8. 2.8 - Case Study: A Trivia Game
      1. The Source of the Trivia Game
      2. Identifying Support Classes
      3. Implementing the Support Classes
      4. The Trivia Game Application
      5. Case Study Summation
    9. Summary
    10. Exercises
  8. 3 - The Stack ADT
    1. 3.1 - Stacks
      1. Operations on Stacks
      2. Using Stacks
    2. 3.2 - Collection Elements
      1. Generally Usable Collections
    3. 3.3 - Exceptional Situations
      1. Handling Exceptional Situations
      2. Exceptions and ADTs: An Example
      3. Error Situations and ADTs
    4. 3.4 - Formal Specification
      1. Exceptional Situations
      2. The Interfaces
      3. Example Use
    5. 3.5 - Array-Based Implementations
      1. The ArrayStack Class
      2. Definitions of Stack Operations
      3. Test Plan
    6. 3.6 - Application: Well-Formed Expressions
      1. The Balanced Class
      2. The Application
    7. 3.7 - Link-Based Implementation
      1. The LLObject Node Class
      2. The LinkedStack Class
      3. The push Operation
      4. The pop Operation
      5. The Other Stack Operations
      6. Comparing Stack Implementations
    8. 3.8 - Case Study: Postfix Expression Evaluator
      1. Discussion
      2. Evaluating Postfix Expressions
      3. Postfix Expression Evaluation Algorithm
      4. Specification: Program Postfix Evaluation
      5. Brainstorming and Filtering
      6. The PostFixEvaluator Class
      7. The PFixConsole Class
      8. Testing the Postfix Evaluator
    9. Summary
    10. Exercises
  9. 4 - Recursion
    1. 4.1 - Recursive Definitions, Algorithms, and Programs
      1. Recursive Definitions
      2. Recursive Algorithms
      3. Recursive Programs
    2. 4.2 - The Three Questions
      1. Verifying Recursive Algorithms
      2. Writing Recursive Methods
      3. Debugging Recursive Methods
    3. 4.3 - Towers of Hanoi
      1. The Algorithm
      2. The Method
      3. The Program
    4. 4.4 - Counting Blobs
      1. Generating Blobs
      2. The Counting Algorithm
      3. The Marking Algorithm
      4. The Grid Class
      5. The Program
    5. 4.5 - Recursive Linked-List Processing
      1. Reverse Printing
    6. 4.6 - Removing Recursion
      1. How Recursion Works
      2. Iteration
      3. Stacking
    7. 4.7 - Deciding Whether to Use a Recursive Solution
      1. Recursion Overhead
      2. Inefficient Algorithms
      3. Clarity
    8. Summary
    9. Exercises
  10. 5 - The Queue ADT
    1. 5.1 - Queues
      1. Operations on the Queues
      2. Using Queues
    2. 5.2 - Formal Specification
      1. Example Use
    3. 5.3 - Array-Based Implementations
      1. The ArrayBndQueue Class
      2. The ArrayUnbndQueue Class
    4. 5.4 - Application: Palindromes
      1. The Palindrome Class
      2. The Application
    5. 5.5 - Application: The Card Game of War
      1. The RankCardDeck Class
      2. The WarGame Class
      3. The WarGameApp Class
    6. 5.6 - Link-Based Implementations
      1. The Enqueue Operation
      2. The Dequeue Operation
      3. The Queue Implementation
      4. A Circular Linked Queue Design
      5. Comparing Queue Implementations
    7. 5.7 - Concurrency, Interference, and Synchronization
      1. The counter Class
      2. Java Threads
      3. Interference
      4. Synchronization
      5. A Synchronized Queue
    8. 5.8 - Case Study: Average Waiting Time
      1. Problem Discussion
      2. Program Design
      3. Program Details
      4. Testing Considerations
    9. Summary
    10. Exercises
  11. 6 - The List ADT
    1. 6.1 - Comparing Objects Revisited
      1. The equals Method
      2. The Comparable Interface
    2. 6.2 - Lists
      1. Varieties of Lists
      2. Assumptions for Our Lists
    3. 6.3 - Formal Specification
      1. The ListInterface
      2. The Indexed List Interface
      3. Example Use
    4. 6.4 - Array-Based Implementations
      1. The ArrayUnsortedList Class
      2. The ArraySortedList Class
      3. The ArrayIndexedList Class
    5. 6.5 - Applications: Poker, Golf, and Music
      1. Poker
      2. Golf
      3. Music
    6. 6.6 - The Binary Search Algorithm
      1. Improving Linear Search in a Sorted List
      2. Binary Search Algorithm
      3. Recursive Binary Search
      4. Efficiency Analysis
    7. 6.7 - Reference-Based Implementations
      1. The RefUnsortedList Class
      2. The RefSortedList Class
    8. 6.8 - Storing Objects and Structures in Files
      1. Saving Object Data in Text Files
      2. Serialization of Objects
      3. Serializing Structures
      4. Application: Song Lists
    9. Summary
    10. Exercises
  12. 7 - More Lists
    1. 7.1 - Circular Linked Lists
      1. An Unsorted Circular List
      2. The CRefUnsortedList Class
      3. Circular Versus Linear Linked Lists
    2. 7.2 - Doubly Linked Lists
      1. The Add and Remove Operations
    3. 7.3 - Linked Lists with Headers and Trailers
    4. 7.4 - A Linked List as an Array of Nodes
      1. Why Use an Array?
      2. How Is an Array Used?
    5. 7.5 - A Specialized List ADT
      1. The Specification
      2. The Implementation
    6. 7.6 - Case Study: Large Integers
      1. The LargeInt Class
      2. Addition and Subtraction
      3. Test Plan
      4. The LargeIntApp Program
    7. Summary
    8. Exercises
  13. 8 - Binary Search Trees
    1. 8.1 - Trees
      1. Binary Trees
      2. Binary Search Trees
      3. Binary Tree Traversals
    2. 8.2 - The Logical Level
      1. Tree Elements
      2. The Binary Search Tree Specification
    3. 8.3 - The Application Level
    4. 8.4 - The Implementation Level: Basics
    5. 8.5 - Iterative Versus Recursive Method Implementations
      1. Recursive Approach to the size Method
      2. Iterative Approach to the size Method
      3. Recursion or Iteration?
    6. 8.6 - The Implementation Level: Remaining Operations
      1. The contains and get Operations
      2. The add Operation
      3. The remove Operation
      4. Iteration
      5. Testing Binary Search Tree Operations
    7. 8.7 - Comparing Binary Search Tree and Linear Lists
      1. Big-O Comparisons
    8. 8.8 - Balancing a Binary Search Tree
    9. 8.9 - A Nonlinked Representation of Binary Trees
    10. 8.10 - Case Study: Word Frequency Generator
      1. Problem
      2. Discussion
      3. Brainstorming
      4. Filtering
      5. The User Interface
      6. Error Handling
      7. Scenario Analysis
      8. The WordFreq Class
      9. The Word Frequency Generator Program
      10. Testing
    11. Summary
    12. Exercises
  14. 9 - Priority Queues, Heaps, and Graphs
    1. 9.1 - Priority Queues
      1. Logical Level
      2. Application Level
      3. Implementation Level
    2. 9.2 - Heaps
      1. Heap Implementation
      2. The enqueue Method
      3. The dequeue Method
      4. A Sample Use
      5. Heaps Versus Other Representations of Priority Queues
    3. 9.3 - Introduction to Graphs
    4. 9.4 - Formal Specification of a Graph ADT
    5. 9.5 - Implementations of Graphs
      1. Array-Based Implementation
      2. Linked Implementation
    6. 9.6 - Graph Applications
      1. Depth-First Searching
      2. Breadth-First Searching
      3. The Single-Source Shortest-Paths Problem
    7. Summary
    8. Exercises
  15. 10 - Sorting and Searching Algorithms
    1. 10.1 - Sorting
      1. A Test Harness
    2. 10.2 - Simple Sorts
      1. Straight Selection Sort
      2. Bubble Sort
      3. Insertion Sort
    3. 10.3 - O(N log2N) Sorts
      1. Merge Sort
      2. Quick Sort
      3. Heap Sort
    4. 10.4 - More Sorting Considerations
      1. Testing
      2. Efficiency
      3. Objects and References
      4. Using the Comparable Interface
      5. Using the Comparator Interface
      6. Stability
    5. 10.5 - Searching
      1. Linear Searching
      2. High Probability Ordering
      3. Sorted Lists
    6. 10.6 - Hashing
      1. Collisions
      2. Choosing a Good Hash Function
      3. Complexity
    7. Summary
    8. Exercises
  16. Appendix A Java Reserved Words
  17. Appendix B Operator Precedence
  18. Appendix C Primitive Data Types
  19. Appendix D ASCII Subset of Unicode
  20. Appendix E Application of Programmer Interfaces for the Java Classes and Interfaces Used in This Book
  21. Index

Product information

  • Title: Object-Oriented Data Structures Using Java, 3rd Edition
  • Author(s): Dale
  • Release date: February 2011
  • Publisher(s): Jones & Bartlett Learning
  • ISBN: 9781449613556