Algorithmen und Datenstrukturen in Swift: Ein vollständiger Leitfaden für iOS-Entwickler

Algorithmen und Datenstrukturen in Swift: Von den Grundlagen bis zu fortgeschrittenen Techniken

Das Verständnis von Algorithmen und Datenstrukturen ist die Grundlage, die einen Anfänger-Entwickler von einem erfahrenen Ingenieur unterscheidet. Für einen iOS/macOS-Entwickler, der mit Swift arbeitet, beeinflusst dieses Wissen direkt die Leistung der Anwendung, die Reaktionszeit der Benutzeroberfläche und die Effizienz der Speichernutzung. In diesem Artikel behandeln wir die wichtigsten Datenstrukturen und Algorithmen, die jeder Swift-Entwickler kennen sollte, mit praktischen Codebeispielen.

1. Grundlegende Datenstrukturen in Swift: Arrays, Sets und Dictionaries

Swift bietet leistungsstarke integrierte Collections, aber das Verständnis ihrer internen Funktionsweise hilft, effizienteren Code zu schreiben.

Arrays (Array)

Ein Array ist eine geordnete Sammlung von Elementen mit Zugriff über einen Index. In Swift ist Array als dynamisches Array mit einer amortisierten Komplexität von O(1) für das Hinzufügen am Ende implementiert.

// Erstellung und grundlegende Operationenvar numbers = [1, 2, 3, 4, 5]numbers.append(6) // O(1) im Durchschnittnumbers.insert(0, at: 0) // O(n) — Verschiebung der Elementelet first = numbers[0] // O(1)numbers.removeLast() // O(1)numbers.remove(at: 2) // O(n) — Verschiebung

Sets (Set)

Set ist eine ungeordnete Sammlung eindeutiger Elemente. Es ist basierend auf einer Hash-Tabelle implementiert, was O(1) für Einfügen, Löschen und Suchen ergibt.

var uniqueNumbers: Set<Int> = [1, 2, 3, 3, 4]print(uniqueNumbers) // [1, 2, 3, 4] — Duplikate entferntuniqueNumbers.insert(5) // O(1)let contains = uniqueNumbers.contains(3) // true, O(1)

Dictionaries (Dictionary)

Ein assoziatives Array zum Speichern von Schlüssel-Wert-Paaren. Ebenfalls basierend auf Hash-Tabellen.

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. Benutzerdefinierte Datenstrukturen: Stacks, Queues und Linked Lists

Obwohl Swift keine integrierten Implementierungen von Stack und Queue hat, lassen sie sich leicht selbst implementieren.

Stack (Stack) — LIFO

Ein Stack funktioniert nach dem Prinzip "Last In, First Out". Er wird für Rückgängig-Funktionen und die Tiefensuche in Bäumen verwendet.

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 (Queue) — FIFO

Eine Queue funktioniert nach dem Prinzip "First In, First Out". Sie wird verwendet, um Aufgaben in der Reihenfolge ihres Eingangs zu verarbeiten.

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 (Linked List)

Eine Linked List besteht aus Knoten, von denen jeder auf den nächsten verweist. Sie ermöglicht das effiziente Einfügen/Entfernen von Elementen in der Mitte der Liste.

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