Data Structures Algorithms in Kotlin Implementing Practical Data Structures in Kotlin (raywenderlich Tutorial Team, Irina Galata etc.) (z-library.sk, 1lib.sk, z-lib.sk)

Data Structures & Algorithms in Kotlin Irina Galata & Matei Suica Copyright ©2019 Razeware LLC. No6ce 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. No6ce 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 Kotlin raywenderlich.com 2

About the Authors Irina Galata is an author of this book. She is a software engineer in Linz, Austria, working at Runtastic. She passionate about programming and exploring new technologies. You can follow her on twitter @igalata13. Matei Suica is an author of this book. He is a software developer that dreams about changing the world with his work. From his small office in Romania, Matei is trying to create an App that will help millions. When the laptop lid closes, he likes to go to the gym and read. You can find him on Twitter or LinkedIn: @mateisuica. About the Editors Bruno Lemgruber is the technical editor of this book. He is an iOS and Android developer who enjoys being challenged and working on projects that requires him to work outside his comfort and knowledge set, as he continues to learn new languages and development techniques. Nowadays, he works in a bank from Brazil (@SICOOB_oficial) in the iOS team. He loves to drink craft beer when he has a free time! You can follow him on twitter @brunoteixeiralc. Márton Braun is a technical editor of this book. He is a Kotlin enthusiast since the 1.0 of the language, and an aspiring writer, speaker, educator. He's working as an Android developer and teaches Kotlin and Android in university courses. Creator of the MaterialDrawerKt and Krate libraries. He occasionally gets addicted to StackOverflow, where he's one of the top contributors under the Kotlin tag. Data Structures & Algorithms in Kotlin raywenderlich.com 3

Tammy Coron is an editor of this book. Tammy is an independent creative professional and the host of Roundabout: Creative Chaos. She’s also a Development Editor at The Pragmatic Bookshelf, a Sr. Editor at Razeware, and a content contributor at Creative Bloq, Lynda.com, iMore, and raywenderlich.com. Massimo Carli is the final pass editor of this book. Massimo has been working with Java since 1995 when he co-founded the first Italian magazine about this technology http://www.mokabyte.it. After many years creating Java desktop and enterprise application, he started to work in the mobile world. In 2001 he wrote his first book about J2ME. After many J2ME and Blackberry applications, Massimo then started to work with Android in 2008. The same year he wrote the first Italian book about Android, a best seller on Amazon.it. That was the first of a series of 10 books about Android and Kotlin. Massimo worked at Yahoo and Facebook and he's actually Senior Mobile Engineer at Spotify. He's a musical theatre lover and a supporter of the soccer team S.P.A.L. Data Structures & Algorithms in Kotlin raywenderlich.com 4

About the Contributors We'd like to acknowledge the work of the authors of Data Structures & Algorithms in Swift, the content of which served as the basis for this book. • Vincent Ngo • Kelvin Lau We’d also like to acknowledge the efforts of the following contributors to the Swift Algorithm Club GitHub repo (https://github.com/raywenderlich/swift-algorithm- club), upon whose work portions of this book are based. • Matthijs Hollemans, the original creator of the Swift Algorithm Club. We’d also like to thank the following for their contributions to the repo: • Donald Pinckney, Graph https://github.com/donald-pinckney • Christian Encarnacion, Trie and Radix Sort https://github.com/Thukor • Kevin Randrup, Heap https://github.com/kevinrandrup • Paulo Tanaka, Depth First Search https://github.com/paulot • Nicolas Ameghino, BST https://github.com/nameghino • Mike Taghavi, AVL Tree • Chris Pilcher, Breadth First Search About the Ar6st Vicki Wenderlich is the designer and artist of the cover of this book. She is Ray’s wife and business partner. She is a digital artist who creates illustrations, game art and a lot of other art or design work for the tutorials and books on raywenderlich.com. When she’s not making art, she loves hiking, a good glass of wine and attempting to create the perfect cheese plate. Data Structures & Algorithms in Kotlin raywenderlich.com 5

