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

【One-Line Pitch】 A hands-on tour of classic data structures and algorithms written specifically for Swift developers, using Swift 4 and Xcode 9. Best for iOS/macOS engineers who want to understand what happens under the hood of the standard library and prepare for technical interviews. 【Book Arc】 - **Opening (~0%–12%)**: Sets up the toolchain (macOS Sierra, Xcode 9, Swift 4) and establishes the core vocabulary of complexity analysis, then contrasts the Swift `Array` (ordered, random-access, O(1) `count`) with the linked list, building a `Node` and the basic list operations. - **Early (~12%–32%)**: Moves from linked lists into abstract data types — stacks (LIFO via `push`/`pop`), queues (array, doubly linked list, ring buffer, and two-stack implementations), and then trees, covering binary trees, the three traversal orders, and the binary search tree with its insert/remove/contains methods. - **Middle (~32%–52%)**: Tackles the BST's weakness — imbalance — with the self-balancing AVL tree and its four rotations (left, left-right, right, right-left), then branches into specialized structures: tries for prefix matching and heaps stored as flat arrays with sift-up/sift-down operations. - **Late (~52% onward)**: The excerpts thin out here; the remaining material appears to continue into further algorithms and structures, but the sample does not cover the specifics in detail. 【Key Takeaways】 - **Complexity is the lens for every choice** (Opening): The book repeatedly grounds decisions in Big-O — `count` is O(1), array insertion is O(n), BST insertion is O(log n) when balanced. This framing is what makes the structures comparable rather than just catalogued. - **Swift's `Array` is not a neutral default** (Opening): Its ordered, zero-based, random-access nature is a guarantee, not a given — dictionaries have weaker ordering, and linked lists and trees lack constant-time access entirely. - **Linked lists trade access for mutation** (Opening): Constant-time insertion and removal at the front, plus reliable performance characteristics, come at the cost of O(n) traversal — and implementing `Collection` conformance requires a custom index and careful copy-on-write handling with `isKnownUniquelyReferenced`. - **The same abstract type has many implementations** (Early): Queues are built four different ways (array, doubly linked list, ring buffer, two-stack), each with distinct performance profiles — a concrete lesson that the interface and the implementation are separate concerns. - **Unbalanced trees are the BST's Achilles' heel** (Early): Operations degrade from O(log n) to O(n) when the tree skews, which is precisely the motivation for the AVL tree's rotations. - **Rotations preserve in-order traversal while reducing depth** (Middle): The four rotation types (left, left-right, right, right-left) are the mechanism that keeps AVL trees balanced, and the book emphasizes that in-order traversal is unchanged after a rotation. - **Tries beat arrays for prefix matching at scale** (Middle): With O(k*m) versus O(k*n) complexity, tries outperform array-based prefix matching for large, uniformly distributed datasets. - **Heaps live happily in a flat array** (Middle): Representing a binary heap level-by-level in an array yields efficient time and space complexity and makes element swapping — central to sift-up and sift-down — easier than with a node-based tree. 【Reading Tips】 - **Deep-read the complexity discussions**: The Big-O analysis is the transferable knowledge; the specific Swift code is version-dependent (Swift 4/Xcode 9) and will need adaptation. - **Skim the toolchain setup**: The opening requirements (macOS Sierra 10.12.6, Xcode 9) are dated; modern readers can move quickly to the data structure chapters. - **Work the playgrounds alongside the text**: The book is structured around starter playgrounds and `example(of:)` blocks — typing the code is where the learning happens. - **Focus on the "why" behind each implementation choice**: The queue chapter's four implementations and the heap's array representation are the most instructive parts for building intuition. - **Treat the AVL rotations as the hard spot**: The four rotation cases are the most conceptually demanding section; expect to re-read and trace the diagrams. 【Coverage Limits】 This guide is based on stratified excerpts covering roughly the first half of the book (through heaps); the later chapters and any advanced algorithms beyond that point are not represented in the sample, so their content is not summarized here.