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