Data Structures Algorithms in Dart (Jonathan Sande) (z-library.sk, 1lib.sk, z-lib.sk)

📄 File Format: PDF

💾 File Size: 27.0 MB

📖 Read Online ⬇️ Download

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

📄 Page 1

(This page has no text content)

📄 Page 2

Data Structures & Algorithms in Dart By Jonathan Sande Copyright ©2022 Razeware LLC. Notice of Rights All rights reserved. No part of this book or corresponding materials (such as text, images, or source code) may be reproduced or distributed by any means without prior written permission of the copyright owner. Notice of Liability This book and all corresponding materials (such as source code) are provided on an “as is” basis, without warranty of any kind, express of implied, including but not limited to the warranties of merchantability, fitness for a particular purpose, and noninfringement. In no event shall the authors or copyright holders be liable for any claim, damages or other liability, whether in action of contract, tort or otherwise, arising from, out of or in connection with the software or the use of other dealing in the software. Trademarks All trademarks and registered trademarks appearing in this book are the property of their own respective owners. Data Structures & Algorithms in Dart Data Structures & Algorithms in Dart raywenderlich.com 2

📄 Page 3

Table of Contents: Overview Book License 15............................................................................................. Before You Begin 16................................................................ What You Need 17........................................................................................ Book Source Code & Forums 18............................................................. Acknowledgments 21.................................................................................. Introduction 22.............................................................................................. Section I: Introduction 25...................................................... Chapter 1: Why Learn Data Structures & Algorithms? 26................................................................................... Chapter 2: Complexity 29.............................................................. Chapter 3: Basic Data Structures in Dart 40......................... Section II: Elementary Data Structures 47...................... Chapter 4: Stacks 48........................................................................ Chapter 5: Linked Lists 54............................................................. Chapter 6: Queues 73..................................................................... Section III: Trees 99................................................................. Chapter 7: Trees 101....................................................................... Chapter 8: Binary Trees 112......................................................... Chapter 9: Binary Search Trees 122.......................................... Chapter 10: AVL Trees 139........................................................... Chapter 11: Tries 154...................................................................... Data Structures & Algorithms in Dart raywenderlich.com 3

📄 Page 4

Chapter 12: Binary Search 166................................................... Chapter 13: Heaps 173................................................................... Chapter 14: Priority Queues 198............................................... Section IV: Sorting Algorithms 204.................................... Chapter 15: O(n²) Sorting Algorithms 206............................. Chapter 16: Merge Sort 219........................................................ Chapter 17: Radix Sort 227.......................................................... Chapter 18: Heapsort 244............................................................ Chapter 19: Quicksort 254........................................................... Section V: Graphs 274............................................................. Chapter 20: Graphs 275................................................................. Chapter 21: Breadth-First Search 300..................................... Chapter 22: Depth-First Search 311........................................ Chapter 23: Dijkstra’s Algorithm 326....................................... Conclusion 344.............................................................................................. Section VI: Challenge Solutions 346.................................. Chapter 4 Solutions 347................................................................ Chapter 5 Solutions 349................................................................ Chapter 6 Solutions 357................................................................ Chapter 7 Solutions 366................................................................ Chapter 8 Solutions 369................................................................ Chapter 9 Solutions 374................................................................ Chapter 10 Solutions 378.............................................................. Data Structures & Algorithms in Dart raywenderlich.com 4

📄 Page 5

Chapter 11 Solutions 382.............................................................. Chapter 12 Solutions 385.............................................................. Chapter 13 Solutions 389.............................................................. Chapter 14 Solutions 392.............................................................. Chapter 15 Solutions 399.............................................................. Chapter 16 Solutions 404.............................................................. Chapter 17 Solutions 408.............................................................. Chapter 18 Solutions 411.............................................................. Chapter 19 Solutions 414.............................................................. Chapter 20 Solutions 416.............................................................. Chapter 21 Solutions 418.............................................................. Chapter 22 Solutions 421.............................................................. Chapter 23 Solutions 424.............................................................. Data Structures & Algorithms in Dart raywenderlich.com 5

📄 Page 6

Table of Contents: Extended Book License 15. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Before You Begin 16. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . What You Need 17. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Book Source Code & Forums 18. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . About the Authors 20. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . About the Editors 20. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Acknowledgments 21. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Content Development 21. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Introduction 22. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . How to Read This Book 22. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Section I: Introduction 25. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 1: Why Learn Data Structures & Algorithms? 26. . . . . . The Goal of This Book 28. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 2: Complexity 29. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Time Complexity 30. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Space Complexity 38. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Other Notations 39. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key Points 39. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 3: Basic Data Structures in Dart 40. . . . . . . . . . . . . . . . . . . . List 40. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Map 44. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Set 45. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key Points 46. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Where to Go From Here? 46. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Section II: Elementary Data Structures 47. . . . . . . . . . . . Data Structures & Algorithms in Dart raywenderlich.com 6

