Object-Oriented Data Structures Using Java, 4th Edition

Object-Oriented Data Structures Using Java, 4th Edition

by Dale
Released September 2016
Publisher(s): Jones & Bartlett Learning
ISBN: 9781284089103

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

Object-Oriented Data Structures Using Java, Fourth Edition presents traditional data structures and object-oriented topics with an emphasis on problem-solving, theory, and software engineering principles.

Table of contents

  1. Cover Page
  2. Title Page
  3. Copyright Page
  4. Dedication
  5. Contents
  6. Preface
  7. 1 Getting Organized
    1. 1.1 Classes, Objects, and Applications
      1. Classes
      2. The Unified Method
      3. Objects
      4. Applications
    2. 1.2 Organizing Classes
      1. Inheritance
      2. Packages
    3. 1.3 Exceptional Situations
      1. Handling Exceptional Situations
      2. Exceptions and Classes: An Example
    4. 1.4 Data Structures
      1. Implementation-Dependent Structures
      2. Implementation-Independent Structures
      3. What Is a Data Structure?
    5. 1.5 Basic Structuring Mechanisms
      1. Memory
      2. References
      3. Arrays
    6. 1.6 Comparing Algorithms: Order of Growth Analysis
      1. Measuring an Algorithm’s Time Efficiency
      2. Complexity Cases
      3. Size of Input
      4. Comparing Algorithms
      5. Order of Growth
      6. Selection Sort
      7. Common Orders of Growth
    7. Summary
    8. Exercises
  8. 2 The Stack ADT
    1. 2.1 Abstraction
      1. Information Hiding
      2. Data Abstraction
      3. Data Levels
      4. Preconditions and Postconditions
      5. Java Interfaces
      6. Interface-Based Polymorphism
    2. 2.2 The Stack
      1. Operations on Stacks
      2. Using Stacks
    3. 2.3 Collection Elements
      1. Generally Usable Collections
    4. 2.4 The Stack Interface
      1. Exceptional Situations
      2. The Interface
      3. Example Use
    5. 2.5 Array-Based Stack Implementations
      1. The ArrayBoundedStack Class
      2. Definitions of Stack Operations
      3. The ArrayListStack Class
    6. 2.6 Application: Balanced Expressions
      1. The Balanced Class
      2. The Application
      3. The Software Architecture
    7. 2.7 Introduction to Linked Lists
      1. Arrays Versus Linked Lists
      2. The LLNode Class
      3. Operations on Linked Lists
    8. 2.8 A Link-Based Stack
      1. The LinkedStack Class
      2. The push Operation
      3. The pop Operation
      4. The Other Stack Operations
      5. Comparing Stack Implementations
    9. 2.9 Application: Postfix Expression Evaluator
      1. Discussion
      2. Evaluating Postfix Expressions
      3. Postfix Expression Evaluation Algorithm
      4. Error Processing
      5. The PostFixEvaluator Class
      6. The PFixCLI Class
    10. 2.10 Stack Variations
      1. Revisiting Our Stack ADT
      2. The Java Stack Class and the Collections Framework
    11. Summary
    12. Exercises
  9. 3 Recursion
    1. 3.1 Recursive Definitions, Algorithms, and Programs
      1. Recursive Definitions
      2. Recursive Algorithms
      3. Recursive Programs
      4. Iterative Solution for Factorial
    2. 3.2 The Three Questions
      1. Verifying Recursive Algorithms
      2. Determining Input Constraints
      3. Writing Recursive Methods
      4. Debugging Recursive Methods
    3. 3.3 Recursive Processing of Arrays
      1. Binary Search
    4. 3.4 Recursive Processing of Linked Lists
      1. Recursive Nature of Linked Lists
      2. Traversing a Linked List
      3. Transforming a Linked List
    5. 3.5 Towers
      1. The Algorithm
      2. The Method
      3. The Program
    6. 3.6 Fractals
      1. A T-Square Fractal
      2. Variations
    7. 3.7 Removing Recursion
      1. How Recursion Works
      2. Tail Call Elimination
      3. Direct Use of a Stack
    8. 3.8 When to Use a Recursive Solution
      1. Recursion Overhead
      2. Inefficient Algorithms
      3. Clarity
    9. Summary
    10. Exercises
  10. 4 The Queue ADT
    1. 4.1 The Queue
      1. Operations on Queues
      2. Using Queues
    2. 4.2 The Queue Interface
      1. Example Use
    3. 4.3 Array-Based Queue Implementations
      1. The ArrayBoundedQueue Class
      2. The ArrayUnboundedQueue Class
    4. 4.4 An Interactive Test Driver
      1. The General Approach
      2. A Test Driver for the ArrayBoundedQueue Class
      3. Using the Test Driver
    5. 4.5 Link-Based Queue Implementations
      1. The Enqueue Operation
      2. The Dequeue Operation
      3. A Circular Linked Queue Design
      4. Comparing Queue Implementations
    6. 4.6 Application: Palindromes
      1. The Palindrome Class
      2. The Applications
    7. 4.7 Queue Variations
      1. Exceptional Situations
      2. The GlassQueue
      3. The Double-Ended Queue
      4. Doubly Linked Lists
      5. The Java Library Collection Framework Queue/Deque
    8. 4.8 Application: Average Waiting Time
      1. Problem Discussion and Example
      2. The Customer Class
      3. The Simulation
      4. Testing Considerations
    9. 4.9 Concurrency, Interference, and Synchronization
      1. The Counter Class
      2. Java Threads
      3. Interference
      4. Synchronization
      5. A Synchronized Queue
      6. Concurrency and the Java Library Collection Classes
    10. Summary
    11. Exercises
  11. 5 The Collection ADT
    1. 5.1 The Collection Interface
      1. Assumptions for Our Collections
      2. The Interface
    2. 5.2 Array-Based Collection Implementation
    3. 5.3 Application: Vocabulary Density
    4. 5.4 Comparing Objects Revisited
      1. The equals Method
      2. The Comparable Interface
    5. 5.5 Sorted Array-Based Collection Implementation
      1. Comparable Elements
      2. The Implementation
      3. Implementing ADTs “by Copy” or “by Reference”
      4. Sample Application
    6. 5.6 Link-Based Collection Implementation
      1. The Internal Representation
      2. The Operations
      3. Comparing Collection Implementations
    7. 5.7 Collection Variations
      1. The Java Collections Framework
      2. The Bag ADT
      3. The Set ADT
    8. Summary
    9. Exercises
  12. 6 The List ADT
    1. 6.1 The List Interface
      1. Iteration
      2. Assumptions for Our Lists
      3. The Interface
    2. 6.2 List Implementations
      1. Array-Based Implementation
      2. Link-Based Implementation
    3. 6.3 Applications: Card Deck and Games
      1. The Card Class
      2. The CardDeck Class
      3. Application: Arranging a Card Hand
      4. Application: Higher or Lower?
      5. Application: How Rare Is a Pair?
    4. 6.4 Sorted Array-Based List Implementation
      1. The Insertion Sort
      2. Unsupported Operations
      3. Comparator Interface
      4. Constructors
      5. An Example
    5. 6.5 List Variations
      1. Java Library Lists
      2. Linked List Variations
      3. A Linked List as an Array of Nodes
    6. 6.6 Application: Large Integers
      1. Large Integers
      2. The Internal Representation
      3. The LargeIntList class
      4. The LargeInt Class
      5. Addition and Subtraction
      6. The LargeIntCLI Program
    7. Summary
    8. Exercises
  13. 7 The Binary Search Tree ADT
    1. 7.1 Trees
      1. Tree Traversals
    2. 7.2 Binary Search Trees
      1. Binary Trees
      2. Binary Search Trees
      3. Binary Tree Traversals
    3. 7.3 The Binary Search Tree Interface
      1. The Interface
    4. 7.4 The Implementation Level: Basics
    5. 7.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. 7.6 The Implementation Level: Remaining Observers
      1. The contains and get Operations
      2. The Traversals
    7. 7.7 The Implementation Level: Transformers
      1. The add Operation
      2. The remove Operation
    8. 7.8 Binary Search Tree Performance
      1. Text Analysis Experiment Revisited
      2. Insertion Order and Tree Shape
      3. Balancing a Binary Search Tree
    9. 7.9 Application: Word Frequency Counter
      1. The WordFreq Class
      2. The Application
    10. 7.10 Tree Variations
      1. Application-Specific Variations
      2. Balanced Search Trees
    11. Summary
    12. Exercises
  14. 8 The Map ADT
    1. 8.1 The Map Interface
    2. 8.2 Map Implementations
      1. Unsorted Array
      2. Sorted Array
      3. Unsorted Linked List
      4. Sorted Linked List
      5. Binary Search Tree
      6. An ArrayList-Based Implementation
    3. 8.3 Application: String-to-String Map
    4. 8.4 Hashing
      1. Collisions
    5. 8.5 Hash Functions
      1. Array Size
      2. The Hash Function
      3. Java’s Support for Hashing
      4. Complexity
    6. 8.6 A Hash-Based Map
      1. The Implementation
      2. Using the HMap class
    7. 8.7 Map Variations
      1. A Hybrid Structure
      2. Java Support for Maps
    8. Summary
    9. Exercises
  15. 9 The Priority Queue ADT
    1. 9.1 The Priority Queue Interface
      1. Using Priority Queues
      2. The Interface
    2. 9.2 Priority Queue Implementations
      1. Unsorted Array
      2. Sorted Array
      3. Sorted Linked List
      4. Binary Search Tree
    3. 9.3 The Heap
    4. 9.4 The Heap Implementation
      1. A Nonlinked Representation of Binary Trees
      2. Implementing a Heap
      3. The enqueue Method
      4. The dequeue Method
      5. A Sample Use
      6. Heaps Versus Other Representations of Priority Queues
    5. Summary
    6. Exercises
  16. 10 The Graph ADT
    1. 10.1 Introduction to Graphs
    2. 10.2 The Graph Interface
    3. 10.3 Implementations of Graphs
      1. Array-Based Implementation
      2. Linked Implementation
    4. 10.4 Application: Graph Traversals
      1. Depth-First Searching
      2. Breadth-First Searching
    5. 10.5 Application: The Single-Source Shortest-Paths Problem
    6. Summary
    7. Exercises
  17. 11 Sorting and Searching Algorithms
    1. 11.1 Sorting
      1. A Test Harness
    2. 11.2 Simple Sorts
      1. Selection Sort
      2. Bubble Sort
      3. Insertion Sort
    3. 11.3 O(N log2N) Sorts
      1. Merge Sort
      2. Quick Sort
      3. Heap Sort
    4. 11.4 More Sorting Considerations
      1. Testing
      2. Efficiency
      3. Objects and References
      4. Comparing Objects
      5. Stability
    5. 11.5 Searching
      1. Sequential Searching
      2. High-Probability Ordering
      3. Sorted Collections
      4. Hashing
    6. Summary
    7. Exercises
  18. Appendix A: Java Reserved Words
  19. Appendix B: Operator Precedence
  20. Appendix C: Primitive Data Types
  21. Appendix D: ASCII Subset of Unicode
  22. Glossary
  23. Index

Product information

  • Title: Object-Oriented Data Structures Using Java, 4th Edition
  • Author(s): Dale
  • Release date: September 2016
  • Publisher(s): Jones & Bartlett Learning
  • ISBN: 9781284089103