Swift算法与数据结构：iOS开发者完整指南

Swift 算法与数据结构：从基础到高级技巧

理解算法与数据结构是区分初级开发者和资深工程师的基础。对于使用 Swift 的 iOS/macOS 开发者而言，这些知识直接影响应用性能、界面响应时间和内存使用效率。本文将介绍每位 Swift 开发者需要掌握的关键数据结构和算法，并附有实用代码示例。

1. Swift 基础数据结构：数组、集合与字典

Swift 提供了强大的内置集合类型，但理解其内部工作机制有助于编写更高效的代码。

数组（Array）

数组是有序的元素集合，支持基于索引的访问。Swift 的 Array 实现为动态数组，尾部追加元素的摊还时间复杂度为 O(1)。

// 创建与基本操作var numbers = [1, 2, 3, 4, 5]numbers.append(6) // 平均 O(1)numbers.insert(0, at: 0) // O(n) — 元素移位let first = numbers[0] // O(1)numbers.removeLast() // O(1)numbers.remove(at: 2) // O(n) — 移位

集合（Set）

Set 是无序的唯一元素集合。它基于哈希表实现，插入、删除和查找操作的时间复杂度均为 O(1)。

var uniqueNumbers: Set<Int> = [1, 2, 3, 3, 4]print(uniqueNumbers) // [1, 2, 3, 4] — 重复项被移除uniqueNumbers.insert(5) // O(1)let contains = uniqueNumbers.contains(3) // true, O(1)

字典（Dictionary）

用于存储键值对的关联数组。同样基于哈希表实现。

var scores: [String: Int] = ["Alice": 95, "Bob": 87]scores["Charlie"] = 92 // O(1)if let aliceScore = scores["Alice"] {    print("Alice: \\(aliceScore)")}scores.removeValue(forKey: "Bob") // O(1)

2. 自定义数据结构：栈、队列与链表

尽管 Swift 没有内置的栈和队列实现，但我们可以轻松地自行创建。

栈（Stack）— 后进先出

栈遵循"后进先出"原则。常用于撤销操作和树的深度优先遍历。

struct Stack<Element> {    private var storage: [Element] = []        mutating func push(_ element: Element) { storage.append(element) }    mutating func pop() -> Element? { storage.popLast() }    func peek() -> Element? { storage.last }    var isEmpty: Bool { storage.isEmpty }}

var stack = Stack<Int>()stack.push(1); stack.push(2); stack.push(3)print(stack.pop()!) // 3print(stack.peek()!) // 2

队列（Queue）— 先进先出

队列遵循"先进先出"原则。用于按到达顺序处理任务。

struct Queue<Element> {    private var input: [Element] = []    private var output: [Element] = []        mutating func enqueue(_ element: Element) { input.append(element) }        mutating func dequeue() -> Element? {        if output.isEmpty {            output = input.reversed()            input.removeAll()        }        return output.popLast()    }        var isEmpty: Bool { input.isEmpty && output.isEmpty }}

var queue = Queue<String>()queue.enqueue("First"); queue.enqueue("Second")print(queue.dequeue()!) // "First"

链表（Linked List）

链表由节点组成，每个节点指向下一个节点。它允许在列表中间高效地插入/删除元素。

class ListNode<T> {    var value: T    var next: ListNode?    init(_ value: T) { self.value = value }}

class LinkedList<T> {    var head: ListNode<T>?        func append(_ valu