Listes liées dans Swift

Question

J'ai décidé d'améliorer ma connaissance des structures de données et je suis tombé sur la liste des liens. Je me demandais si quelqu'un avait un exemple concret de la façon dont nous les utilisons par rapport au développement mobile ou à tout autre type de projet qui utilise swift comme langue, car il me semble que la classe Array a déjà assez de flexibilité. est.

Answer 1

Vous devez utiliser des listes chaînées chaque fois que vous avez besoin de leur avantage principal: O (1) insertion et suppression à des points arbitraires dans la liste. L'erreur que la plupart des gens font avec les listes chaînées est de les implémenter comme type de valeur dans Swift. C'est très difficile et la structure de données qui en résulte est généralement inutile. La forme la plus commune est avec une énumération:

enum List<T> { 
    indirect case Cons(T, List<T>) 
    case Nil 
} 

let list = List.Cons(1, .Cons(2, .Cons(3, .Nil))) 

Je n'ai jamais vu quelqu'un arriver avec une implémentation efficace de cela. Les collections efficaces dans Swift nécessitent une copie sur écriture, ce qui est très difficile à construire pour une énumération.

La manière naturelle de créer des listes chaînées dans Swift est un type de référence mutable. C'est très facile à rendre efficace et très utile.

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

let list = List(1, List(2, List(3, nil))) 

Et sous cette forme, utiliser cette fonctionnalité? Tout moment O (1) l'insertion et la suppression des points arbitraires dans la liste.

Vous pouvez également créer ce type de référence immuable (en utilisant let) si vous avez plusieurs grandes listes partageant une queue significative. Je n'ai jamais vu ça arriver en pratique.

La plupart des gens que je connais qui suivent cette voie veulent une liste liée immuable afin qu'ils puissent implémenter les nombreux algorithmes récursifs très beaux qui sont construits sur eux et qui sont très communs dans les langages FP (ceci peut dire plus sur les gens savoir que la question elle-même). Mais Swift est au mieux modérément hostile à la récursivité, donc cela vaut rarement la peine de l'ennoier sauf en tant qu'exercice. Mais les algorithmes récursifs ne sont qu'une utilisation des listes chaînées. En tant que structure de données d'insertion arbitraire O (1), elles sont aussi utiles dans Swift que dans Pascal et C, et vous les construisez à peu près de la même manière.