Data Structures and Algorithms in Swift (Kevin Lau, Vincent Ngo) (Z-Library)

Data Structures & Algorithms in Swift By Kelvin Lau & Vincent Ngo Download from finelybook 7450911@qq.com 2

Data Structures & Algorithms in Swift Kelvin Lau & Vincent Ngo Copyright ©2018 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. Download from finelybook 7450911@qq.com 3

About the authors Kelvin Lau is an author of this book. Kelvin is a physicist turned Swift iOS Developer. While he's currently entrenched with iOS development, he often reminisces of his aspirations to be part of the efforts in space exploration. Outside of programming work, he's an aspiring entrepreneur and musician. You can find him on Twitter: @kelvinlauKL Vincent Ngo is an author of this book. A software developer by day, and an iOS-Swift enthusiast by night, he believes that sharing knowledge is the best way to learn and grow as a developer. Vincent starts every morning with a homemade green smoothie in hand to fuel his day. When he is not in front of a computer, Vincent is training to play in small golf tournaments, doing headstands at various locations while on a hiking adventure, or looking up how to make tamago egg. You can find him on Twitter: @vincentngo2. Download from finelybook 7450911@qq.com 4

About the editors Steven Van Impe is the technical editor of this book. Steven is a computer science lecturer at the University College of Ghent, Belgium. When he’s not teaching, Steven can be found on his bike, rattling over cobblestones and sweating up hills, or relaxing around the table, enjoying board games with friends. You can find Steven on Twitter as @svanimpe. Chris Belanger is the editor of this book. Chris is the Editor in Chief at raywenderlich.com. He was a developer for nearly 20 years in various fields from e-health to aerial surveillance to industrial controls. If there are words to wrangle or a paragraph to ponder, he’s on the case. When he kicks back, you can usually find Chris with guitar in hand, looking for the nearest beach. Twitter: @crispytwit. Download from finelybook 7450911@qq.com 5

Ray Fix is the final pass editor of this book. A passionate Swift educator, enthusiast and advocate, he is actively using Swift to create Revolve: a next generation iPad controlled research microscope at Discover Echo Inc. Ray is mostly-fluent in spoken and written Japanese and stays healthy by walking, jogging, and playing ultimate Frisbee. When he is not doing one of those things, he is writing and dreaming of code in Swift. You can find him on Twitter: @rayfix. Download from finelybook 7450911@qq.com 6

We’d also like to acknowledge the efforts of the following contributors to the Swift Algorithm Club GitHub repo, upon whose work portions of this book are based: 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 Download from finelybook 7450911@qq.com 7

Book license By purchasing Data Structures & Algorithms in Swift, you have the following license: You are allowed to use and/or modify the source code in Data Structures & Algorithms in Swift 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 Swift 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 Swift, available at www.raywenderlich.com”. The source code included in Data Structures & Algorithms in Swift is for your personal use only. You are NOT allowed to distribute or sell the source code in Data Structures & Algorithms in Swift 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 Download from finelybook 7450911@qq.com 8

All trademarks and registered trademarks appearing in this guide are the properties of their respective owners. Download from finelybook 7450911@qq.com 9

Early access edition You’re reading an an early access edition of Data Structures & Algorithms in Swift. This edition contains a sample of the chapters that will be contained in the final release. We hope you enjoy the preview of this book, and that you’ll come back to help us celebrate the full launch of Data Structures & Algorithms in Swift later in 2018! The best way to get update notifications is to sign up for our monthly newsletter. This includes a list of the tutorials that came out on raywenderlich.com that month, any important news like book updates or new books, and a list of our favorite development links for that month. You can sign up here: www.raywenderlich.com/newsletter Download from finelybook 7450911@qq.com 10

Who this book is for This book is for developers who are comfortable with Swift 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 Swift language, we recommend our book, the Swift Apprentice, which goes into depth on the Swift language itself: https://store.raywenderlich.com/products/swift-apprentice If you want to learn more about iOS app development in Swift, we recommend working through our classic book, the iOS Apprentice: https://store.raywenderlich.com/products/ios-apprentice Download from finelybook 7450911@qq.com 11

