Data Structures and Algorithms in Swift (eBook)

Table of Contents 4
About the Author 11
About the Technical Reviewer 12
Chapter 1: Arrays 13
Introduction 13
Main Features of Arrays 14
Retrieving Elements from an Array 16
Adding Elements to an Array 17
Removing Elements from an Array 18
Built-in Functions and Properties 18
isEmpty 18
First and Last 19
Reversed and Reverse 19
Count 19
Important 20
Conclusion 20
Chapter 2: Dictionaries 21
Introduction 21
Accessing Values in a Dictionary 23
Adding/Modifying to a Dictionary 25
Removing a Value from a Dictionary 26
Built-in Functions and Properties 26
isEmpty 26
First 26
Count 27
Keys 27
Conclusion 27
Chapter 3: Sets 28
Accessing, Adding, and Removing an Element of a Set 28
Accessing an Element 28
Adding an Element 30
Removing Elements 30
Set Operations 31
Comparison Operations 31
Union 31
Intersection 32
Subtracting 33
Symmetric Difference 34
Membership and Equality Operations 35
Set Equality 35
Set Membership 35
Conclusion 37
Chapter 4: Stacks 38
Using Swift with Stacks 39
Stack Structures 42
Stack Extensions 43
Conclusion 43
Chapter 5: Queue 44
Implementation 46
Conclusion 51
Chapter 6: Linked Lists 52
Implementation 53
Node 54
Singly Linked List 54
Adding New Values to a Linked List 55
Append 56
Insert 57
Removing New Values from a Linked List 58
removeLast 59
remove(at:) 60
Doubly Linked List 61
Append 63
Remove Node Method 64
Remove(at:) 64
Summary 65
Chapter 7: Hash Table 66
Creating Hash Table 67
Retrieving Data from a Hash Table 68
Updating a Value in a Hash Table 69
Removing a Value from a Hash Table 70
Summary 71
Chapter 8: Trees 72
Creation 73
Insertion 74
Searching Data 75
Conclusion 77
Chapter 9: Trie Data Structure 78
Why a Trie? 78
How It Works 79
Implementation 80
Insert 81
Query 82
Remove 83
Conclusion 86
Chapter 10: Binary Tree 87
Binary Tree Primer 87
Properties of Binary Tree 88
Types of Binary Trees 88
Implementation 91
Tree Traversal (Also Known As Tree Search) 91
In-Order Traversal 92
Pre-Order Traversal 93
Post-Order Traversal 95
Conclusion 96
Chapter 11: Binary Search Tree 97
Implementation 98
Insert 99
Search 102
Example 104
Delete 104
Deleting a Leaf 104
Deleting a Node with One Child 105
Deleting a Node with Two Children 106
Conclusion 110
Chapter 12: Red–Black Tree 111
Implementation 112
Rotation 115
Insertion 119
Deletion 125
Conclusion 130
Chapter 13: Big O 131
Time Complexity 131
Space Complexity 134
Drop the Constants and Nondominant Terms 135
How to Calculate Complexities? 136
Add vs. Multiply 138
Amortized Time 139
Log N Runtimes 140
Recursive Runtimes 141
Conclusion 142
Chapter 14: Sorting Algorithms 143
Bubble Sort 143
Implementation 146
Selection Sort 147
Implementation 149
Insertion Sort 150
Implementation 152
Merge Sort 153
Implementation 156
Quick Sort 158
Implementation 161
Pivot Selection 162
Conclusion 163
Chapter 15: Search Algorithms 164
Linear Search 164
Implementation 166
Binary Search 167
Implementation 169
Conclusion 170
Chapter 16: Graph Algorithms 171
Directed Graphs 172
Undirected Graphs 172
Weighted Graphs 173
Breadth-First Search (BFS) 174
Implementation 179
Depth-First Search (DFS) 182
Implementation 187
Dijkstra’s Algorithm 190
Implementation 198
Algorithm 199
Conclusion 202
Chapter 17: Choosing the Best Algorithm 203
Sorting Algorithms 204
Bubble Sort 204
Selection Sort 204
Insertion Sort 205
Merge Sort 205
Quick Sort 205
Search Algorithms 206
Linear Search vs. Binary Search 206
Graph Search Algorithms (GSA) 208
Dijkstra’s Algorithm 209
Index 210