Quelles sont les règles concrètes pour utiliser une liste chaînée au lieu d'un tableau?

18

Une liste chaînée peut être utilisée lorsque vous souhaitez insérer et supprimer des éléments à bas prix et que peu importe que les éléments ne soient pas côte à côte en mémoire.

C'est très abstrait et j'aimerais une explication concrète de la raison pour laquelle une liste chaînée devrait être utilisée plutôt qu'un tableau. Je ne suis pas très expérimenté en programmation, donc je n'ai pas beaucoup (voire pas) d'expérience dans le monde réel.

data-structures linked-list à droite
la source
3
Honnêtement, je ne pense pas que les exemples signifient autant pour vous jusqu'à ce que vous ayez une certaine expérience de l'écriture de quelque chose, puis de voir l'effet que la modification des structures de données a sur votre code. Soit essayez d'écrire quelque chose qui vous intéresse, et déterminez quelles structures de données et conteneurs sont les mieux adaptés, ou regardez un code existant et réfléchissez à la raison pour laquelle chaque conteneur a été sélectionné, et quel effet le changer aurait.
inutile
Je ne pense pas qu'il soit possible de communiquer utilement les compromis et les effets secondaires de la sélection de la structure de données au PO (inexpérimenté) sans un exemple beaucoup plus long que ce qui est raisonnable ici. Les exemples donnés comme réponses sont bons et répondent à la question telle que posée, mais pas (ce que je lis) à une demande implicite de compréhension réelle.
inutile

Réponses:

37

Voici quelque chose à mi-chemin entre un exemple et une analogie. Vous avez des courses à faire, alors prenez un morceau de papier et écrivez:

  • banque
  • les courses
  • déposer le nettoyage à sec

Ensuite, vous vous souvenez que vous devez également acheter des timbres. En raison de la géographie de votre ville, vous devez le faire après la banque. Vous pouvez copier toute votre liste sur une nouvelle feuille de papier:

  • banque
  • timbres
  • les courses
  • déposer le nettoyage à sec

ou vous pourriez gribouiller sur celui que vous aviez:

  • banque ....... TIMBRES
  • les courses
  • déposer le nettoyage à sec

Comme vous avez pensé à d'autres courses, vous pouvez les écrire au bas de la liste, mais avec des flèches vous rappelant dans quel ordre les faire. Il s'agit d'une liste liée. C'est plus rapide et plus facile que de copier toute la liste à chaque fois que vous ajoutez quelque chose.

Ensuite, votre téléphone portable sonne pendant que vous êtes à la banque "hé, j'ai les timbres, ne décrochez plus". Vous rayez simplement STAMPS de la liste, vous n'en réécrivez pas un tout nouveau sans STAMPS.

Maintenant, vous pouvez réellement implémenter une liste de courses dans le code (peut-être une application qui met vos courses en ordre en fonction de votre géographie) et il y a une chance raisonnable que vous utilisiez réellement une liste liée pour cela dans le code. Vous souhaitez ajouter et supprimer de nombreux éléments, les commandes doivent être traitées, mais vous ne voulez pas recopier la liste entière après chaque insertion ou suppression.

