iOS & Swift

Data Structures & Algorithms in Swift

The most popular and comprehensive book on Swift algorithms & data structures! Covers search, sort, trees, stacks, and more. By Vincent Ngo & Kelvin Lau.

Read for Free with the Personal Plan* * Includes this and all other books in our online library See all benefits
Buy Individually $59.99* *Includes access to all of our online reading features.
Leave a rating/review
Download materials
Buy paperback—Amazon Comments
Save for later
Share

Who is this 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.

Covered concepts

  • Basic data structures and algorithms
  • Protocols for generalizing algorithms
  • Building your own data structures using the Swift standard library
  • Trees, tries and graphs
  • Building algorithms on top of other primitives
  • Sorting algorithms
  • Algorithmic complexity
  • Finding shortest paths, traversals, and subgraphs

Understanding how data structures and algorithms work in code is crucial for creating efficient and scalable apps and acing job interviews. Swift’s standard library and, more recently, the Swift Collections and Algorithms packages contain a robust set of general-purpose collection types and algorithms, yet they don’t cover every case!

In...

more

Before You Begin

This section tells you a few things you need to know before starting, such as what you’ll need for hardware and software, where to find the project files for this book and more.

Section I: Introduction

The chapters in this short but essential section will motivate the study of data structures and algorithms and give you a quick rundown of the Swift standard library, whose facilities you can use as a basis for creating your own data structures and algorithms.

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.
2
Toggle description
Answering the question, "Does it scale?" is all about understanding the complexity of an algorithm. Big-O notation is the primary tool you use to think about algorithmic performance in the abstract, independent of hardware or language. This chapter will prepare you to think in these terms.
3
Toggle description
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.

Section II: Elementary Data Structures

This section looks at a few important data structures that are not found in the Swift standard library but form the basis of more advanced algorithms covered in future sections. All of them are collections optimized for (and enforce) a particular access pattern. You will also get a glimpse of how protocols in Swift can be used to build up these useful primitives.

Each concept chapter is followed by a Challenge chapter where you will be asked to answer something about the data structure, write a utility function, or use it directly to solve a common problem. Worked solutions to the Challenge chapters are located at the end of the book. We encourage you not to peek at our solution until you have given the challenge a shot yourself.

4
Toggle description
The stack data structure is similar in concept to a physical stack of objects. When you add an item to a stack, you place it on top of the stack. When you remove an item from a stack, you always remove the top-most item. Stacks are useful and also exceedingly simple. The main goal of building a stack is to enforce how you access your data.
5
Toggle description
Practice your new-found Stack knowledge with these challenges.
6
Toggle description
A linked list is a collection of values arranged in a linear, unidirectional sequence. A linked list has some theoretical advantages over contiguous storage options such as the Swift Array, including constant time insertion and removal from the front of the list and other reliable performance characteristics.
7
Toggle description
Challenge exercises for linked lists.
Toggle description
Lines are everywhere, whether you are lining up to buy tickets to your favorite movie or waiting for a printer machine to print out your documents. These real-life scenarios mimic the queue data structure. Queues use first-in-first-out ordering, meaning the first enqueued element will be the first to get dequeued. Queues are handy when you need to maintain the order of your elements to process later.
Toggle description
Challenge exercises for queues.

Section III: Trees

Trees are another way to organize information, introducing the concept of children and parents. You‘ll take a look at the most common tree types and see how they readily solve specific computational problems. Just like the last section, this section will introduce you to a concept with a chapter, followed by a Challenge chapter to help you hone the skills you are learning.

Trees are a handy way to organize information when performance is critical. Adding them as a tool to your toolbelt will undoubtedly prove to be useful throughout your career.

Toggle description
The tree is a data structure of profound importance. It is used to tackle many recurring challenges in software development, such as representing hierarchical relationships, managing sorted data, and facilitating fast lookup operations. There are many types of trees, and they come in various shapes and sizes.
Toggle description
Challenge exercises for trees.
Toggle description
In the previous chapter, you looked at a basic tree where each node can have many children. A binary tree is a tree where each node has at most two children, often referred to as the left and right children. Binary trees serve as the basis for many tree structures and algorithms. In this chapter, you’ll build a binary tree and learn about the three most important tree traversal algorithms.
Toggle description
Challenge exercises for binary trees.
Toggle description
A binary search tree facilitates fast lookup, addition, and removal operations. Each operation has an average time complexity of O(log n), which is considerably faster than linear data structures such as arrays and linked lists.
Toggle description
Challenge exercises for binary trees.
Toggle description
In the previous chapter, you learned about the O(log n) performance characteristics of the binary search tree. However, you also learned that unbalanced trees can deteriorate the performance of the tree, all the way down to O(n). In 1962, Georgy Adelson-Velsky and Evgenii Landis came up with the first self-balancing binary search tree: the AVL Tree.
Toggle description
Challenge exercises for AVL trees.
Toggle description
The trie (pronounced as “try”) is a tree that specializes in storing data that can be represented as a collection, such as English words. The benefits of a trie are best illustrated by looking at it in the context of prefix matching, which you’ll do in this chapter.
Toggle description
Challenge exercises for tries.
Toggle description
Binary search is one of the most efficient searching algorithms with the time complexity of O(log n). This is comparable with searching for an element inside a balanced binary search tree. To perform a binary search, the collection must perform index manipulation in constant time and be sorted.
Toggle description
Challenge exercises for binary search.
Toggle description
A heap is a complete binary tree, also known as a binary heap, that can be constructed using an array. Heaps come in two flavors: Max heaps and Min heaps. Have you seen the movie Toy Story, with the claw machine and the squeaky little green aliens? Imagine that the claw machine is operating on your heap structure and will always pick the minimum or maximum value, depending on the flavor of heap.
Toggle description
Challenge exercises for heaps.
Toggle description
Queues are simply lists that maintain the order of elements using first-in-first-out (FIFO) ordering. A priority queue is another version of a queue that dequeues elements in priority order instead of using FIFO ordering. A priority queue is especially useful when identifying the maximum or minimum value given a list of elements.
Toggle description
Challenge exercises for priority queues.

