Data Structures and Problem Solving Using Java: United States Edition

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