What you need To follow along with this book, you'll need the following: A Mac running macOS Sierra 10.12.6, at a minimum, with the latest point release and security patches installed. This is so you can install the latest version of the required development tool: Xcode. Xcode 9 or later. Xcode is the main development tool for writing code in Swift. You need Xcode 9 at a minimum, since that version includes Swift 4. You can download the latest version of Xcode for free from the Mac App Store, here: apple.co/1FLn51R. If you haven't installed the latest version of Xcode, be sure to do that before continuing with the book. The code covered in this book depends on Swift 4 and Xcode 9 — you may get lost if you try to work with an older version. Download from finelybook 7450911@qq.com 12

Book source code and forums You can get the source code for the book here: www.raywenderlich.com/store/data-structures-algorithms- swift/source-code There, you’ll find all the code from the chapters for your use. 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. Download from finelybook 7450911@qq.com 13

About the cover The legendary, elusive kraken has captured the imagination of sailors, artists and authors for hundreds of years. Most modern-day scientists believe that the creature known as the kraken is most likely the giant squid: a deep-water member of the Architeuthidae family that can grow up to 43 feet in length! Little is known about the giant squid, due to its preference for cold, deep-water habitats. It’s much like the data structures and algorithms that lurk deep within software; although you may not yet understand how data structures and algorithms form the basis of scalable, high- performance solutions, this book will be your own personal Nautilus that will transport you 20,000 leagues under a sea of code! Download from finelybook 7450911@qq.com 14

Preface The study of data structures is one about efficiency. Given a particular amount of data, what is the best way to store it to achieve a particular goal? As a programmer, you regularly use a variety of collection types, such as arrays, dictionaries, and sets. These are data structures that hold a collection of data, each structure having its own performance characteristics. As an example, consider the difference between an array and a set. Both are meant to hold a collection of elements, but trying to find a particular element in an array takes a lot longer than finding an element in a set. On the other hand, you can order the elements an array, but you can’t order the elements of a set. Data structures are a well-studied area, and the concepts are language agnostic; a data structure from C is functionally and conceptually identical to the same data structure in any other language, such as Swift. At the same time, the high-level expressiveness of Swift make it an ideal choice for learning these core concepts without sacrificing too much performance. So why should you learn data structures and algorithms? Interviews When you interview for a software engineering position, chances are you’ll be tested on data structures and algorithms. Having a strong foundation in data structures and algorithms is the “bar” for many companies with software engineering positions. Work Data structures are most relevant when working with large amounts Download from finelybook 7450911@qq.com 15

Data structures are most relevant when working with large amounts of data. If you’re dealing with a non-trivial amount of data, using the appropriate data structure will play a big role in the performance and scalability of your software. Self-improvement Knowing about the strategies used by algorithms to solve tricky problems gives you ideas for improvements you can make to your own code. Swift’s Standard Library has small set of general purpose collection types; they definitely don’t cover every case. And yet, as you will see, these primitives can be used as a great starting point for building more complex and special purpose constructs. Knowing more data structures than just the standard array and dictionary gives you a bigger collection of tools you can use to build your own apps. Download from finelybook 7450911@qq.com 16

Swift Standard Library Before you dive into the rest of this book, you’ll first look at a few data structures that are baked into the Swift language. The Swift standard library refers to the framework that defines the core components of the Swift language. Inside, you’ll find a variety of tools and types to help build your Swift apps. In this chapter you’ll focus on two data structures that the standard library provides right out of the box: Array and Dictionary. Arrays An array is a general-purpose, generic container for storing a collection of elements, and is used commonly in all sorts of Swift programs. You can create an array by using an array literal, which is a comma-separated list of values surrounded with square brackets. For example: // An array of `String` elements let people = ["Brian", "Stanley", "Ringo"] This is a generic type in that it abstracts across any element type. The element type has no formal requirements; it can be anything. In the above example, the compiler type infers the elements to be String types. Swift defines arrays using protocols. Each of these protocols layers more capability on the array. For example, an Array is a Sequence which means that you can iterate through it at least once. It is also a Collection which means it can be traversed multiple times, non- destructively, and it can be accessed using a subscript operator. Array is also a RandomAccessCollection which makes guarantees about efficiency. Download from finelybook 7450911@qq.com 17

