Introduction
>>
Data Structures and Algorithms
Cliff Shaffer
Peter Ljunglöf
Nick Smallbone
2016–2024
1
Introduction
1.1
Selecting a Data Structure
1.2
Abstract Data Types
1.3
All ADTs Used in This Book
1.4
Information retrieval: Sets and Maps
1.5
Comparables, Comparators and Key-Value Pairs
1.6
Example: Comparables and Comparators in Java
2
Arrays: searching and sorting
2.1
Searching in an Array
2.2
Sorting
2.3
Sorting Terminology and Notation
2.4
Insertion Sort
2.5
Bubble Sort
2.6
Selection Sort
2.7
The Cost of Exchange Sorting
2.8
Optimizing Sort Algorithms with Code Tuning
2.9
Mergesort
2.10
Implementing Mergesort
2.11
Quicksort
2.12
An Empirical Comparison of Sorting Algorithms
2.13
Lower Bounds for Sorting
2.14
Arrays as Sets or Maps
3
Algorithm Analysis
3.1
Problems, Algorithms, and Programs
3.2
Comparing Algorithms
3.3
Best, Worst, and Average Cases
3.4
Faster Computer, or Faster Algorithm?
3.5
Asymptotic Analysis and Upper Bounds
3.6
Lower Bounds and
Θ
\Theta
Notation
3.7
Calculating Program Running Time
3.8
Analyzing Problems
3.9
Common Misunderstandings
3.10
Multiple Parameters
3.11
Space Bounds
3.12
Code Tuning and Empirical Analysis
3.13
Growth Rates Review
3.14
Summation Techniques
3.15
Solving Recurrence Relations
3.16
Amortized Analysis
4
Lists
4.1
The List ADT
4.2
Static Array-Based Lists
4.3
Dynamic Array-Based Lists
4.4
Linked Lists
4.5
Comparison of List Implementations
4.6
Implementing Maps using Lists
4.7
Doubly Linked Lists
4.8
Stacks
4.9
Implementing Recursion
4.10
Queues
4.11
Practice questions: lists, stacks and queues
5
Binary Trees
5.1
Definitions and Properties
5.2
Binary Tree as a Recursive Data Structure
5.3
Binary Tree Node Implementations
5.4
The Full Binary Tree Theorem
5.5
Binary Tree Traversals
5.6
Implementing Tree Traversals
5.7
Information Flow in Recursive Functions
5.8
Binary Tree Space Requirements
5.9
A Hard Information Flow Problem
5.10
General Trees
5.11
The Union/Find Algorithm
5.12
Sequential Tree Representations
6
Binary Search Trees
6.1
Binary Search Tree Definition
6.2
Binary Tree Guided Information Flow
6.3
Balanced Trees
6.4
The AVL Tree
6.5
The Red-Black Tree
6.6
The Splay Tree
6.7
Skip Lists
7
Priority queues
7.1
Array Representation for Complete Binary Trees
7.2
Heaps and Priority Queues
7.3
Heapsort
7.4
Huffman Coding Trees
8
Hashing
8.1
Hash Function Principles
8.2
Sample Hash Functions
8.3
Separate Chaining, or Open Hashing
8.4
Converting Objects to Table Indices
8.5
Bucket Hashing
8.6
Open Addressing
8.7
Improved Collision Resolution
8.8
Analysis of Open Addressing
8.9
Open Addressing, Deletion
8.10
Hash Tables in Real Life
9
Graphs
9.1
Graph Representations
9.2
Graph Implementations
9.3
Graph Traversals
9.4
Topological Sort
9.5
Shortest-Paths Problems
9.6
Minimal Cost Spanning Trees
9.7
All-Pairs Shortest Paths
9.8
Graph Concepts Summary
10
Glossary
11
Bibliography