Classic Data Structures in Java
With this book, Tim Budd looks at data structures by providing a solid foundation on the ADT, and uses the graphical elements found in Java when possible.
The beginning chapters provide the foundation on which everything else will be built. These chapters define the essential concept of the abstract data type (ADT), and describe the tools used in the evaluation and analysis of data structures. The book moves on to provide a detailed description of the two most important fundamental data abstractions, the vector and the linked list, providing an explanation of some of the more common variations on these fundamental ideas.
Next, the material considers data structures applicable to problems in which the order that values are added to a collection is important, followed by a consideration of the various different ways in which binary trees are used in the creation of data structures. The last few chapters consider a sequence of more advanced data structures. Most are constructed as adaptors built on top of earlier abstractions. Hash tables are introduced first as a technique for implementing simple collections, and later as a tool for developing efficient maps. Lastly, the graph data type is considered. Here there are several alternative data structures presentations in common use, and the emphasis in this chapter is more on the development and analysis of useful algorithms than on any particular data structure.
- An object-oriented mindset is applied throughout.
- The clear separation between ADT (interface) and implementation is emphasized throughout.
- A rigorous approach to development in encouraged, with techniques for developing formal proofs of programs being presented, and proofs of programs appearing throughout the text.
- An explorational and visual approach is encouraged by providing tools that make it easy to create a visual record of execution time, and Experiments that will help see aspects of execution that may not be obvious from the code.
- Important software patterns are highlighted, and the use of patterns is emphasized from the beginning.
- Graphical elements, chosen to minimize the unnecessary detail and emphasize the important lessons of Java, are used to motivate the student's interest in the material.
- Sidebars are included throughout so that readers can then peruse additional information as they choose.
- End of Chapter material is designed to aid students comprehension of the material just presented, including: a chapter summary, glossary of key terms, numerous basic study questions, a collection of thought-provoking exercises, and a series of programming projects.
- An appendix with an overview of Java syntax makes this book appropriate for readers without a Java background.
- Written by Tim Budd, author of numerous other successful texts, including Classic Data Structures in C++, Data Structures in C++ with the STL, Introduction to Object Oriented Programming, and C++ for Java Programmers.
(All chapters conclude with "Chapter Summary", "Further Information", "Study Questions", "Exercises", and "Programming Projects".)
1. The Management of Complexity.
Abstraction, Information Hiding, and Layering.
Division into Parts.
Interface and Implementation.
The Service View.
Repetition and Recursion.
Layers of Specialization.
2. Abstract Data Types.
Interfaces and Polymorphism.
Abstract Data Types.
The Fundamental ADTs.
Sorted, Comparator and Comparable.
Stack, Queue and Deque.
FindMin and FindNth.
Indexed Collections and Sorting Algorithms.
Recipes as Algorithms.
Analyzing Computer Algorithms.
Description of the Result.
Time to Execute.
4. Execution-Time Measurement.
Execution Time of Programming Constructs.
Summing Algorithmic Execution Times.
The Importance of Fast Algorithms.
Benchmarking and Actual Execution Times.
5. Increasing Confidence in Correctness.
Asserting That the Outcome is Correct.
Progress Toward an Objective.
Manipulating Unnamed Quantities.
A Visual Vector.
7. Sorting Vectors.
Finding the nth Element.
8. Linked Lists.
The LinkedList Abstraction.
9. List Variations.
Execution Timings for Merge Operations.
Checking for Balanced Parentheses.
Towers of Hanoi, Revisited.
A Four-Function Calculator.
A Solitaire Program.
Implementation of the Stack Abstraction.
Depth- and Breadth-First Search.
An Implementation: The IndexedDeque.
The Caterpillar Game.
A Pastry Factory Simulation.
Implementation of the Queue Abstraction.
The Ring Buffer Queue.
Piped Input/Output Streams.
Dynamic Memory Implementation.
Preorder Tree Traversal.
In-Order Tree Traversal.
Level-Order Tree Traversal.
Binary Tree Representation of General Trees.
14. Binary Search Trees.
15. Priority Queues.
Application—Discrete Event-Driven Simulation.
Ice Cream Store Simulation.
16. Hash Tables.
Hash Functions in the Java Standard Library.
Hash Table Sorting Algorithms.
The Hashtable Data Type.
Application—Ranking Poker Hands.
An Address Database.
Searching Problems and Maps.
Set Union, Intersection, and Differences.
Sorted List Sets.
Application—A Spelling Checker.
The Union-Find Problem.
The BitSet Abstraction.
Weighted-Edge List Representation.
Other Graph Problems.
Depth-First Search Spanning Tree.
Problem-The Traveling Salesman.
Appendix A. Java Syntax.
Data Field Declaration.
Data Field and Method Access.
Appendix B. Import Libraries.
Appendix C. Data Structures in the Java Standard Library.
Enumerators and Iterators.
Stack, Queue, and Deque.
Binary Search Tree.