For example, the count property is guaranteed to be a "cheap" constant-time operation written O(1). This means that no matter how big your array gets, computing count will always take the same amount of time. Arrays are also useful for ordering the elements. Order Elements in an array are explicitly ordered. Using the above people array as an example, "Brian" comes before "Stanley". All elements in an array have a corresponding zero-based, integer index. For example, the people array from the above example has three indices, one corresponding to each element. You can retrieve the value of an element in the array by writing the following: people[0] // "Brian" people[1] // "Stanley" people[2] // "Ringo" Order is defined by the array data structure and should not be taken for granted. Some data structures, such as Dictionary, have a weaker concept of order. Random-access Random-access is a trait that data structures can claim if they can handle element retrieval in constant O(1) time. For example, getting "Ringo" from the people array takes constant time. Again, this performance should not be taken for granted. Other data structures such as linked lists and trees do not have constant time access. Array performance Download from finelybook 7450911@qq.com 18

Aside from being a random-access collection, there are other areas of performance that are of interest to you as a developer, particularly, how well or poorly does the data structure fare when the amount of data it contains needs to grow? For arrays, this varies on two factors. Insertion location The first factor is where you choose to insert the new element inside the array. The most efficient scenario for adding an element to an array is to append it at the end of the array: people.append("Charles") print(people) // prints ["Brian", "Stanley", "Ringo", "Charles"] Inserting "Charles" using the append method will place the string at the end of the array. This is a constant-time operation, and is the most efficient way to add elements into an array. However, there may come a time that you need to insert an element in a particular location, such as in the very middle of the array. In such a scenario, this is an O(n) operation. To help illustrate why that is the case, consider the following analogy. You’re standing in line for the theater. Someone new comes along, to join the lineup. What’s the easiest place to add people to the lineup? At the end of course! If the newcomer tried to insert themselves into the middle of the line, they would have to convince half the lineup to shuffle back to make room. And if they were terribly rude, they’d try to insert themselves at the head of the line. This is the worst-case scenario, because every single person in the lineup would need to shuffle back to make room for this new person in front! This is exactly how the array works. Inserting new elements from Download from finelybook 7450911@qq.com 19

This is exactly how the array works. Inserting new elements from anywhere aside from the end of the array will force elements to shuffle backwards to make room for the new element: people.insert("Andy", at: 0) // ["Andy", "Brian", "Stanley", "Ringo", "Charles"] To be precise, every element must shift backwards by one index, which takes n steps. Because of this it is considered a linear time or O(n) operation. If the number of elements in the array doubles, the time required for this insert operation will also double. If inserting elements in front of a collection is a common operation for your program, you may want to consider a different data structure to hold your data. The second factor that determines the speed of insertion is the array’s capacity. If the space that the array pre-allocated (the capacity) is exceeded it must reallocate storage and copy over the current elements. This means that any given insertion, even at the end, could take n steps to complete if a copy is made. However, the standard library employs a subtle trick to prevent appends from being O(n) time. Each time it runs out of storage and needs to copy, it doubles the capacity. Doing this allows arrays to have an amortized cost that it is still constant time O(1). Dictionary A dictionary is another generic collection that holds key-value pairs. For example, here’s a dictionary containing a user’s name and their score: var scores: [String: Int] = ["Eric": 9, "Mark": 12, "Wayne": Dictionaries don’t have any guarantees of order, nor can you insert at Download from finelybook 7450911@qq.com 20