Section IV: Sorting Algorithms

Putting lists in order is a classical computational problem. Sorting has been studied since the days of vacuum tubes and perhaps even before that. Although you may never need to write your own sorting algorithm using the highly optimized standard library, studying sorting has many benefits. You’ll learn, for example, about the all-important technique of divide-and-conquer, stability, and best and worst case timings.

This section will follow the same structure of introducing you to a concept with a chapter, followed by a Challenge chapter to practice the skills you are acquiring.

Studying sorting may seem a bit academic and disconnected from the “real world” of app development, but understanding the tradeoffs for these simple cases will lead you to a better understanding and let you analyze any algorithm.

Toggle description
O(n²) time complexity is not great performance, but the sorting algorithms in this category are easy to understand and useful in some scenarios. These algorithms are space-efficient; they only require constant O(1) additional memory space. In this chapter, you'll look at the bubble sort, selection sort, and insertion sort algorithms.
Toggle description
Challenge exercises for O(n²) sorting.
Toggle description
Merge sort is one of the most efficient sorting algorithms. With a time complexity of O(log n), it’s one of the fastest of all general-purpose sorting algorithms. The idea behind merge sort is divide and conquer: to break up a big problem into several smaller, easier to solve problems and then combine those solutions into a final result. The merge sort mantra is to split first and merge after.
Toggle description
Challenge questions for merge-sort.
Toggle description
In this chapter, you’ll look at a completely different model of sorting. So far, you’ve been relying on comparisons to determine the sorting order. Radix sort is a non-comparative algorithm for sorting integers in linear time. There are multiple implementations of radix sort that focus on different problems. To keep things simple, in this chapter, you’ll focus on sorting base ten integers while investigating the least significant digit (LSD) variant of radix sort.
Toggle description
Challenge questions for radix sort.
Toggle description
Heapsort is another comparison-based algorithm that sorts an array in ascending order using a heap. This chapter builds on the heap concepts presented in Chapter 22, “Heaps”.Heapsort takes advantage of a heap being, by definition, a partially sorted binary tree.
Toggle description
Challenge questions for heapsort.
Toggle description
In the preceding chapters, you’ve learned to sort an array using comparison-based sorting algorithms, merge sort, and heap sort. Quicksort is another comparison-based sorting algorithm. Much like merge sort, it uses the same strategy of divide and conquer. In this chapter, you will implement Quicksort and look at various partitioning strategies to get the most out of this sorting algorithm.
Toggle description
Challenge questions for Quicksort.

Section V: Graphs

Graphs are an instrumental data structure that can model a wide range of things: webpages on the internet, the migration patterns of birds, protons in the nucleus of an atom. This section gets you thinking deeply (and broadly) about using graphs and graph algorithms to solve real-world problems.

The chapters that follow will give the foundation you need to understand graph data structures. Like previous sections, every other chapter will serve as a Challenge chapter so you can practice what you’ve learned.

After completing this section, you will have powerful tools at your disposal to model and solve important real-life problems using graphs. Let’s get started!

Toggle description
What do social networks have in common with booking cheap flights around the world? You can represent both of these real-world models as graphs! A graph is a data structure that captures relationships between objects. It is made up of vertices connected by edges. In a weighted graph, every edge has a weight associated with it that represents the cost of using this edge. These weights let you choose the cheapest or shortest path between two vertices.
Toggle description
Challenge questions for graphs.
Toggle description
In the previous chapter, you explored using graphs to capture relationships between objects. Several algorithms exist to traverse or search through a graph's vertices. One such algorithm is the breadth-first search algorithm, which solves many problems, including generating a minimum spanning tree, finding potential paths between vertices, and finding the shortest path between two vertices.
Toggle description
Challenge questions for breadth-first search.
Toggle description
In the previous chapter, you looked at breadth-first search, where you had to explore every neighbor of a vertex before going to the next level. In this chapter, you will look at depth-first search, which has applications for topological sorting, detecting cycles, pathfinding in maze puzzles, and finding connected components in a sparse graph.
Toggle description
Challenge questions for depth-first search.
Toggle description
Have you ever used the Google or Apple Maps app to find the shortest or fastest from one place to another? Dijkstra’s algorithm is particularly useful in GPS networks to help find the shortest path between two places. Dijkstra’s algorithm is a greedy algorithm, which constructs a solution step-by-step, and picks the most optimal path at every step in isolation.
Challenge questions for Dijkstra's algorithm.
Toggle description
In previous chapters, you’ve looked at depth-first and breadth-first search algorithms. These algorithms form spanning trees. This chapter will look at Prim’s algorithm, a greedy algorithm used to construct a minimum spanning tree. A minimum spanning tree is a spanning tree with weighted edges where the total weight of all edges is minimized. You’ll learn how to implement a greedy algorithm to construct a solution step-by-step and pick the most optimal path at every step.
Toggle description
Challenge questions for Prim’s spanning tree.