Swift Data Structure and Algorithms电子书

Swift Data Structure and Algorithms

Swift Data Structure and Algorithms

Credits

About the Authors

About the Reviewers

www.PacktPub.com

Why subscribe?

Preface

What this book covers

What you need for this book

Who this book is for

Conventions

Reader feedback

Customer support

Downloading the example code

Downloading the color images of this book

Errata

Piracy

Questions

1. Walking Across the Playground

What is the importance of data structures?

Data structures + algorithms = programs

Interactive Playgrounds

The Swift REPL

Fundamental data structures

Contiguous data structures

Arrays

Declaring an array

Retrieving elements

Adding elements

Removing elements

Linked data structures

Singly linked list

Overview of data structures

Overview of algorithms

Data types in Swift

Value types and reference types

Named and compound types

Type aliases

Collection types in the Swift standard library

Asymptotic analysis

Order of growth

Summary

2. Working with Commonly Used Data Structures

Using the Swift standard library

Why structures?

Declaring arrays in Swift

Initializing array

Adding and updating elements in an array

Retrieving and removing elements from an array

Retrieving and initializing dictionaries

Initializing a dictionary

Adding/modifying/removing a key-value pair

Retrieving values from a dictionary

Declaring sets

Initializing a set

Modifying and retrieving elements of a set

Set operations

Comparison operations

Membership and equality operations

Characteristics of tuples

Unnamed tuples

Named tuples

Implementing subscripting

Subscript syntax

Subscript options

Understanding mutability and immutability

Mutability of collections

Interoperability between Swift and Objective-C

Initialization

Swift type compatibility

Bridging collection classes

NSArray to Array

NSSet to set

NSDictionary to dictionary

Swift protocol-oriented programming

Dispatching

Protocol syntax

Protocols as types

Protocol extensions

Examining protocols for use in collections

Array literal syntax

Making an array enumerable

Sequence/IteratorProtocol

Summary

3. Standing on the Shoulders of Giants

Iterators, sequences, and collections

Iterators

Sequences

Collections

Stack

Applications

Implementation

Protocols

Queue

Applications

Implementation

Protocols

Circular buffer

Applications

Implementation

Protocols

Priority queue

Applications

Implementation

Protocols

StackList

Applications

Implementation

Protocols

Summary

4. Sorting Algorithms

The insertion sort

The algorithm

Analysis of the insertion sort

Use cases of the insertion sort

Optimizations

Merge sort

The algorithm for array-based merge sort

Analysis of merge sort

The algorithm and analysis for linked list-based merge sort

Performance comparison

Quick sort

The algorithm – Lomuto's implementation

Analysis of Lomuto's partitioning scheme

The algorithm – Hoare's implementation

Analysis of Hoare's partitioning scheme

Choice of pivot

The wrong way – first or last element

The wrong way – select random element

The right way

Improved pivot selection for quick sort algorithm

Optimizations

Summary

5. Seeing the Forest through the Tree

Tree – definition and properties

Overview of different types of tree

Binary tree

Binary search tree

B-tree

Splay tree

Red-black tree

Binary trees

Types and variations

Code

Binary search trees

Inserting a node

Tree walks (traversals)

Inorder tree walk

Preorder tree walk

Postorder tree walk

Searching

Deletion

B-trees,

Splay trees

Splay operation

Simple rotation or zig

Zig-Zig or Zag-Zag

Zig-Zag

Summary

6. Advanced Searching Methods

Red-black trees

Red-black tree node implementation

Rotations

Right rotation

Left rotation

Insertion

AVL trees

AVL tree node implementation

AVL tree rotations

Simple rotation left

Simple rotation right

Double rotation – right-left

Double rotation – left-right

Search

Insertion

Trie tree

Radix tree

A look at several substring search algorithms

Substring search algorithm examples

Naive (brute force) algorithm

The Rabin-Karp algorithm

Summary

7. Graph Algorithms

Graph theory

Types of graphs

Undirected graph

Directed graph

Weighted graph

Graph representations

Object-oriented approach – structs/classes

Adjacency list

Adjacency matrix

Incidence matrix

Data structures

Vertex

Edge

Adjacency list

Depth first search

Breadth first search

Spanning tree

Minimum spanning tree

Prim algorithm

Shortest path

Dijkstra algorithm

SwiftGraph

Summary

8. Performance and Algorithm Efficiency

Algorithm efficiency

Best, worst, and average cases

Measuring efficiency and the Big-O notation

Asymptotic analysis

How to calculate complexities

Orders of common functions

O(1)

O(log(n))

O(n)

O(nlog(n))

O(n^2)

O(2^n)

Graphic comparison

Evaluating runtime complexity

Summary

9. Choosing the Perfect Algorithm

URL shortener

Problems with long URL

URL shortener solution approach

URL shortener Swift implementation

Method 1 - searching for the correct tuple

Method 2 – accessing the correct array position by index

Searching in a huge amount of data

The huge blacklist problem

The huge blacklist solution approach

The huge blacklist Swift implementation

Method 2 – the Bloom filter solution

Summary

Epilogue