## Table of Contents

1. Introduction to Data Structures and Algorithms

1.1 Data structures

1.2 Introduction to algorithms

1.3 Relation between data structures and algorithms

1.4 Abstract data types

1.5 Applications of ADTs

1.6 Algorithm efficiency

2. Searching and Algorithm Analysis

2.1 Searching and algorithms

2.2 Binary search

2.3 Java: Linear and binary search

2.4 Constant time operations

2.5 Growth of functions and complexity

2.6 O notation

2.7 Algorithm analysis

2.8 Recursive definitions

2.9 Recursive algorithms

2.10 Analyzing the time complexity of recursive algorithms

3. Sorting Algorithms

3.1 Sorting: Introduction

3.2 Selection sort

3.3 Java: Selection sort

3.4 Insertion sort

3.5 Java: Insertion sort

3.6 Shell sort

3.7 Java: Shell sort

3.8 Quicksort

3.9 Java: Quicksort

3.10 Merge sort

3.11 Java: Merge sort

3.12 Radix sort

3.13 Java: Radix sort

3.14 Overview of fast sorting algorithms

3.15 Java: Sorting with different operators

4. Lists, Stacks, and Queues

4.1 List abstract data type (ADT)

4.2 Singly-linked lists

4.3 Singly-linked lists: Insert

4.4 Singly-linked lists: Remove

4.5 Linked list search

4.6 Java: Singly-linked lists

4.7 Doubly-linked lists

4.8 Doubly-linked lists: Insert

4.9 Doubly-linked lists: Remove

4.10 Java: Doubly-linked lists

4.11 Linked list traversal

4.12 Sorting linked lists

4.13 Java: Sorting linked lists

4.14 Linked list dummy nodes

4.15 Linked lists: Recursion

4.16 Stack abstract data type (ADT)

4.17 Stacks using linked lists

4.18 Queue abstract data type (ADT)

4.19 Queues using linked lists

4.20 Java: Stacks and queues

4.21 Deque abstract data type (ADT)

4.22 Array-based lists

4.23 Java: Array-based list

5. Hash Tables

5.1 Hash tables

5.2 Chaining

5.3 Linear probing

5.4 Quadratic probing

5.5 Double hashing

5.6 Hash table resizing

5.7 Common hash functions

5.8 Direct hashing

5.9 Hashing Algorithms: Cryptography, Password Hashing

5.10 Java: Hash tables

6. Trees

6.1 Binary trees

6.2 Applications of trees

6.3 Binary search trees

6.4 BST search algorithm

6.5 BST insert algorithm

6.6 BST remove algorithm

6.7 BST inorder traversal

6.8 BST height and insertion order

6.9 BST parent node pointers

6.10 BST: Recursion

6.11 Tries

6.12 Java: Binary search tree

7. Balanced Trees

7.1 AVL: A balanced tree

7.2 AVL rotations

7.3 AVL insertions

7.4 AVL removals

7.5 Java: AVL Trees

7.6 Red-black tree: A balanced tree

7.7 Red-black tree: Rotations

7.8 Red-black tree: Insertion

7.9 Red-black tree: Removal

7.10 Java: Red-black trees

8. Heads and Treaps

8.1 Heaps

8.2 Heaps using arrays

8.3 Java: Heaps

8.4 Heap sort

8.5 Java: Heap sort

8.6 Priority queue abstract data type (ADT)

8.7 Treaps

9. Sets

9.1 Set abstract data type

9.2 Set operations

9.3 Static and dynamic set operations

9.4 Java: Set implementation

10. Graphs

10.1 Graphs: Introduction

10.2 Applications of graphs

10.3 Graph representations: Adjacency lists

10.4 Graph representations: Adjacency matrices

10.5 Graphs: Breadth-first search

10.6 Graphs: Depth-first search

10.7 Directed graphs

10.8 Weighted graphs

10.9 Java: Graphs

10.10 Java: Breadth-first search

10.11 Java: Depth-first search

10.12 Algorithm: Dijkstra’s shortest path

10.13 Java: Dijkstra’s shortest path

10.14 Algorithm: Bellman-Ford’s shortest path

10.15 Java: Bellman-Ford’s shortest path

10.16 Topological sort

10.17 Java: Topological sort

10.18 Minimum spanning tree

10.19 Java: Minimum spanning tree

10.20 All pairs shortest path

10.21 Java: All pairs shortest path

11. Algorithms

11.1 Huffman compression

11.2 Heuristics

11.3 Java: Heuristics

11.4 Greedy algorithms

11.5 Java: Greedy algorithms

11.6 Dynamic programming

11.7 Java: Dynamic programming

12. B-trees

12.1 B-trees

12.2 2-3-4 tree search algorithm

12.3 2-3-4 tree insert algorithm

12.4 2-3-4 tree rotations and fusion

12.5 2-3-4 tree removal

12.6 Java: 2-3-4 trees

13. Additional Material

13.1 Bubble sort

13.2 Quickselect

13.3 Java: Quickselect

13.4 Bucket sort

13.5 List data structure

13.6 Circular lists

14. Turing Machines (Optional)

14.1 Turing machines introduction

14.2 Turing machine components

14.3 Complexity classes

14.4 Java: Turing machine example

## What You’ll Find In This zyBook:

### More action with less text.

- Features Java-specific code examples throughout, grounded in essential data structures and algorithms
- Animations and tools are an excellent match for teaching data structures
- Over 40 challenge activities are included to provide extra practice for students. Each is auto-graded and features randomly-generated content.
- Test banks are also included for every section.

## The zyBooks Approach

### Less text doesn’t mean less learning.

Studying data structures and algorithms often represents a person’s first study of the “science” of computing, beyond just programming. Mastery of these concepts is part of the foundation of the discipline of computing, leading to computing professionals as distinct from programmers.

Data structures is an extremely visual subject, forming an excellent match for the extensive use of animations that typifies a zyBook. Embedded learning questions help the reader understand and remember concepts.

The content is maximally modular to enable configuration by instructors. Instructors can rearrange sections, set sections as optional, add instructor’s notes to sections, and more.

## Authors

**Roman Lysecky**

*Professor of Electrical and Computer Engineering, **Univ. of Arizona*

**Frank Vahid**

*Professor of Computer Science and Engineering, **Univ. of California, Riverside*

**Evan Olds**

*Content Developer, **zyBooks*