Une liste doublement liée a une surcharge minimale (juste un autre pointeur par cellule), et vous permet d'ajouter aux deux extrémités et de faire des allers-retours et de vous amuser généralement.

Eh bien, si vous regardez un peu plus en profondeur, les deux incluent également des tableaux dans le langage de base:

• Le 5e rapport de schéma révisé (R5RS) inclut le type de vecteur , qui sont des collections indexées sur des nombres entiers de taille fixe avec un temps meilleur que linéaire pour un accès aléatoire.
• Le rapport Haskell 98 a également un type de tableau .

Cependant, l'instruction de programmation fonctionnelle a longtemps mis l'accent sur les listes à simple lien plutôt que sur les tableaux ou les listes à double lien. En fait, il est fort probable que ce soit trop souligné. Il y a cependant plusieurs raisons à cela.

La première est que les listes à lien unique sont l'un des types de données récursives les plus simples et les plus utiles. Un équivalent défini par l'utilisateur du type de liste de Haskell peut être défini comme ceci:

data List a           -- A list with element type `a`...
  = Empty             -- is either the empty list...
  | Cell a (List a)   -- or a pair with an `a` and the rest of the list. 

Le fait que les listes soient un type de données récursif signifie que les fonctions qui fonctionnent sur les listes utilisent généralement la récursivité structurelle . En termes Haskell: vous réglez la correspondance sur les constructeurs de liste, et vous récursivement sur une sous - partie de la liste. Dans ces deux définitions de fonction de base, j'utilise la variable aspour faire référence à la fin de la liste. Notez donc que les appels récursifs "descendent" dans la liste:

map :: (a -> b) -> List a -> List b
map f Empty = Empty
map f (Cell a as) = Cell (f a) (map f as)

filter :: (a -> Bool) -> List a -> List a
filter p Empty = Empty
filter p (Cell a as)
    | p a = Cell a (filter p as)
    | otherwise = filter p as

Cette technique garantit que votre fonction se terminera pour toutes les listes finies, et est également une bonne technique de résolution de problèmes - elle a tendance à diviser naturellement les problèmes en sous-parties plus simples et plus tenables.

Les listes à liaison unique sont donc probablement le meilleur type de données pour initier les étudiants à ces techniques, qui sont très importantes en programmation fonctionnelle.

La deuxième raison est moins une raison «pourquoi des listes à liaison unique», mais plutôt une raison «pourquoi pas des listes ou tableaux à double liaison»: ces derniers types de données appellent souvent mutation (variables modifiables), programmation fonctionnelle très souvent fuit. Alors comme ça arrive:

• Dans un langage passionné comme Scheme, vous ne pouvez pas créer une liste à double lien sans utiliser de mutation.
• Dans un langage paresseux comme Haskell, vous pouvez créer une liste à double liaison sans utiliser de mutation. Mais chaque fois que vous créez une nouvelle liste basée sur celle-ci, vous êtes obligé de copier la plupart sinon la totalité de la structure de l'original. Alors qu'avec les listes à lien unique, vous pouvez écrire des fonctions qui utilisent le «partage de structure» - les nouvelles listes peuvent réutiliser les cellules des anciennes listes lorsque cela est approprié.
• Traditionnellement, si vous utilisiez des tableaux de manière immuable, cela signifiait qu'à chaque fois que vous vouliez modifier le tableau, vous deviez copier le tout. (Les bibliothèques Haskell récentes comme vector, cependant, ont trouvé des techniques qui améliorent considérablement ce problème).

La troisième et dernière raison s'applique principalement aux langages paresseux comme Haskell: dans la pratique, les listes à liaison unique paresseuses sont souvent plus similaires aux itérateurs qu'aux listes en mémoire proprement dites. Si votre code consomme les éléments d'une liste de façon séquentielle et les jette au fur et à mesure, le code objet ne matérialise que les cellules de la liste et son contenu lorsque vous avancez dans la liste.

Cela signifie que la liste entière n'a pas besoin d'exister en mémoire à la fois, seulement la cellule actuelle. Les cellules avant celle en cours peuvent être récupérées (ce qui ne serait pas possible avec une liste à double liaison); les cellules postérieures à la cellule actuelle n'ont pas besoin d'être calculées tant que vous n'y êtes pas.

Cela va encore plus loin. Il existe une technique utilisée dans plusieurs bibliothèques Haskell populaires, appelée fusion , où le compilateur analyse votre code de traitement de liste et repère les listes intermédiaires qui sont générées et consommées séquentiellement puis «jetées». Avec cette connaissance, le compilateur peut éliminer complètement l'allocation de mémoire des cellules de ces listes. Cela signifie qu'une liste à liaison unique dans un programme source Haskell, après compilation, pourrait en fait devenir une boucle au lieu d'une structure de données.