Table of Contents: Overview Book License 14................................................................................... Who This Book Is For 15.................................................................... What You Need 16.............................................................................. Book Source Code & Forums 17...................................................... About the Cover 19............................................................................. Sec6on I: Introduc6on to Data Structures & Algorithms 20......................................................................... Chapter 1: Kotlin & Kotlin Standard Library 21.................. Chapter 2: Complexity 39....................................................... Sec6on II: Elementary Data Structures 52...................... Chapter 3: Linked List 53......................................................... Chapter 4: Stack Data Structures 85.................................... Chapter 5: Queues 94.............................................................. Sec6on III: Trees 125............................................................ Chapter 6: Trees 127................................................................ Chapter 7: Binary Trees 140................................................... Chapter 8: Binary Search Trees 152...................................... Chapter 9: AVL Trees 173........................................................ Chapter 10: Tries 191............................................................... Chapter 11: Binary Search 204.............................................. Chapter 12: The Heap Data Structure 213......................... Data Structures & Algorithms in Kotlin raywenderlich.com 6

Chapter 13: Priority Queues 238.......................................... Sec6on IV: Sor6ng Algorithms 251.................................. Chapter 14: O(n²) SorZng Algorithms 253.......................... Chapter 15: Merge Sort 268................................................... Chapter 16: Radix Sort 279.................................................... Chapter 17: Heap Sort 289..................................................... Chapter 18: Quicksort 298..................................................... Sec6on V: Graphs 316......................................................... Chapter 19: Graphs 318.......................................................... Chapter 20: Breadth-First Search 344................................. Chapter 21: Depth-First Search 355.................................... Chapter 22: Dijkstra’s Algorithm 368................................... Chapter 23: Prim’s Algorithm 387......................................... Conclusion 403..................................................................................... Data Structures & Algorithms in Kotlin raywenderlich.com 7

Table of Contents: Extended Book License 14. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Who This Book Is For 15. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . What You Need 16. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Book Source Code & Forums 17. . . . . . . . . . . . . . . . . . . . . . . . . . About the Cover 19. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sec6on I: Introduc6on to Data Structures & Algorithms 20. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 1: Kotlin & Kotlin Standard Library 21. . . . . . . . . . . . . . IntroducZon to Kotlin 22. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . The Kotlin Standard Library 30. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key points 38. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 2: Complexity 39. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Time complexity 40. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Other Zme complexiZes 47. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Comparing Zme complexity 47. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Space complexity 48. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key points 51. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sec6on II: Elementary Data Structures 52. . . . . . . . . . . Chapter 3: Linked List 53. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Node 54. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . LinkedList 55. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Adding values to the list 56. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Removing values from the list 61. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Kotlin collecZon interfaces 66. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Becoming a Kotlin mutable collecZon 67. . . . . . . . . . . . . . . . . . . . . . . . . . Data Structures & Algorithms in Kotlin raywenderlich.com 8

Challenges 76. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key points 84. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 4: Stack Data Structures 85. . . . . . . . . . . . . . . . . . . . . . . Stack operaZons 86. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ImplementaZon 87. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . push and pop operaZons 87. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 91. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key points 93. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 5: Queues 94. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Common operaZons 95. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Example of a queue 96. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . List-based implementaZon 97. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Doubly linked list implementaZon 100. . . . . . . . . . . . . . . . . . . . . . . . . . . . Ring buffer implementaZon 104. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Double-stack implementaZon 108. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 115. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key points 124. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sec6on III: Trees 125. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 6: Trees 127. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Terminology 128. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ImplementaZon 129. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Traversal algorithms 131. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 137. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key points 139. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 7: Binary Trees 140. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ImplementaZon 141. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Traversal algorithms 143. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 147. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key points 151. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Data Structures & Algorithms in Kotlin raywenderlich.com 9

