This book provides a practical introduction to data structures from a viewpoint of abstract thinking and problem solving, as well as the use of Java. It does this through what remains a unique approach that clearly separates each data structure’s interface (how to use a data structure) from it’s implementation (how to actually program that structure) into different parts of the book. Part I (Tour of Java), Part II (Algorithms and Building Blocks), and Part III (Applications) lay the groundwork by discussing basic concepts and tools and providing some practical examples, but implementation of data structures is not shown until Part IV (Implementations), forcing the reader to think about the functionality of the data structures before the hash table is implemented.
The third edition of Data Structures and Problem Solving Using Java incorporates the enhancements of Java 5.0. It includes coverage of generic programming, and content on the design of generic collection classes. This book is appropriate for readers who are familiar with basic Java programming concepts or are new to the language and want to learn how it treats data structures concepts.
Table of Contents:
Part One: Tour of Java
Chapter 1: Primitive Java 1.1 The General Environment
1.2 The First Program
1.3 Primitive Types
1.4 Basic Operators
1.5 Conditional Statements
1.6 Methods
Summary
Key Concepts
Common Errors
On the Internet
Exercises
References
Chapter 2: Reference Types 2.1 What is a Reference?
2.2 Basics of Objects and References
2.3 Strings
2.4 Arrays
2.5 Exception Handling
2.6 Input and Output
Summary
Key Concepts
Common Errors
On the Internet
Exercises
References
Chapter 3: Objects and Classes
3.1 What is Object-Oriented Programming?
3.2 A Simple Example
3.3 javadoc
3.4 Basic Methods
3.5 Additional Constructs
3.6 Packages
3.7 A Design Pattern: Composite (pair)
Summary
Key Concepts
Common Errors
On the Internet
Exercises
References
Chapter 4: Inheritance
4.1 What is Inheritance?
4.2 Designing Hierarchies
4.3 Multiple Inheritance
4.4 The Interface
4.5 Fundamental Inheritance in Java
4.6 Implementing Generic Components Using Inheritance
4.7 Implementing Generic Components Using Java 1.5 Generics
4.8 The Functor (Function Objects)
4.9 Dynamic Dispatch Details
Summary
Key Concepts
Common Errors
On the Internet
Exercises
References
Part Two: Algorithms and Building Blocks
Chapter 5: Algorithm Analysis
5.1 What is Algorithm Analysis?
5.2 Examples of Algorithm Running Times
5.3 The Maximum Contiguous Subsequence Sum Problem
5.4 General Big-Oh Rules
5.5 The Logarithm
5.6 Static Searching Problem
5.7 Checking on Algorithm Analysis
5.8 Limitations of Big-Oh Analysis
Summary
Key Concepts
Common Errors
On the Internet
Exercises
References
Chapter 6: The Collections API
6.1 Introduction
6.2 The Iterator Pattern
6.3 Collections API: Containers and Iterators
6.4 Generic Algorithms
6.5 The List Interface
6.6 Stacks and Queues
6.7 Sets
6.8 Maps
6.9 Priority Queues
Summary
Key Concepts
Common Errors
On the Internet
Exercises
References
Chapter 7: Recursion
7.1 What is Recursion?
7.2 Background: Proofs by Mathematical Induction
7.3 Basic Recursion
7.4 Numerical Applications
7.5 Divide-and-Conquer Algorithms
7.6 Dynamic Programming
7.7 Backtracking
Chapter 8: Sorting Algorithms
8.1 Why is Sorting Important?
8.2 Preliminaries
8.3 Analysis of the Insertion Sort and Other Simple Sorts
8.4 Shellsort
8.5 Mergesort
8.6 Quicksort
8.7 Quickselect
8.8 A Lower Bound for Sorting
Summary
Key Concepts
Common Errors
On the Internet
Exercises
References
Chapter 9: Randomization
9.1 Why do we need random numbers?
9.2 Random Number Generators
9.3 Nonuniform Random Numbers
9.4 Generating a Random Permutation
9.5 Randomized Algorithms
9.6 Randomized Primality Testing
Summary
Key Concepts
Common Errors
On the Internet
Exercises
References
Part Three: Applications
Chapter 10: Fun and Games
10.1 Word Search Puzzles
10.2 The Game of Tic-Tac-Toe
Summary
Key Concepts
Common Errors
On the Internet
Exercises
References
Chapter 11: Stacks and Compilers
11.1 Balanced-Symbol Checker
11.2 A Simple Calculator
Summary
Key Concepts
Common Errors
On the Internet
Exercises
References
Chapter 12: Utilities
12.1 File Compression
12.2 A Cross-Reference Generator
Summary
Key Concepts
Common Errors
On the Internet
Exercises
References
Chapter 13: Simulation
13.1 The Josephus Problem
13.2 Event-Driven Simulation
Summary
Key Concepts
Common Errors
On the Internet
Exercises
Chapter 14: Graphs and Paths
14.1 Definitions
14.2 Unweighted Shortest-Path Problem
14.3 Positive-Weighted, Shortest-Path Problem
14.4 Negative-Weighted, Shortest-Path Problem
14.5 Path Problems in Acyclic Graphs
Summary
Key Concepts
Common Errors
On the Internet
Exercises
References
Part Four: Implementations
Chapter 15: Inner Classes and Implementation of ArrayList
15.1 Iterators and Nested Classes
15.2 Iterators and Inner Classes
15.3 The AbstractCollection Class
15.4 StringBuilder
15.5 Implementation of ArrayList with an Iterator
Summary
Key Concepts
Common Errors
On the Internet
Exercises
Chapter 16: Stacks and Queues
16.1 Dynamic Array Implementations
16.2 Linked List Implementations
16.3 Comparison of the Two Methods
16.4 The java.util.Stack Class
16.5 Double-Ended Queues
Summary
Key Concepts
Common Errors
On the Internet
Exercises
Chapter 17: Linked Lists
17.1 Basic Ideas
17.2 Java Implementation
17.3 Doubly Linked Lists and Circularly Linked Lists
17.4 Sorted Linked Lists
17.5 Implementing the Collections api LinkedList Class
Summary
Key Concepts
Common Errors
On the Internet
Exercises
Chapter 18: Trees
18.1 General Trees
18.2 Binary Trees
18.3 Recursion and Trees
18.4 Tree Traversal: Iterator Classes
Summary
Key Concepts
Common Errors
On the Internet
Exercises
Chapter 19: Binary Search Trees
19.1 Basic Ideas
19.2 Order Statistics
19.3 Analysis of Binary Search Tree Operations
19.4 AVL Trees
19.5 Red-Black Trees
19.6 AA-Trees
19.7 Implementing the Collections api TreeSet and TreeMap Classes
19.8 B-Trees
Summary
Key Concepts
Common Errors
On the Internet
Exercises
References
Chapter 20: Hash Tables
20.1 Basic Ideas
20.2 Hash Function
20.3 Linear Probing
20.4 Quadratic Probing
20.5 Separate Chaining Hashing
20.6 Hash Tables versus Binary Search Trees
20.7 Hashing Applications
Summary
Key Concepts
Common Errors
On the Internet
Exercises
References
Chapter 21: A Priority Queue: The Binary Heap
21.1 Basic Ideas
21.2 Implementation of the Basic Operations
21.3 The buildHeap Operation: Linear-Time Heap Construction
21.4 Advanced Operations: decreaseKey and merge
21.5 Internal Sorting: Heapsort
21.6 External Sorting
Summary
Key Concepts
Common Errors
On the Internet
Exercises
References
Part Five: Advanced Data Structures
Chapter 22: Splay Trees
22.1 Self-Adjustment and Amortized Analysis
22.2 The Basic Bottom-Up Splay Tree
22.3 Basic Splay Tree Operations
22.4 Analysis of Bottom-Up Splaying
22.5 Top-Down Splay Trees
22.6 Implementation of Top-Down Splay Trees
22.7 Comparison of the Splay Tree with Other Search Trees
Summary
Key Concepts
Common Errors
On the Internet
Exercises
References
Chapter 23: Merging Priority Queues
23.1 The Skew Heap
23.2 The Pairing Heap
Summary
Key Concepts
Common Errors
On the Internet
Exercises
References
Chapter 24: The Disjoint Set Class
24.1 Equivalence Relations
24.2 Dynamic Equivalence and Applications
24.3 The Quick-Find Algorithm
24.4 The Quick-Union Algorithm
24.5 Java Implementation
24.6 Worst Case for Union-by-Rank and Path Compression
Summary
Key Concepts
Common Errors
On the Internet
Exercises
References
Appendix A: Operators
Appendix B: Graphical User Interfaces
B.1 The Abstract Window Toolkit and Swing
B.2 Basic Objects in Swing
B.3 Basic Principles
Summary
Key Concepts
Common Errors
On the Internet
Exercises
References
Appendix C: Bitwise Operators
Index