La fusion est également la technique utilisée par la vectorbibliothèque susmentionnée pour générer du code efficace pour des tableaux immuables. Il en va de même pour les bibliothèques extrêmement populaires bytestring(tableaux d'octets) et text(chaînes Unicode), qui ont été construites en remplacement du Stringtype natif pas très génial de Haskell (qui est le même que la [Char]liste de caractères à lien unique). Donc, dans Haskell moderne, il existe une tendance où les types de tableaux immuables avec prise en charge de la fusion deviennent très courants.

La fusion de listes est facilitée par le fait que dans une liste à lien unique, vous pouvez avancer mais jamais reculer . Cela soulève un thème très important dans la programmation fonctionnelle: utiliser la "forme" d'un type de données pour dériver la "forme" d'un calcul. Si vous souhaitez traiter les éléments de manière séquentielle, une liste à liaison unique est un type de données qui, lorsque vous le consommez avec une récursivité structurelle, vous donne ce modèle d'accès très naturellement. Si vous souhaitez utiliser une stratégie "diviser pour mieux régner" pour attaquer un problème, les structures de données arborescentes ont tendance à très bien le prendre en charge.

Beaucoup de gens abandonnent le chariot de programmation fonctionnelle dès le début, ils sont donc exposés aux listes à lien unique, mais pas aux idées sous-jacentes plus avancées.

Parce qu'ils fonctionnent bien avec l'immuabilité. Supposons que vous ayez deux listes immuables, [1, 2, 3]et [10, 2, 3]. Représentés comme des listes liées individuellement où chaque élément de la liste est un nœud contenant l'élément et un pointeur vers le reste de la liste, ils ressemblent à ceci:

node -> node -> node -> empty
 1       2       3

node -> node -> node -> empty
 10       2       3

Voyez comment les [2, 3]portions sont identiques? Avec des structures de données mutables, ce sont deux listes différentes, car le code qui écrit de nouvelles données dans l'une d'elles ne doit pas affecter le code utilisant l'autre. Cependant, avec des données immuables , nous savons que le contenu des listes ne changera jamais et que le code ne peut pas écrire de nouvelles données. Nous pouvons donc réutiliser les queues et faire en sorte que les deux listes partagent une partie de leur structure:

node -> node -> node -> empty
 1      ^ 2       3
        |
node ---+
 10

Étant donné que le code utilisant les deux listes ne les mutera jamais, nous n'avons jamais à nous soucier des modifications d'une liste affectant l'autre. Cela signifie également que lorsque vous ajoutez un élément au début de la liste, vous n'avez pas à copier et à créer une toute nouvelle liste.

Cependant, si vous essayez de représenter [1, 2, 3]et [10, 2, 3]de listes doublement liées:

node <-> node <-> node <-> empty
 1       2       3

node <-> node <-> node <-> empty
 10       2       3

Maintenant, les queues ne sont plus identiques. Le premier [2, 3]a un pointeur vers 1la tête, mais le second a un pointeur vers 10. En outre, si vous souhaitez ajouter un nouvel élément à la tête de la liste, vous devez muter la tête précédente de la liste pour la faire pointer vers la nouvelle tête.

Le problème des têtes multiples pourrait potentiellement être résolu en faisant en sorte que chaque nœud stocke une liste des têtes connues et en modifiant la création de nouvelles listes, mais vous devez ensuite travailler à maintenir cette liste aux cycles de récupération de place lorsque les versions de la liste avec des têtes différentes ont des durées de vie différentes en raison de leur utilisation dans différents morceaux de code. Cela ajoute de la complexité et des frais généraux, et la plupart du temps cela n'en vaut pas la peine.

La réponse de @ sacundim est principalement vraie, mais il existe également d'autres informations importantes sur les compromis concernant les conceptions linguistiques et les exigences pratiques.

Objets et références

Ces langages imposent (ou supposent) généralement des objets ayant des étendues dynamiques non liées (ou dans le langage de C, durée de vie , bien que pas exactement la même en raison des différences de signification des objets parmi ces langages, voir ci-dessous) par défaut, en évitant les références de première classe ( par exemple, pointeurs d'objets en C) et comportement imprévisible dans les règles sémantiques (par exemple comportement indéfini d'ISO C concernant la sémantique).

De plus, la notion d'objets (de première classe) dans de tels langages est restrictive de façon conservatrice: aucune propriété "locative" n'est spécifiée et garantie par défaut. Ceci est complètement différent dans certains langages de type ALGOL dont les objets sont sans étendues dynamiques non liées (par exemple en C et C ++), où les objets signifient essentiellement des sortes de "stockage typé", généralement couplés avec des emplacements de mémoire.

Encoder le stockage dans les objets présente des avantages supplémentaires comme la possibilité d'attacher des effets de calcul déterministes tout au long de leur vie, mais c'est un autre sujet.

Problèmes de simulation des structures de données

Sans références de première classe, les listes à liaison unique ne peuvent pas simuler de nombreuses structures de données traditionnelles (avides / mutables) de manière efficace et transférable, en raison de la nature de la représentation de ces structures de données et des opérations primitives limitées dans ces langues. (Au contraire, en C, vous pouvez dériver des listes liées assez facilement même dans un programme strictement conforme .) Et de telles structures de données alternatives comme les tableaux / vecteurs ont des propriétés supérieures par rapport aux listes liées individuellement dans la pratique. C'est pourquoi R ⁵ RS introduit de nouvelles opérations primitives.

Mais il existe des différences entre les types de vecteurs / tableaux et les listes à double liaison. Un tableau est souvent supposé avec une complexité de temps d'accès O (1) et moins de surcharge d'espace, qui sont d'excellentes propriétés non partagées par les listes. (Bien qu'à strictement parler, ni l'un ni l'autre ne soit garanti par l'ISO C, mais les utilisateurs s'y attendent presque toujours et aucune implémentation pratique ne violerait trop évidemment ces garanties implicites.) OTOH, une liste à double liaison rend souvent les deux propriétés encore pire qu'une liste à liaison unique , tandis que l'itération en arrière / en avant est également prise en charge par un tableau ou un vecteur (avec des indices entiers) avec encore moins de surcharge. Ainsi, une liste doublement couplée ne fonctionne pas mieux en général. Encore pire, les performances sur l'efficacité du cache et la latence sur l'allocation dynamique de mémoire des listes sont catastrophiquement pires que les performances des tableaux / vecteurs lors de l'utilisation de l'allocateur par défaut fourni par l'environnement d'implémentation sous-jacent (par exemple libc). Ainsi, sans un runtime très spécifique et «intelligent» optimisant fortement ces créations d'objets, les types de tableau / vecteur sont souvent préférés aux listes liées. (Par exemple, en utilisant ISO C ++, il y a une mise en garde quistd::vectordevrait être préféré à std::listpar défaut.) Ainsi, introduire de nouvelles primitives pour supporter spécifiquement les listes liées (doublement) n'est certainement pas aussi bénéfique que de prendre en charge les structures de données de tableau / vecteur dans la pratique.