Chapter 8: Binary Search Trees 152. . . . . . . . . . . . . . . . . . . . . . . . Case study: array vs. BST 153. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ImplementaZon 157. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 168. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key points 172. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 9: AVL Trees 173. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Understanding balance 174. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ImplementaZon 175. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 187. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key points 190. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 10: Tries 191. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Example 192. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ImplementaZon 194. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 202. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key points 203. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 11: Binary Search 204. . . . . . . . . . . . . . . . . . . . . . . . . . . . Example 205. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ImplementaZon 206. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 208. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key points 212. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 12: The Heap Data Structure 213. . . . . . . . . . . . . . . . . . What is a heap? 214. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . The heap property 214. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Heap applicaZons 215. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Common heap operaZons 216. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . SorZng and comparing 216. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . How do you represent a heap? 218. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . InserZng into a heap 220. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Removing from a heap 223. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Removing from an arbitrary index 227. . . . . . . . . . . . . . . . . . . . . . . . . . . . Data Structures & Algorithms in Kotlin raywenderlich.com 10

Searching for an element in a heap 228. . . . . . . . . . . . . . . . . . . . . . . . . . . Heapify an array 229. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . TesZng 231. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 233. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key points 237. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 13: Priority Queues 238. . . . . . . . . . . . . . . . . . . . . . . . . . ApplicaZons 239. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Common operaZons 239. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ImplementaZon 240. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 245. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key points 250. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sec6on IV: Sor6ng Algorithms 251. . . . . . . . . . . . . . . . . Chapter 14: O(n²) SorZng Algorithms 253. . . . . . . . . . . . . . . . . . Bubble sort 254. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . SelecZon sort 257. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . InserZon sort 260. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . GeneralizaZon 262. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 264. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key points 267. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 15: Merge Sort 268. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ImplementaZon 270. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Performance 274. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 275. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key points 278. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 16: Radix Sort 279. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Example 280. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ImplementaZon 281. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 284. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key points 288. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Data Structures & Algorithms in Kotlin raywenderlich.com 11

Chapter 17: Heap Sort 289. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Gehng started 290. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Example 290. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ImplementaZon 293. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Performance 295. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 296. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key points 297. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 18: Quicksort 298. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Example 299. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ParZZoning strategies 300. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Effects of a bad pivot choice 307. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 313. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key points 315. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Sec6on V: Graphs 316. . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 19: Graphs 318. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Weighted graphs 319. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Common operaZons 321. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Defining a vertex 323. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Defining an edge 323. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Adjacency list 324. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ImplementaZon 325. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Adjacency matrix 331. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ImplementaZon 332. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Graph analysis 338. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 340. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key points 343. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 20: Breadth-First Search 344. . . . . . . . . . . . . . . . . . . . . Example 345. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ImplementaZon 348. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Performance 349. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Data Structures & Algorithms in Kotlin raywenderlich.com 12

Challenges 350. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key points 354. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 21: Depth-First Search 355. . . . . . . . . . . . . . . . . . . . . . . DFS example 356. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ImplementaZon 360. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Performance 362. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 363. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key points 367. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 22: Dijkstra’s Algorithm 368. . . . . . . . . . . . . . . . . . . . . . Example 369. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ImplementaZon 377. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Trying out your code 382. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Performance 383. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 384. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key points 386. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Chapter 23: Prim’s Algorithm 387. . . . . . . . . . . . . . . . . . . . . . . . . Example 389. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ImplementaZon 393. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . TesZng your code 397. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Performance 398. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Challenges 399. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Key points 402. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Conclusion 403. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Data Structures & Algorithms in Kotlin raywenderlich.com 13

LBook License By purchasing Data Structures & Algorithms in Kotlin, you have the following license: • You are allowed to use and/or modify the source code in Data Structures & Algorithms in Kotlin 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 Kotlin 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 Kotlin, available at www.raywenderlich.com”. • The source code included in Data Structures & Algorithms in Kotlin is for your personal use only. You are NOT allowed to distribute or sell the source code in Data Structures & Algorithms in Kotlin 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 14

