Object-Oriented Data Structures Using Java by Dale, Nell -- Read -- Imperial Library of Trantor

Index

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

← Prev
Back
Next →

← Prev
Back
Next →