Pour être honnête, les listes ont toujours certaines propriétés spécifiques mieux que les tableaux / vecteurs:

• Les listes sont basées sur les nœuds. La suppression d'éléments des listes n'invalide pas la référence à d'autres éléments dans d'autres nœuds. (Cela est également vrai pour certaines structures de données arborescentes ou graphiques.) OTOH, les tableaux / vecteurs peuvent faire référence à la position de fin invalidée (avec une réallocation massive dans certains cas).
• Les listes peuvent épisser en O (1) temps. La reconstruction de nouveaux tableaux / vecteurs avec ceux actuels est beaucoup plus coûteuse.

Cependant, ces propriétés ne sont pas trop importantes pour une langue avec prise en charge intégrée des listes à liaison unique, qui est déjà capable d'une telle utilisation. Bien qu'il existe encore des différences, dans les langues avec des étendues dynamiques obligatoires d'objets (ce qui signifie généralement qu'il y a un garbage collector gardant les références pendantes), l'invalidation peut également être moins importante, selon les intentions. Ainsi, les seuls cas où les listes doublement liées gagnent peuvent être:

• Des exigences de garantie de non-réallocation et d'itération bidirectionnelle sont nécessaires. (Si les performances de l'accès aux éléments sont importantes et que l'ensemble de données est suffisamment grand, je choisirais plutôt des arbres de recherche binaires ou des tables de hachage.)
• Des opérations d'épissure bidirectionnelles efficaces sont nécessaires. C'est extrêmement rare. (Je ne remplis les conditions que pour implémenter quelque chose comme des enregistrements d'historique linéaire dans un navigateur.)

Immuabilité et repliement

Dans un langage pur comme Haskell, les objets sont immuables. Les objets du schéma sont souvent utilisés sans mutation. Un tel fait permet d'améliorer efficacement l'efficacité de la mémoire avec l' internement d'objet - partage implicite de plusieurs objets avec la même valeur à la volée.

Il s'agit d'une stratégie d'optimisation de haut niveau agressive dans la conception du langage. Cependant, cela implique des problèmes de mise en œuvre. Il introduit en fait des alias implicites dans les cellules de stockage sous-jacentes. Cela rend l'analyse d'alias plus difficile. En conséquence, il y a probablement moins de possibilités d'éliminer les frais généraux des références non de première classe, même les utilisateurs ne les touchent jamais du tout. Dans des langues comme Scheme, une fois que la mutation n'est pas totalement exclue, cela interfère également avec le parallélisme. Cependant, cela peut être correct dans une langue paresseuse (qui a déjà des problèmes de performances causés par les thunks).

Pour la programmation à usage général, un tel choix de conception de langage peut être problématique. Mais avec certains modèles de codage fonctionnels communs, les langages semblent toujours bien fonctionner.