Algorithmes et structures de données en Swift : guide complet pour développeur iOS

Algorithmes et structures de données en Swift : des bases aux techniques avancées

La compréhension des algorithmes et des structures de données est le fondement qui distingue un développeur débutant d'un ingénieur expérimenté. Pour un développeur iOS/macOS travaillant en Swift, cette connaissance impacte directement les performances de l'application, le temps de réponse de l'interface et l'efficacité de l'utilisation de la mémoire. Dans cet article, nous allons décortiquer les structures de données et algorithmes clés que tout développeur Swift se doit de connaître, avec des exemples de code pratiques.

1. Structures de données de base en Swift : tableaux, ensembles et dictionnaires

Swift fournit des collections intégrées puissantes, mais comprendre leur fonctionnement interne aide à écrire un code plus efficace.

Tableaux (Array)

Un tableau est une collection ordonnée d'éléments avec un accès par index. En Swift, Array est implémenté comme un tableau dynamique avec une complexité amortie de O(1) pour l'ajout à la fin.

// Création et opérations de basevar numbers = [1, 2, 3, 4, 5]numbers.append(6) // O(1) en moyennenumbers.insert(0, at: 0) // O(n) — décalage des élémentslet first = numbers[0] // O(1)numbers.removeLast() // O(1)numbers.remove(at: 2) // O(n) — décalage

Ensembles (Set)

Set est une collection non ordonnée d'éléments uniques. Implémentée sur la base d'une table de hachage, elle offre O(1) pour l'insertion, la suppression et la recherche.

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

Dictionnaires (Dictionary)

Tableau associatif pour stocker des paires "clé-valeur". Également basé sur des tables de hachage.

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. Structures de données personnalisées : piles, files d'attente et listes chaînées

Bien que Swift n'ait pas d'implémentations intégrées pour la pile et la file d'attente, il est facile de les implémenter soi-même.

Pile (Stack) — LIFO

La pile fonctionne sur le principe "dernier entré, premier sorti". Elle est utilisée pour annuler des actions, parcourir des arbres en profondeur.

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

File d'attente (Queue) — FIFO

La file d'attente fonctionne sur le principe "premier entré, premier sorti". Elle est utilisée pour traiter des tâches dans l'ordre d'arrivée.

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"

Liste chaînée (Linked List)

Une liste chaînée est composée de nœuds, chacun référençant le suivant. Elle permet d'insérer/supprimer efficacement des éléments au milieu de la 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