📄 Page 7

Chapter 4: Stacks 48. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Stack Operations 49. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Implementation 49. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 53. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key Points 53. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 5: Linked Lists 54. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Node 55. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . LinkedList 57. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Adding Values to a List 58. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Removing Values From a List 62. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Making a List Iterable 67. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 71. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key Points 72. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 6: Queues 73. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Common Operations 74. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Example of a Queue 75. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . List-Based Implementation 76. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Doubly Linked List Implementation 80. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ring Buffer Implementation 84. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Double-Stack Implementation 89. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 96. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key Points 98. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Section III: Trees 99. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 7: Trees 101. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Terminology 102. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Implementation 104. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Traversal Algorithms 105. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 110. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key Points 111. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Data Structures & Algorithms in Dart raywenderlich.com 7

📄 Page 8

Chapter 8: Binary Trees 112. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Implementation 113. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Traversal Algorithms 115. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 120. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key Points 121. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 9: Binary Search Trees 122. . . . . . . . . . . . . . . . . . . . . . . . . . . . List vs. BST 123. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Implementation 127. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 138. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key Points 138. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 10: AVL Trees 139. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Understanding Balance 140. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Implementation 141. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 152. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key Points 153. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Where to Go From Here? 153. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 11: Tries 154. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . List vs. Trie 155. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Implementation 157. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 165. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key Points 165. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 12: Binary Search 166. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Linear Search vs. Binary Search 167. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Implementation 168. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 171. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key Points 172. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 13: Heaps 173. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . What’s a Heap? 173. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . The Heap Property 174. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . The Shape Property 175. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Data Structures & Algorithms in Dart raywenderlich.com 8

📄 Page 9

Heap Applications 175. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Fitting a Binary Tree Into a List 176. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Implementation 178. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 196. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key Points 197. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 14: Priority Queues 198. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Applications 199. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Common Operations 199. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Implementation 200. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 203. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key Points 203. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Section IV: Sorting Algorithms 204. . . . . . . . . . . . . . . . . . . . Chapter 15: O(n²) Sorting Algorithms 206. . . . . . . . . . . . . . . . . . . . . . Bubble Sort 207. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Selection Sort 211. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Insertion Sort 213. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Stability 216. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 217. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key Points 218. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 16: Merge Sort 219. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Example 220. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Implementation 221. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Performance 225. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 226. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key Points 226. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 17: Radix Sort 227. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sorting by Least Significant Digit 228. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sorting by Most Significant Digit 234. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 242. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Data Structures & Algorithms in Dart raywenderlich.com 9

📄 Page 10

Key Points 243. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 18: Heapsort 244. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Example 245. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Implementation 248. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Performance 252. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 253. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key Points 253. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 19: Quicksort 254. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Example 255. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Naïve Implementation 256. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Partitioning Strategies 258. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 273. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key Points 273. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Where to Go From Here? 273. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Section V: Graphs 274. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 20: Graphs 275. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Types of Graphs 276. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Common Operations 278. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Adjacency List 282. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Adjacency Matrix 290. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Graph Analysis 297. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 299. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key Points 299. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 21: Breadth-First Search 300. . . . . . . . . . . . . . . . . . . . . . . . . . How Breadth-First Search Works 301. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Implementation 305. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Performance 308. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 309. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key Points 310. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Data Structures & Algorithms in Dart raywenderlich.com 10

📄 Page 11

Chapter 22: Depth-First Search 311. . . . . . . . . . . . . . . . . . . . . . . . . . . . How Depth-First Search Works 312. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Implementation 318. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Performance 321. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Cycles 321. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 325. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key Points 325. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 23: Dijkstra’s Algorithm 326. . . . . . . . . . . . . . . . . . . . . . . . . . . How Dijkstra’s Algorithm Works 327. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Implementation 335. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Performance 342. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 343. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key Points 343. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Conclusion 344. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Approaching a Difficult Problem 344. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Learning Tips 345. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Where to Go From Here? 345. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Section VI: Challenge Solutions 346. . . . . . . . . . . . . . . . . . . Chapter 4 Solutions 347. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 1 347. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 5 Solutions 349. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 1 349. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 2 350. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 3 351. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 4 354. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 6 Solutions 357. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 1 357. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 2 358. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 3 362. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Data Structures & Algorithms in Dart raywenderlich.com 11

📄 Page 12

Solution to Challenge 4 363. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 7 Solutions 366. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 1 366. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 2 368. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 8 Solutions 369. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 1 370. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 2 370. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 9 Solutions 374. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 1 374. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 2 376. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 3 377. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 10 Solutions 378. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 1 378. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 2 379. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 3 380. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 11 Solutions 382. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 1 382. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 2 383. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 12 Solutions 385. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 1 385. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 2 386. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 3 386. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 13 Solutions 389. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 1 389. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 2 390. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 3 390. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 4 391. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 14 Solutions 392. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 1 392. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Data Structures & Algorithms in Dart raywenderlich.com 12

