You are previewing Data Structures and Algorithms Using Java.
O'Reilly logo
Data Structures and Algorithms Using Java

Book Description

With an accessible writing style and manageable amount of content, Data Structures and Algorithms Using Java is the ideal text for your course. This outstanding text correlates to the recommended syllabus put forth by the Association of Computing Machinery standard curriculum guidelines. The author has produced a resource that is more readable and instructional than any other, without compromising the scope of the ACM CS103, Data Structures and Algorithms, course material. The text’s unique, student-friendly pedagogical approach and organizational structure will keep students engaged in the process of self-directed investigative discovery both inside and outside the classroom. The pedagogical features of the text, based on the author’s 30 years of teaching experience, include succinct code examples, a unique common template used as the organizational basis of each chapter, the use of pseudocode to present the major algorithms developed in the text, nearly 300 carefully designed figures, and a concise review of Java.

Table of Contents

  1. Cover Page
  2. Title Page
  3. Copyright Page
  4. Dedecation Page
  5. Contents
  6. Preface
  7. Chapter 1 - Overview and Java Review
    1. 1.1 - Data Structures
      1. 1.1.1 - What is Data?
      2. 1.1.2 - What is a Data Structure?
    2. 1.2 - Selecting a Data Structure
      1. 1.2.1 - The Data Structure's Impact on Performance
      2. 1.2.2 - Determining the Performance of a Data Structure
      3. 1.2.3 - The Trade-Off Process
    3. 1.3 - Fundamental Concepts
      1. 1.3.1 - Terminology
      2. 1.3.2 - Access Modes
      3. 1.3.3 - Linear Lists
      4. 1.3.4 - Data Structure Operations
      5. 1.3.5 - Implementing a Programmer-Defined Data Structure
      6. 1.3.6 - Procedural Abstractions and Abstract Data Types (ADTs)
      7. 1.3.7 - Encapsulation
    4. 1.4 - Calculating Speed (Time Complexity)
      1. 1.4.1 - Big-O Analysis(O Standing for Order of Magnitude)
      2. 1.4.2 - Algorithm Speed
      3. 1.4.3 - Relative Speed of Algorithms
      4. 1.4.4 - Absolute Speed of an Algorithm
      5. 1.4.5 - Data Structure Speed
    5. 1.5 - Calculating Memory Overhead (Space Complexity)
    6. 1.6 - Java Review
      1. 1.6.1 - Arrays of Primitive Variables
      2. 1.6.2 - Definition of a Class
      3. 1.6.3 - Declaration of an Object
      4. 1.6.4 - Accessing Objects
      5. 1.6.5 - Standard Method Name Prefixes
      6. 1.6.6 - Shallow and Deep Copies
      7. 1.6.7 - Declaration of an Array of Objects
      8. 1.6.8 - Objects that Contain Objects as Data Members
      9. 1.6.9 - Classes that Extend Classes, Inheritance
      10. 1.6.10 - Parent and Child References
      11. 1.6.11 - Generic Types
    7. Knowledge Exercises
    8. Programming Exercises
  8. Chapter 2 - Array-Based Structures
    1. 2.1 - The Built-in Structure Array
      1. 2.1.1 - Multidimensional Arrays
    2. 2.2 - Programmer-Defined Array Structures
      1. 2.2.1 - Unsorted Array
      2. 2.2.2 - Sorted Array
      3. 2.2.3 - Unsorted-Optimized Array
      4. 2.2.4 - Error Checking
    3. 2.3 - Implementation of the Unsorted-Optimized Array Structure
      1. 2.3.1 - Baseline Implementation
      2. 2.3.2 - Utility Methods
    4. 2.4 - Expandable Array-Based Structures
    5. 2.5 - Generic Data Structures
      1. 2.5.1 - Design Considerations
      2. 2.5.2 - Generic Implementation of the Unsorted-Optimized Array
      3. 2.5.3 - Client-Side Use of Generic Structures
      4. 2.5.4 - Heterogeneous Generic Data Structures
    6. 2.6 - Java's ArrayList Class
    7. Knowledge Exercises
    8. Programming Exercises
  9. Chapter 3 - Restricted Structures
    1. 3.1 - Restricted Structures
    2. 3.2 - Stack
      1. 3.2.1 - Stack Operations, Terminology, and Error Conditions
      2. 3.2.2 - Classical Model of a Stack
      3. 3.2.3 - A Stack Application: Evaluation of Arithmetic Expressions
      4. 3.2.4 - Expanded Model of a Stack
    3. 3.3 - Queue
      1. 3.3.1 - Queue Operations, Terminology, and Error Conditions
      2. 3.3.2 - Classical Model of a Queue
      3. 3.3.3 - Queue Applications
      4. 3.3.4 - Expanded Model of a Queue
    4. 3.4 - Generic Implementation of the Classic Stack, a Methodized Approach
      1. 3.4.1 - Generic Conversion Methodology
    5. 3.5 - Priority Queues
    6. 3.6 - Java's Stack Class
    7. Knowledge Exercises
    8. Programming Exercises
  10. Chapter 4 - Linked Lists and Iterators
    1. 4.1 - Noncontiguous Structures
    2. 4.2 - Linked Lists
    3. 4.3 - Singly Linked Lists
      1. 4.3.1 - Basic Operation Algorithms
      2. 4.3.2 - Implementation
      3. 4.3.3 - Performance of the Singly Linked List
      4. 4.3.4 - A Stack Implemented as a Singly Linked List
    4. 4.4 - Other Types of Linked Lists
      1. 4.4.1 - Circular Singly Linked List
      2. 4.4.2 - Double-Ended Singly Linked List
      3. 4.4.3 - Sorted Singly Linked List
      4. 4.4.4 - Doubly Linked List
      5. 4.4.5 - Multilinked List
    5. 4.5 - Iterators
      1. 4.5.1 - Implementation of an Iterator
      2. 4.5.2 - Multiple Iterators
    6. 4.6 - Java's LinkedList Class and ListIterator Interface
    7. Knowledge Exercises
    8. Programming Exercises
  11. Chapter 5 - Hashed Data Structures
    1. 5.1 - Hashed Data Structures
    2. 5.2 - Hashing Access Algorithms
      1. 5.2.1 - A Hashing Example
    3. 5.3 - Perfect Hashed Data Structures
      1. 5.3.1 - Direct Hashed Structure
    4. 5.4 - Nonperfect Hashed Structures
      1. 5.4.1 - Primary Storage Area Size
      2. 5.4.2 - Preprocessing Algorithms
      3. 5.4.3 - Hashing Functions
      4. 5.4.4 - Collision Algorithms
      5. 5.4.5 - The Linear Quotient (LQHashed) Data Structure Implementation
      6. 5.4.6 - Dynamic Hashed Structures
    5. Knowledge Exercises
    6. Programming Exercises
  12. Chapter 6 - Recursion
    1. 6.1 - What is Recursion?
    2. 6.2 - Understanding Recursive Algorithms
      1. 6.2.1 - n Factorial
      2. 6.2.2 - The Code of a Recursive Algorithm
      3. 6.2.3 - Tracing a Recursive Method's Execution Path
    3. 6.3 - Formulating a Recursive Algorithm
      1. 6.3.1 - Definitions
      2. 6.3.2 - Methodology
      3. 6.3.3 - Practice Problems
    4. 6.4 - Problems with Recursion
      1. 6.4.1 - Dynamic Programming Applied to Recursion
    5. 6.5 - Backtracking, an Application of Recursion
      1. 6.5.1 - A Generalized Backtracking Algorithm
      2. 6.5.2 - Algorithm Adaptation Methodology
    6. Knowledge Exercises
    7. Programming Exercises
  13. Chapter 7 - Trees
    1. 7.1 - Trees
      1. 7.1.1 - Graphics and Terminology of Trees
    2. 7.2 - Binary Trees
      1. 7.2.1 - Terminology
      2. 7.2.2 - Mathematics
    3. 7.3 - Binary Search Trees
      1. 7.3.1 - Basic Operation Algorithms
      2. 7.3.2 - Performance
      3. 7.3.3 - Implementation
      4. 7.3.4 - Standard Tree Traversals
      5. 7.3.5 - Balanced Search Trees
      6. 7.3.6 - Array Implementation of a Binary Search Tree
      7. 7.3.7 - Performance
      8. 7.3.8 - Java's TreeMap Data Structure
    4. Knowledge Exercises
    5. Programming Exercises
  14. Chapter 8 - Sorting
    1. 8.1 - Sorting
    2. 8.2 - Sorting Algorithm Speed
      1. 8.2.1 - Minimum Sort Effort
      2. 8.2.2 - An Implementation Issue Affecting Algorithm Speed
    3. 8.3 - Sorting Algorithms
      1. 8.3.1 - The Binary Tree Sort
      2. 8.3.2 - The Bubble Sort
      3. 8.3.3 - The Heap Sort
      4. 8.3.4 - The Merge Sort
      5. 8.3.5 - Quicksort
    4. Knowledge Exercises
    5. Programming Exercises
  15. Chapter 9 - Graphs
    1. 9.1 - Introduction
      1. 9.1.1 - Graphics and Terminology of Graphs
    2. 9.2 - Representing Graphs
      1. 9.2.1 - Representing Vertices
      2. 9.2.2 - Representing Edges
    3. 9.3 - Operations Performed on Graphs
    4. 9.4 - Implementing Graphs in the Vertex Number Mode
    5. 9.5 - Traversing Graphs
      1. 9.5.1 - Depth-First Traversal
      2. 9.5.2 - Breadth-First Traversal
    6. 9.6 - Connectivity and Paths
      1. 9.6.1 - Connectivity of Undirected Graphs
      2. 9.6.2 - Connectivity of Directed Graphs
      3. 9.6.3 - Spanning Trees
      4. 9.6.4 - Shortest Paths
    7. Knowledge Exercises
    8. Programming Exercises
  16. Appendices
    1. Appendix A - ASCII Table
    2. Appendix B - Derivation of the Average Search Length of a Nondirect Hashed Data Structure
    3. Appendix C - Proof That If an Integer, P, is not Evenly Divisible by an Integer Less Than the Square Root of P, It is a Prime Number
    4. Appendix D - Calculations to Show That (n + 1) (log2(n + 1) − 2) is the Minimum Sort Effort for the Binary Tree Sort
  17. Glossary
  18. Index