You are previewing A Concise Introduction to Data Structures using Java.
O'Reilly logo
A Concise Introduction to Data Structures using Java

Book Description

A student-friendly text, A Concise Introduction to Data Structures Using Java takes a developmental approach, starting with simpler concepts first and then building toward greater complexity. Important topics, such as linked lists, are introduced gradually and revisited with increasing depth. More code and guidance are provided at the beginning, allowing students time to adapt to Java while also beginning to learn data structures. As students develop fluency in Java, less code is provided and more algorithms are outlined in pseudocode. The text is designed to support a second course in computer science with an emphasis on elementary data structures.

The clear, concise explanations encourage students to read and engage with the material, while partial implementations of most data structures give instructors the flexibility to develop some methods as examples and assign others as exercises. The book also supplies an introductory chapter on Java basics that allows students who are unfamiliar with Java to quickly get up to speed. The book helps students become familiar with how to use, design, implement, and analyze data structures, an important step on the path to becoming skilled software developers.

Table of Contents

  1. Preliminaries
  2. Series
  3. Dedication
  4. Preface
    1. To Instructors
    2. Feedback
    3. Acknowledgments
  5. About the Author
  6. Chapter 1 A Brief Introduction to Java
    1. 1.1 Basics
      1. Classes
      2. Types and Variables
      3. Primitive and Reference Types
      4. Primitive Types
      5. Operators
      6. Increment and Decrement
      7. Statements and Blocks
      8. Assignment
      9. Control Statements
      10. If Statements
      11. While Loops
      12. For Loops
      13. Switch
      14. Output Statements
      15. Methods
      16. Comments
      17. Compiling and Running Java Programs
    2. 1.2 Strings
      1. Concatenation
      2. String Methods
      3. Comparing Strings
    3. 1.3 Arrays
      1. Declaring Array References
      2. Creating Arrays
      3. Accessing Array Elements
      4. Enhanced For-Loop
      5. Linear Search
    4. 1.4 Using Objects
      1. Declaring Object References
      2. Creating Objects
      3. Accessing Fields and Calling Methods
      4. Object References
      5. Using equals()
      6. Destroying Objects
      7. StringBuilders
      8. String Tokenizing
    5. 1.5 Writing Classes
      1. Class Definitions
      2. Visibility
      3. Declaring and Initializing Fields
      4. Writing Methods
      5. Writing Constructors
      6. Overloading Methods and Constructors
      7. Instance and Static Methods
      8. Calling Static Methods from Other Classes
      9. Instance and Static Fields
      10. toString() Methods
      1. Listing 1.1
      2. Listing 1.2
      3. Listing 1.3
      4. Listing 1.4
      5. Listing 1.5
      1. Table 1.1
      2. Table 1.2
      3. Table 1.3
      4. Table 1.4
      5. Table 1.5
      6. Table 1.6
      7. Table 1.7
  7. Chapter 2 Algorithm Analysis
    1. 2.1 Big-O Notation
      1. Big-O Notation
      2. What to Count
      3. Best, Worst, and Average Case
      4. Performance Measurement
    2. 2.2 Sorting: Insertion Sort
      1. Insertion Sort
      2. Implementation
      3. Worst-Case Analysis
      4. Generating Random Data
      5. Using Java Libraries
    3. 2.3 Searching: Binary Search
      1. Implementation
      2. Sample Trace
      3. Analysis of Binary Search
      1. Listing 2.1
      2. Listing 2.2
      3. Listing 2.3
      1. Table 2.1
      2. Table 2.2
      3. Table 2.3
  8. Chapter 3 Integer Stacks
    1. 3.1 Stack Interface
      1. Abstract Data Types
      2. Java Interfaces
      3. Interface Types
      4. Classes Implement Interfaces
      5. Programming to Interfaces
    2. 3.2 Array Implementation
      1. Throwing Exceptions
      2. Resizing the Array
    3. 3.3 Linked Implementation
      1. Linked Lists
      2. Nodes
      3. Insertion at Front
      4. Deletion at Front
      5. Linked Implementation
      6. Nested Classes
      7. Null Pointer Exceptions
      1. Listing 3.1
      2. Listing 3.2
      3. Listing 3.3
      4. Listing 3.4
      1. Table 3.1
      2. Table 3.2
  9. Chapter 4 Generic Stacks
    1. 4.1 Generic Types
      1. Type Parameters
      2. Generic Stack ADT
      3. Type Parameters Inside Interface and Class Definitions
      4. Type Arguments
      5. Wrapper Classes
      6. Automatic Boxing and Unboxing
      7. Creating Generic Objects
    2. 4.2 Generic Stack Implementations
      1. Generic Nested Classes
      2. Generic Arrays
      3. Unchecked Casts
      4. Obsolete References
      5. Generic Array Stack
    3. 4.3 Evaluating Expressions: Background
      1. Binary Operations
      2. Prefix, Infix, and Postfix
      3. Evaluating Postfix Algorithm
      4. Infix to Postfix Algorithm
    4. 4.4 Evaluating Expressions: Implementations
      1. Operator Precedence
      2. toPostfix() Implementation
      3. Using Conditional Boolean Expressions
      4. evalPostfix() Implementation
      1. Listing 4.1
      2. Listing 4.2
      3. Listing 4.3
      4. Listing 4.4
      5. Listing 4.5
      6. Listing 4.6
      7. Listing 4.7
      1. Table 4.1
      2. Table 4.2
      3. Table 4.3
      4. Table 4.4
      5. Table 4.5
  10. Chapter 5 Queues
    1. 5.1 Interface and Linked Implementation
      1. Queue ADT
      2. Linked Implementation
      3. Insertion After a Node
      4. Deletion After a Node
      5. Managing the Tail
    2. 5.2 Array Implementation
      1. Basic Idea
      2. Problem: Drift
      3. Circular Array
      4. Resizing Circular Arrays
    3. 5.3 Inheritance: Fixed-Length Queues
      1. Examples: GPUs and Network Routers
      2. Inheritance
      3. Inheritance Hierarchies
      4. Is-A and Has-A Relationships
      5. Implementation
      6. Java Class Extensions
      7. Subclass Constructors
      8. Overriding Methods
      9. Protected Fields in the Superclass
      10. The Object Class
    4. Project: Fixed-Length Queue Simulation
      1. Model
      2. Clock-Based Simulations
      3. Random Tasks
      1. Listing 5.1
      2. Listing 5.2
      3. Listing 5.3
      4. Listing 5.4
      1. Table 5.1
      2. Table 5.2
      3. Table 5.3
  11. 6 Lists
    1. 6.1 Interface
      1. List Indexing
      2. List ADT
      3. Shifting
      4. Overloading Methods
      5. Arrays and Lists
    2. 6.2 Array Implementation
      1. Index Checking
      2. Shifting in an ArrayList
    3. 6.3 Linked Implementation
      1. Dummy Nodes
      2. Double Links
      3. Deletion with Double Links
      4. Traversals
      5. Indexed Access
      6. Performance
      7. Using Nodes and References
    4. 6.4 Iterators
      1. Iterators
      2. Iterables
      3. Linked List Iterator
      4. Privacy Issues
      5. Inner Classes
      6. Extending Interfaces
      7. Using Iterators
      1. Listing 6.1
      2. Listing 6.2
      3. Listing 6.3
      1. Table 6.1
      2. Table 6.2
      3. Table 6.3
  12. Chapter 7 Recursion
    1. 7.1 Mathematical Functions
      1. Recursive Functions in Java
      2. Tracing Recursive Calls
      3. Natural Recursions
    2. 7.2 Visualizing Recursion
      1. Recursive Call Trees
      2. Analyzing Recursive Functions
      3. Implementing Recursion
      4. Function Call Stack
      5. Visualizing the Call Stack
      6. Stack Traces
    3. 7.3 Recursive and Generalized Searches
      1. Public Wrapper Methods
      2. Generalized Linear Search: Objects
      3. Generalized Binary Search: Comparables
      4. Generic Methods
      5. Integer[] and int[]
    4. 7.4 Applications
      1. Longest Common Subsequence
      2. Towers of Hanoi
      3. Backtracking
      1. Listing 7.1
      2. Listing 7.2
      3. Listing 7.3
      4. Listing 7.4
      5. Listing 7.5
      1. Table 7.1
  13. Chapter 8 Trees
    1. 8.1 Definitions and Examples
      1. Expression Trees
      2. Binary Search Trees
      3. Representing General Trees as Binary Trees
    2. 8.2 Traversals
      1. Depth-First
      2. Breadth-First
    3. 8.3 Binary Tree Abstract Class
      1. Abstract Classes
      2. Binary Tree Class
      3. Project: A Collection Hierarchy
      1. Listing 8.1
      2. Listing 8.2
      1. Table 8.1
  14. Chapter 9 Binary Search Trees
    1. 9.1 Queries
      1. Search
      2. Minimum and Maximum
      3. Predecessor and Successor
      4. Conditional Operator
      5. Performance
    2. 9.2 Insertion
      1. Java Assertions
    3. 9.3 Deletion
      1. Deleting By Hand
      2. Nodes without Two Children
    4. 9.4 Performance
      1. Unsorted Lists
      2. Sorted Lists
      3. Binary Search Trees
      1. Listing 9.1
      2. Listing 9.2
      3. Listing 9.3
      4. Listing 9.4
      1. Table 9.1
  15. Chapter 10 Heaps
    1. 10.1 Priority Queue Interface and Array-Based Heaps
      1. Priority Queue Interface
      2. Heap Data Structure
      3. Complete Binary Trees
      4. Array-Based Binary Trees
      5. Parents and Children
      6. Generic Arrays of Comparable Elements
    2. 10.2 Insertion and Deletion
      1. Insertion and Heapifying Up
      2. Deletion
      3. Heapifying Down
    3. 10.3 Buildheap and Heapsort
      1. Buildheap
      2. Buildheap Performance
      3. Heapsort
      4. Project: Event-Based Simulation
      5. Events
      6. Checkout Line Simulation
      7. Modeling Customer Arrivals: Poisson Processes
      8. Modeling Normal Distributions
      9. Design
      1. Listing 10.1
      2. Listing 10.2
      3. Listing 10.3
      4. Listing 10.4
      5. Listing 10.5
      1. Table 10.1
  16. Chapter 11 Hash Tables
    1. 11.1 Map Interface and Linked Implementation
      1. Maps
      2. Linked Map
      3. Map Entries
    2. 11.2 Hash Tables
      1. Direct Addressing
      2. Hash Tables
      3. Collisions
      4. Hash Functions
      5. Integer Keys
      6. String and Object Keys
      7. Java Hashcodes
    3. 11.3 Chaining
      1. Implementation
      2. Generic Arrays Revisited
      3. Performance
      4. Space-Time Tradeoff
      5. Deletion
    4. 11.4 Linear Probing
      1. Linear Probing
      2. Implementation
      3. Performance
      4. Deletion
      5. Other Probe Sequences
      1. Listing 11.1
      2. Listing 11.2
      1. Table 11.1
  17. Bibliography