📄 Page 13

Solution to Challenge 2 394. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 15 Solutions 399. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 1 399. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 2 400. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 3 401. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 4 401. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 16 Solutions 404. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 1 404. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 2 405. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 17 Solutions 408. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 1 408. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 2 409. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 3 410. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 18 Solutions 411. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 1 411. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 2 412. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 19 Solutions 414. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 1 414. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 2 415. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 20 Solutions 416. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 1 416. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 21 Solutions 418. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 1 418. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 2 418. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 3 420. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 22 Solutions 421. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 1 421. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 2 421. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Data Structures & Algorithms in Dart raywenderlich.com 13

📄 Page 14

Chapter 23 Solutions 424. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 1 424. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Solution to Challenge 2 425. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Data Structures & Algorithms in Dart raywenderlich.com 14

📄 Page 15

LBook License By purchasing Data Structures & Algorithms in Dart, you have the following license: • You are allowed to use and/or modify the source code in Data Structures & Algorithms in Dart in as many apps as you want, with no attribution required. • You are allowed to use and/or modify all art, images and designs that are included in Data Structures & Algorithms in Dart in as many apps as you want, but must include this attribution line somewhere inside your app: “Artwork/images/designs: from Data Structures & Algorithms in Dart, available at www.raywenderlich.com”. • The source code included in Data Structures & Algorithms in Dart is for your personal use only. You are NOT allowed to distribute or sell the source code in Data Structures & Algorithms in Dart without prior authorization. • This book is for your personal use only. You are NOT allowed to sell this book without prior authorization, or distribute it to friends, coworkers or students; they would need to purchase their own copies. All materials provided with this book are provided on an “as is” basis, without warranty of any kind, express or implied, including but not limited to the warranties of merchantability, fitness for a particular purpose and noninfringement. In no event shall the authors or copyright holders be liable for any claim, damages or other liability, whether in an action of contract, tort or otherwise, arising from, out of or in connection with the software or the use or other dealings in the software. All trademarks and registered trademarks appearing in this guide are the properties of their respective owners. raywenderlich.com 15

📄 Page 16

Before You Begin This section tells you a few things you need to know before you get started, such as what you’ll need for hardware and software, where to find the project files for this book, and more. raywenderlich.com 16

📄 Page 17

iWhat You Need To follow along with this book, you’ll need the following: • Recommended: A computer with the Dart SDK and supporting IDE installed. The code in this book was all tested using Visual Studio Code, but IntelliJ IDEA is another good IDE. Read more at dart.dev. • Alternative: Any web browser that supports JavaScript. It’s also possible to run the code in this book online. Open a web browser and navigate to dartpad.dev. If you’re using a phone, you’ll have an easier time if you choose the desktop view in your browser page settings. If you haven’t installed the latest version of Dart, be sure to do that before continuing with the book. The code covered in this book depends on Dart 2.15 — you may get lost if you try to work with an older version. raywenderlich.com 17

📄 Page 18

iiBook Source Code & Forums Where to Download the Materials for This Book The materials for this book can be cloned or downloaded from the GitHub book materials repository: • https://github.com/raywenderlich/dsad-materials/tree/editions/1.0 Forums We’ve also set up an official forum for the book at https:// forums.raywenderlich.com/c/books/data-structures-and-algorithms-in-dart. This is a great place to ask questions about the book or to submit any errors you may find. raywenderlich.com 18

📄 Page 19

“Thank you to Dalai, OJ, Anand and Temuujin of Soyol-Erdem University for helping me think through many of the data structures and algorithms in this book. You came up with novel solutions and asked questions that I didn’t always know the answer to. This book is better because of your input.” — Jonathan Sande raywenderlich.com 19

📄 Page 20

About the Authors Jonathan Sande is an author of this book, converting Data Structures & Algorithms in Swift by Kelvin Lau and Vincent Ngo to the current Dart book you have here. Jonathan is a Flutter and Dart developer working mainly on text rendering and input for vertical Mongolian script. Online he goes by Suragch, a Mongolian word meaning “student”, a reminder to never stop learning. In his free time, he enjoys learning about microbiology and the many data structures and algorithms found in nature. You can find him on Twitter: @suragch1 (https://twitter.com/suragch1) About the Editors Pablo Mateo is the final pass editor for this book. He is Delivery Manager at one of the biggest banks in the world, and was also founder and CTO of a technology development company in Madrid. His expertise is focused on web and mobile app development, although he first started as a Creative Art Director. He has been for many years the Main Professor of the iOS and Android Mobile Development Masters Degree at a well-known technology school in Madrid (CICE). He has a masters degree in Artificial Intelligence & Machine-Learning and is currently learning Quantum Computing at MIT. Data Structures & Algorithms in Dart About the Team raywenderlich.com 20