Kate Gregory
la source
3
Selon Bjarne Stroustrup, les LL peuvent ne pas être aussi rapides et faciles à copier que vous le pensez .
Dennis
@ Dennis oui, je sais, grâce au déplacement de la sémantique. Cependant, ce n'est pas vrai pour toutes les langues, donc l'exemple est valable.
Kate Gregory
1
@KateGregory est assez juste, mais il est toujours bon de souligner que les structures de données "de base" sont souvent meilleures que les structures de données intéressantes que nous apprenons à l'école (ou ailleurs). Je ne veux pas que les nouveaux diplômés utilisent les LL partout parce que c'est théoriquement approprié tout en étant un mauvais choix réaliste. Il est important d'utiliser la bonne structure de données, et parfois les gens la compliquent trop. Un peu lié est cet exposé de Jonathan Blow (créateur de "Braid") sur les structures de données .
Dennis
1
@Ray: Une liste chaînée peut surperformer une structure arborescente si vous vous attendez à ce qu'elle soit de l'ordre de 4 éléments et les comparaisons sont relativement bon marché. Je ne sais pas exactement où se situe la coupure, où ce n'est pas le cas. En outre, une structure arborescente nécessite que vos données puissent être triées, tandis qu'une structure de liste vous permet de conserver l'ordre d'insertion (ou tout ordre arbitraire).
David Stone
2
Je ne pense pas que cette analogie soit très précise. En tant qu'êtres humains, nous pouvons (au moins pour une liste aussi courte) trouver un élément dans O (1). Mais si vous voulez faire un insert aléatoire dans une liste chaînée, vous devrez traverser la moitié des éléments en moyenne ce qui vous coûte O (n) seulement pour trouver la position où vous voulez insérer. L'insert réel ne coûte alors que O (1) mais avec un tableau, votre coût est également «seulement» O (n). La raison n'est donc pas seulement due au déplacement de la sémantique mais aussi à l'algorithmique. Le facteur constant caché par le big-O est cependant beaucoup plus important pour la liste aimée, en raison de l'accès à la mémoire non contigu.
5gon12eder
18
  • Les tables de hachage qui utilisent le chaînage pour résoudre les collisions de hachage ont généralement une liste liée par compartiment pour les éléments de ce compartiment.
  • Les allocateurs de mémoire simples utilisent une liste libre des régions de mémoire inutilisées, essentiellement une liste liée avec le pointeur de liste à l'intérieur de la mémoire libre elle-même
  • Dans un système de fichiers FAT , les métadonnées d'un fichier volumineux sont organisées comme une liste liée d'entrées FAT.
Michael Borgwardt
la source
12

La «pile d'appels» en langage C est implémentée sous forme de liste liée dans les API binaires x86 (et la plupart des autres).

Autrement dit, l'appel de procédure en langage C suit une discipline de premier entré, dernier sorti. Le résultat de l'exécution (éventuellement récursive) des appels de fonction est appelé «pile d'appels», ou parfois même «pile».

L' CALLinstruction x86 finit par implémenter une liste chaînée en utilisant la "pile d'appels". Une CALLinstruction pousse le contenu du registre% EIP, l'adresse de l'instruction après la CALLmémoire de la pile. Le prologue appelé fuction pousse le contenu du registre% EBP, l'adresse la plus basse des variables locales dans la fonction appelante, dans la mémoire de la pile. Ensuite, le prologue de la fonction appelée définit% EBP sur la base de pile de la fonction actuelle.

Cela signifie que% EBP est un pointeur vers un emplacement mémoire qui contient l'adresse de la valeur% EBP de la fonction appelante. Ce n'est rien de plus qu'une liste chaînée, implémentée partiellement dans le matériel via CALL.

Dans la mesure où cela est bon, c'est la façon dont les processeurs x86 implémentent les appels de fonction, en particulier les appels de fonction où la fonction a sa propre copie d'arguments et des variables locales à la fonction. Chaque appel de fonction pousse des informations sur la "pile d'appels" qui permettent au CPU de reprendre là où il s'était arrêté dans la fonction appelante, sans interférence de la fonction appelée ou de la fonction appelante.

Bruce Ediger
la source
3

Une liste liée peut être utilisée pour implémenter une file d'attente de messages.

Une file d'attente de messages est une structure dans laquelle nous stockons des informations sur les événements pour un traitement ultérieur. Par exemple, lorsque l'utilisateur appuie sur une touche ou déplace la souris, il s'agit d'un événement. Une application peut être occupée au moment où l'événement se produit, on ne peut donc pas s'attendre à ce qu'elle traite l'événement au moment précis où il se produit. Ainsi, l'événement est placé dans une file d'attente de messages (informations sur la touche enfoncée ou l'emplacement de déplacement de la souris) et lorsque l'application a du temps à perdre, elle vérifie sa file d'attente de messages, en récupère les événements et traite leur. (Cela se produit dans un laps de temps de quelques millisecondes, donc ce n'est pas visible.)

D'après le scénario d'utilisation que je viens de décrire, il devrait être évident que nous ne nous soucions jamais d'avoir un accès aléatoire aux événements stockés dans la file d'attente de messages; nous nous soucions seulement de pouvoir y stocker des messages et de les récupérer. Il est donc judicieux d'utiliser une liste chaînée, qui offre un temps d'insertion / suppression optimal.

(Veuillez ne pas insister pour souligner qu'une file d'attente de messages est susceptible, ou plus probable, ou presque aussi probable, d'être mise en œuvre à l'aide d'une liste de tableaux circulaire; c'est un détail technique et il a une limitation: vous ne pouvez stocker que un nombre limité de messages.)

Mike Nakis
la source