WWho This Book Is For This book is for developers who are comfortable with Kotlin and want to ace whiteboard interviews, improve the performance of their code, and ensure their apps will perform well at scale. If you’re looking for more background on the Kotlin language, we recommend our book, Kotlin Apprentice, which goes into depth on the Kotlin language itself: • https://store.raywenderlich.com/products/kotlin-apprentice If you want to learn more about Android app development in Kotlin, we recommend working through our classic book, Kotlin Apprentice: • https://store.raywenderlich.com/products/kotlin-apprentice raywenderlich.com 15

WWhat You Need To follow along with this book, you need: • IntelliJ IDEA Community Edition 2019.1.x: Available at https:// www.jetbrains.com/idea/. This is the environment in which you’ll develop most of the sample code in this book. • Kotlin playground: You can also use the Kotlin Playground available at the Kotlin home page at https://play.kotlinlang.org. raywenderlich.com 16

BBook Source Code & Forums If you bought the digital edi6on The digital edition of this book comes with the source code for the starter and completed projects for each chapter. These resources are included with the digital edition you downloaded from store.raywenderlich.com. If you bought the print version You can get the source code for the print edition of the book here: www.raywenderlich.com/store/data-structures-and-algorithms-in-kotlin-source- code/ Forums We’ve also set up an official forum for the book at forums.raywenderlich.com. This is a great place to ask questions about the book or to submit any errors you may find. Digital book edi6ons We have a digital edition of this book available in both ePUB and PDF, which can be handy if you want a soft copy to take with you, or you want to quickly search for a specific term within the book. Buying the digital edition version of the book also has a few extra benefits: free updates each time we update the book, access to older versions of the book, and you can download the digital editions from anywhere, at anytime. raywenderlich.com 17

Visit our Data Structures & Algorithms in Kotlin store page here: • https://store.raywenderlich.com/products/data-structures-and-algorithms-in- kotlin. And if you purchased the print version of this book, you’re eligible to upgrade to the digital editions at a significant discount! Simply email support@razeware.com with your receipt for the physical copy and we’ll get you set up with the discounted digital edition version of the book. Data Structures & Algorithms in Kotlin Book Source Code & Forums raywenderlich.com 18

AAbout the Cover Weaver birds are known for their intricate and sophisticated spherical nests, widely considered some of the most elegant animal-built structures in the world. Not only are these complex nests 100% waterproof, humans have never figured out how to reproduce these structures on their own. Weaver birds rely on their elegant weaving techniques to build robust structures, just as you rely on elegant data structures and algorithms to create robust code. After reading Data Structures & Algorithms in Kotlin, you’ll be able to weave structures and algorithms into your code to make your apps more performant and robust. Waterproof? Well, that’s a different story! raywenderlich.com 19

Sec6on I: Introduc6on to Data Structures & Algorithms The chapters in this short but important section explain what’s built into the Kotlin Standard Library and how you use it in building your apps. You’ll learn why one algorithm may be better suited than another. You’ll also learn what the Big-O notation is and how you can continue to answer the question: “Can we do better?” Specifically, you’ll learn: • Chapter 1: Kotlin & Kotlin Standard Library: The Kotlin Standard Library refers to the framework that defines the core elements of the Kotlin language. Inside the Kotlin Standard Library, you’ll find a variety of tools and data types to help build your Kotlin apps, including data structures. • Chapter 2: Complexity: Answering the question, “Does it scale?” is all about understanding the complexity of an algorithm. The Big-O notation is the primary tool that you’ll use to think about algorithmic performance in the abstract and independent hardware or language. This chapter will prepare you to think in these terms. These fundamentals will set you on your way; before you know it, you’ll be ready for the more advanced topics that follow. raywenderlich.com 20