Data Structures and Abstractions with Java

Data Structures and Abstractions with Java™, 5th Edition
Title Page
Copyright
Welcome
Brief Table of Contents
New to This Edition
A Note to Students
Pedagogical Elements
Resources
Detailed Content Description
Acknowledgments
Contents
VideoNotes
Chapter Prerequisites
Introduction Organizing Data
Prelude Designing Classes
Encapsulation
Specifying Methods
Java Interfaces
Choosing Classes
Reusing Classes
Exercises
Projects
Chapter 1 Bags
The Bag
Specifying a Bag
Using the ADT Bag
Using an ADT Is Like Using a Vending Machine
The ADT Set
Java Class Library: The Interface Set
Chapter Summary
Programming Tip
Exercises
Projects
Java Interlude 1 Generics
Generic Data Types
Chapter 2 Bag Implementations That Use Arrays
Using a Fixed-Size Array to Implement the ADT Bag
Using Array Resizing to Implement the ADT Bag
The Pros and Cons of Using an Array to Implement the ADT Bag
Chapter Summary
Programming Tips
Exercises
Projects
Java Interlude 2 Exceptions
The Basics
Handling an Exception
Throwing an Exception
Chapter 3 A Bag Implementation That Links Data
Linked Data
A Linked Implementation of the ADT Bag
Removing an Item from a Linked Chain
A Class Node That Has Set and Get Methods
The Pros and Cons of Using a Chain to Implement the ADT Bag
Chapter Summary
Programming Tip
Exercises
Projects
Chapter 4 The Efficiency of Algorithms
Motivation
Measuring an Algorithm’s Efficiency
Big Oh Notation
Picturing Efficiency
The Efficiency of Implementations of the ADT Bag
Chapter Summary
Exercises
Projects
Chapter 5 Stacks
Specifications of the ADT Stack
Using a Stack to Process Algebraic Expressions
The Program Stack
Java Class Library: The Class Stack
Chapter Summary
Programming Tip
Exercises
Projects
Chapter 6 Stack Implementations
A Linked Implementation
An Array-Based Implementation
A Vector-Based Implementation
Chapter Summary
Exercises
Projects
Java Interlude 3 More About Exceptions
Programmer-Defined Exception Classes
Inheritance and Exceptions
The finally Block
Chapter 7 Queues, Deques, and Priority Queues
The ADT Queue
The ADT Deque
The ADT Priority Queue
Chapter Summary
Programming Tip
Exercises
Projects
Chapter 8 Queue, Deque, and Priority Queue Implementations
A Linked Implementation of a Queue
An Array-Based Implementation of a Queue
Circular Linked Implementations of a Queue
Java Class Library: The Class AbstractQueue
A Doubly Linked Implementation of a Deque
Possible Implementations of a Priority Queue
Chapter Summary
Programming Tip
Exercises
Projects
Chapter 9 Recursion
What Is Recursion?
Tracing a Recursive Method
Recursive Methods That Return a Value
Recursively Processing an Array
Recursively Processing a Linked Chain
The Time Efficiency of Recursive Methods
Tail Recursion
Using a Stack Instead of Recursion
Chapter Summary
Programming Tips
Exercises
Projects
Chapter 10 Lists
Specifications for the ADT List
Using the ADT List
Java Class Library: The Interface List
Java Class Library: The Class ArrayList
Chapter Summary
Exercises
Projects
Chapter 11 A List Implementation That Uses an Array
Using an Array to Implement the ADT List
The Efficiency of Using an Array to Implement the ADT List
Chapter Summary
Exercises
Projects
Chapter 12 A List Implementation That Links Data
Operations on a Chain of Linked Nodes
Beginning the Implementation
Continuing the Implementation
A Refined Implementation
The Efficiency of Using a Chain to Implement the ADT List
Java Class Library: The Class LinkedList
Chapter Summary
Exercises
Projects
Java Interlude 4 Iterators
What Is an Iterator?
The Interface Iterator
The Interface ListIterator
Chapter 13 Iterators for the ADT List
Ways to Implement an Iterator
A Separate Class Iterator
An Inner Class Iterator
Why Are Iterator Methods in Their Own Class?
An Array-Based Implementation of the Interface ListIterator
Chapter Summary
Programming Tip
Exercises
Projects
Chapter 14 Problem Solving with Recursion
A Simple Solution to a Difficult Problem
A Poor Solution to a Simple Problem
Languages and Grammars
Indirect Recursion
Backtracking
Chapter Summary
Exercises
Projects
Java Interlude 5 More About Generics
The Interface Comparable
Generic Methods
Bounded Type Parameters
Wildcards
Chapter 15 An Introduction to Sorting
Organizing Java Methods That Sort an Array
Selection Sort
Insertion Sort
Shell Sort
Comparing the Algorithms
Chapter Summary
Programming Tip
Exercises
Projects
Chapter 16 Faster Sorting Methods
Merge Sort
Quick Sort
Radix Sort
Comparing the Algorithms
Chapter Summary
Exercises
Projects
Java Interlude 6 Mutable and Immutable Objects
Mutable Objects
Immutable Objects
Companion Classes
Chapter 17 Sorted Lists
Specifications for the ADT Sorted List
A Linked Implementation
An Implementation That Uses the ADT List
Chapter Summary
Exercises
Projects
Java Interlude 7 Inheritance and Polymorphism
Further Aspects of Inheritance
Polymorphism
Chapter 18 Inheritance and Lists
Using Inheritance to Implement a Sorted List
Designing a Base Class
An Efficient Implementation of a Sorted List
Chapter Summary
Programming Tips
Exercises
Projects
Chapter 19 Searching
The Problem
Searching an Unsorted Array
Searching a Sorted Array
Searching an Unsorted Chain
Searching a Sorted Chain
Choosing a Search Method
Chapter Summary
Programming Tip
Exercises
Projects
Java Interlude 8 Generics Once Again
More Than One Generic Type
Chapter 20 Dictionaries
Specifications for the ADT Dictionary
Using the ADT Dictionary
Java Class Library: The Interface Map
Chapter Summary
Programming Tips
Exercises
Projects
Chapter 21 Dictionary Implementations
Array-Based Implementations
Linked Implementations
Chapter Summary
Programming Tips
Exercises
Projects
Chapter 22 Introducing Hashing
What Is Hashing?
Hash Functions
Resolving Collisions
Chapter Summary
Exercises
Projects
Chapter 23 Hashing as a Dictionary Implementation
The Efficiency of Hashing
Rehashing
Comparing Schemes for Collision Resolution
A Dictionary Implementation That Uses Hashing
Java Class Library: The Class HashMap
Java Class Library: The Class HashSet
Chapter Summary
Exercises
Projects
Chapter 24 Trees
Tree Concepts
Traversals of a Tree
Java Interfaces for Trees
Examples of Binary Trees
Examples of General Trees
Chapter Summary
Exercises
Projects
Chapter 25 Tree Implementations
The Nodes in a Binary Tree
An Implementation of the ADT Binary Tree
An Implementation of an Expression Tree
General Trees
Using a Binary Tree to Represent a General Tree
Chapter Summary
Programming Tips
Exercises
Projects
Java Interlude 9 Cloning
Cloneable Objects
Chapter 26 A Binary Search Tree Implementation
Getting Started
Searching and Retrieving
Traversing
Adding an Entry
Removing an Entry
The Efficiency of Operations
An Implementation of the ADT Dictionary
Chapter Summary
Exercises
Projects
Chapter 27 A Heap Implementation
Reprise: The ADT Heap
Using an Array to Represent a Heap
Adding an Entry
Removing the Root
Creating a Heap
Heap Sort
Chapter Summary
Exercises
Projects
Chapter 28 Balanced Search Trees
AVL Trees
2-3 Trees
2-4 Trees
Red-Black Trees
B-Trees
Chapter Summary
Exercises
Projects
Chapter 29 Graphs
Some Examples and Terminology
Traversals
Topological Order
Paths
Java Interfaces for the ADT Graph
Chapter Summary
Exercises
Projects
Chapter 30 Graph Implementations
An Overview of Two Implementations
Vertices and Edges
An Implementation of the ADT Graph
Chapter Summary
Exercises
Projects
Appendix A Documentation and Programming Style
Naming Variables and Classes
Indenting
Comments
Appendix B Java Classes
Objects and Classes
Using the Methods in a Java Class
Defining a Java Class
Enumeration as a Class
Packages
Appendix C Creating Classes from Other Classes
Composition
Inheritance
Type Compatibility and Superclasses
Index
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W
Supplement 1 Java Basics
Introduction
Elements of Java
Simple Input and Output Using the Keyboard and Screen
The if-else Statement
The switch Statement
Enumerations
Scope
Loops
The Class String
The Class StringBuilder
Using Scanner to Extract Pieces of a String
Arrays
Wrapper Classes
Supplement 2 File Input and Output
Preliminaries
Text Files
Binary Files
Glossary
Answers to Study Questions
Prelude
Chapter 1
Chapter 2
Chapter 3
Chapter 4
Chapter 5
Chapter 6
Chapter 7
Chapter 8
Chapter 9
Chapter 10
Chapter 11
Chapter 12
Chapter 13
Chapter 14
Java Interlude 5
Chapter 15
Chapter 16
Chapter 17
Chapter 18
Chapter 19
Chapter 20
Chapter 21
Chapter 22
Chapter 24
Chapter 25
Java Interlude 9
Chapter 26
Chapter 27
Chapter 28
Chapter 29
Appendix B
Appendix C