You are previewing Data Structures and the Java Collections Framework, Third Edition.
O'Reilly logo
Data Structures and the Java Collections Framework, Third Edition

Book Description

Instead of emphasizing the underlying mathematics to get programmers to build their own data structures, Collins enables them to manipulate existing structures in the Java Collections Library. This allows them to learn through coding rather than by doing proofs. 23 lab projects and hundreds of programming examples are integrated throughout the pages to build their intuition. The approach this book takes helps programmers quickly learn the concepts that underlie data structures.

Table of Contents

  1. Cover Page
  2. Title Page
  3. Copyright
  4. Dedication
  5. Brief Contents
  6. Contents
  7. PREFACE
    1. WHAT'S NEW IN THE THIRD EDITION
    2. THE JAVA COLLECTIONS FRAMEWORK
    3. OTHER IMPLEMENTATIONS CONSIDERED
    4. JUNIT AND TEST-FIRST DEVELOPMENT
    5. PEDAGOGICAL FEATURES
    6. SUPPORT MATERIAL
    7. SYNOPSES OF THE CHAPTERS
    8. APPENDIXES
    9. ORGANIZATION OF THE LABS
    10. ACKNOWLEDGEMENTS
  8. CHAPTER 0: Introduction to Java
    1. CHAPTER OBJECTIVES
    2. 0.1 Java Fundamentals
    3. 0.2 Classes
    4. 0.3 Arrays
    5. 0.4 Arguments and Parameters
    6. 0.5 Output Formatting
    7. CROSSWORD PUZZLE
    8. PROGRAMMING EXERCISES
  9. CHAPTER 1: Object-Oriented Concepts
    1. CHAPTER OBJECTIVES
    2. 1.1 Data Abstraction
    3. 1.2 Abstract Methods and Interfaces
    4. 1.3 Inheritance
    5. 1.4 Information Hiding
    6. 1.5 Polymorphism
    7. 1.6 The Unified Modeling Language
    8. SUMMARY
    9. CROSSWORD PUZZLE
    10. CONCEPT EXERCISES
    11. PROGRAMMING EXERCISES
  10. CHAPTER 2: Additional Features of Programming and Java
    1. CHAPTER OBJECTIVES
    2. 2.1 Static Variables, Constants and Methods
    3. 2.2 Method Testing
    4. 2.3 Exception Handling
    5. 2.4 File Output
    6. 2.5 System Testing
    7. 2.6 The Java Virtual Machine
    8. 2.7 Packages
    9. 2.8 Overriding the Object Class's equals Method
    10. SUMMARY
    11. CROSSWORD PUZZLE
    12. CONCEPT EXERCISES
    13. PROGRAMMING EXERCISES
  11. CHAPTER 3: Analysis of Algorithms
    1. CHAPTER OBJECTIVES
    2. 3.1 Estimating the Efficiency of Methods
    3. 3.2 Run-Time Analysis
    4. SUMMARY
    5. CROSSWORD PUZZLE
    6. CONCEPT EXERCISES
    7. PROGRAMMING EXERCISES
  12. CHAPTER 4: The Java Collections Framework
    1. CHAPTER OBJECTIVES
    2. 4.1 Collections
    3. 4.2 Some Details of the Java Collections Framework
    4. SUMMARY
    5. CROSSWORD PUZZLE
    6. CONCEPT EXERCISES
    7. PROGRAMMING EXERCISES
  13. CHAPTER 5: Recursion
    1. CHAPTER OBJECTIVES
    2. 5.1 Introduction
    3. 5.2 Factorials
    4. 5.3 Decimal to Binary
    5. 5.4 Towers of Hanoi
    6. 5.5 Searching an Array
    7. 5.6 Backtracking
    8. 5.7 Indirect Recursion
    9. 5.8 The Cost of Recursion
    10. SUMMARY
    11. CROSSWORD PUZZLE
    12. CONCEPT EXERCISES
    13. PROGRAMMING EXERCISES
  14. CHAPTER 6: Array-Based Lists
    1. CHAPTER OBJECTIVES
    2. 6.1 The List Interface
    3. 6.2 The ArrayList Class
    4. 6.3 Application: High-Precision Arithmetic
    5. SUMMARY
    6. CROSSWORD PUZZLE
    7. CONCEPT EXERCISES
    8. PROGRAMMING EXERCISES
  15. CHAPTER 7: Linked Lists
    1. CHAPTER OBJECTIVES
    2. 7.1 What is a Linked List?
    3. 7.2 The SinglyLinkedList Class—A Singly-Linked, Toy Class!
    4. 7.3 Doubly-Linked Lists
    5. 7.4 Application: A Line Editor
    6. SUMMARY
    7. CROSSWORD PUZZLE
    8. CONCEPT EXERCISES
    9. PROGRAMMING EXERCISES
  16. CHAPTER 8: Stacks and Queues
    1. CHAPTER OBJECTIVES
    2. 8.1 Stacks
    3. 8.2 Queues
    4. SUMMARY
    5. CROSSWORD PUZZLE
    6. CONCEPT EXERCISES
    7. PROGRAMMING EXERCISES
  17. CHAPTER 9: Binary Trees
    1. CHAPTER OBJECTIVES
    2. 9.1 Definition of Binary Tree
    3. 9.2 Properties of Binary Trees
    4. 9.3 The Binary Tree Theorem
    5. 9.4 External Path Length
    6. 9.5 Traversals of a Binary Tree
    7. SUMMARY
    8. CROSSWORD PUZZLE
    9. CONCEPT EXERCISES
  18. CHAPTER 10: Binary Search Trees
    1. CHAPTER OBJECTIVES
    2. 10.1 Binary Search Trees
    3. 10.2 Balanced Binary Search Trees
    4. SUMMARY
    5. CROSSWORD PUZZLE
    6. CONCEPT EXERCISES
    7. PROGRAMMING EXERCISES
  19. CHAPTER 11: Sorting
    1. CHAPTER OBJECTIVES
    2. 11.1 Introduction
    3. 11.2 Simple Sorts
    4. 11.3 The Comparator Interface
    5. 11.4 How Fast Can we Sort?
    6. 11.5 Radix Sort
    7. SUMMARY
    8. CROSSWORD PUZZLE
    9. CONCEPT EXERCISES
    10. PROGRAMMING EXERCISES
  20. CHAPTER 12: Tree Maps and Tree Sets
    1. CHAPTER OBJECTIVES
    2. 12.1 Red-Black Trees
    3. 12.2 The Map Interface
    4. 12.3 The TreeMap Implementation of the SortedMap Interface
    5. 12.4 Application of the TreeMap Class: a Simple Thesaurus
    6. 12.5 The TreeSet Class
    7. SUMMARY
    8. CROSSWORD PUZZLE
    9. CONCEPT EXERCISES
    10. PROGRAMMING EXERCISES
  21. CHAPTER 13: Priority Queues
    1. CHAPTER OBJECTIVES
    2. 13.1 Introduction
    3. 13.2 The PriorityQueue Class
    4. 13.3 Implementation Details of the PriorityQueue Class
    5. 13.4 The heapSort Method
    6. 13.5 Application: Huffman Codes
    7. SUMMARY
    8. CROSSWORD PUZZLE
    9. CONCEPT EXERCISES
    10. PROGRAMMING EXERCISES
  22. CHAPTER 14: Hashing
    1. CHAPTER OBJECTIVES
    2. 14.1 A Framework to Analyze Searching
    3. 14.2 Review of Searching
    4. 14.3 The HashMap Implementation of the Map Interface
    5. 14.4 The HashSet Class
    6. 14.5 Open-Address Hashing (optional)
    7. SUMMARY
    8. CROSSWORD PUZZLE
    9. CONCEPT EXERCISES
    10. PROGRAMMING EXERCISES
  23. CHAPTER 15: Graphs, Trees, and Networks
    1. CHAPTER OBJECTIVES
    2. 15.1 Undirected Graphs
    3. 15.2 Directed Graphs
    4. 15.3 Trees
    5. 15.4 Networks
    6. 15.5 Graph Algorithms
    7. 15.6 A Network Class
    8. 15.7 Backtracking Through A Network
    9. SUMMARY
    10. CROSSWORD PUZZLE
    11. CONCEPT EXERCISES
    12. PROGRAMMING EXERCISES
  24. APPENDIX 1: Additional Features of the JAVA Collections Framework
    1. A1.1 Introduction
    2. A1.2 Serialization
    3. A1.3 Fail-Fast Iterators
  25. APPENDIX 2: Mathematical Background
    1. A2.1 Introduction
    2. A2.2 Functions and Sequences
    3. A2.3 Sums and Products
    4. A2.4 Logarithms
    5. A2.5 Mathematical Induction
    6. A2.6 Induction and Recursion
    7. CONCEPT EXERCISES
  26. APPENDIX 3: Choosing a Data Structure
    1. A3.1 Introduction
    2. A3.2 Time-Based Ordering
    3. A3.3 Index-Based Ordering
    4. A3.4 Comparison-Based Ordering
    5. A3.5 Hash-Based Ordering
    6. A3.6 Space Considerations
    7. A3.7 The Best Data Structure?
  27. REFERENCES
  28. INDEX