Les listes chaînées

Définition

Logo définition
Liste chaînée :
Une liste chaînée est une liste à accès séquentiel, où chaque élément contient une valeur et une référence à l'élément suivant. Dans le cas d'une liste chaînée circulaire, le dernier élément indique le premier élément de la liste comme étant son suivant.
Itinéraire : représentation d'une liste chaînée
Les listes chaînées sont une structure de données de type liste contenant une collection d'éléments liées entre eux par une référence à l'objet suivant. L'accès s'effectue séquentiellement par parcours de la liste en suivant les références d'un élément à l'autre. Une manière simple d'imaginer ceci est de se figurer un itinéraire où chaque grande ville rencontrée représenterait un élément d'une liste chaînée. Parcourir cette liste, c'est effectuer l'intégralité du trajet (Paris-Lyon sur l'exemple ci-contre). A chaque ville, le conducteur pourra trouver une référence vers l'élément suivant, à savoir un panneau indiquant la route/direction vers la ville suivante. Pour une liste chaînée, il en est de même: chaque élément contient la valeur de l'élément et une référence vers l'élément suivant, sous la forme d'un pointeur.

 
L'intérêt d'une telle liste est que sa taille peut varier dynamiquement sans soucis de la fragmentation de son stockage mémoire. S'il est vrai que les tableaux sont stockés de manière contigu en mémoire, il n'en va pas de même pour la liste chaînée, d'où sa plus grande souplesse d'emploi. Agrandir la liste revient à créer un nouvel élément en mémoire et à le lier à la liste chaînée par une référence vers son emplacement mémoire. 
 

La figure ci-dessous représente une liste chaînée en mémoire. Il y est parfaitement visible et compréhensible qu'un élément indiquant l'emplacement d'un autre, le stockage n'ait pas à être contigu, ni même ordonné en mémoire. La liste peut alors varier en taille et en emplacement sans se destructurer. Remarquons également que la liste chaînée présentée est circulaire simplement chaînée.

 
 
A une liste chaînée sont associée les primitives ou fonctions de service suivantes:
- "Insérer" : ajoute un élément dans la liste.
- "Supprimer" : supprime un élément de la liste.
- "La liste est-elle vide ?" : renvoie « vrai » si la liste est vide, « faux » sinon.
- "Nombre d'éléments dans la liste" : renvoie le nombre d'éléments dans la liste. 

Liste simplement chaînée

Logo définition
Liste simplement chaînée:
Une liste simplement chaînée est une liste à accès séquentiel, où chaque élément contient une valeur et une référence à l'élément suivant. Dans le cas d'une liste simplement chaînée circulaire, le dernier élément indique le premier élément de la liste comme étant son suivant.

Structure

Un élément d'une liste simplement chaînée est constitué d'une clé (la valeur de l'élément: ici nous utiliserons un  élément de type MonType) et d'une référence à l'élément suivant (un pointeur vers élément). Par convention, l'accès à une liste  simplement chaînée est simplement un pointeur vers le premier élément de cette liste.
 
Structure d'une liste chaînée en Pseudo-Code :

  1. Structure d'un élément de liste simplement chaînée:
  2. - MonType: valeur
  3. - pointeur vers l'élément suivant
  4. Fin de structure

Représentation d'une liste simplement chaînée
Représentation d'une liste simplement chaînée
 
Représentation d'une liste simplement chaînée circulaire
Représentation d'une liste simplement chaînée circulaire

Primitives

Pour l'écriture en pseudo-code des primitives, nous considérerons les accesseurs suivants:
- tete[L] qui a une liste L renvoie l'adresse de son premier élément.
- succ[x] qui a un élément x renvoie l'adresse de son successeur.
- cle[x] qui a un élément x renvoie sa valeur.
Nous considérerons également la fonction :
- isAvant(element1, element2) qui détermine la condition de tri entre deux éléments 1 et 2 dans la liste. Cette fonction est vrai lorsque element1 doit être 'avant' element2 dans la liste.

La liste est-elle vide ?

Nous avons rappelé en présentation de la structure de liste que la convention voulait qu'une liste chaînée soit identifiée par son premier élément. Une liste chaînée sera donc vide si elle ne possède aucun élément, c'est à dire si le pointeur vers la liste est NULL.
 
Primitive 'ListeVide' en Pseudo-Code :

  1. Boolean: fonction IsListeVide(liste L) :
  2. Si tete[L]=NULL
  3. la liste est vide
  4. Sinon
  5. la liste contient au moins un élément
  6. FinSi
  7. FinFonction

Notons qu'il existe une convention appelée 'liste avec sentinelle' qui place systématiquement en tête de liste un noeud factice donc la valeur est conventionnelle. Une telle liste chaînée sera vide si tete[L] est ce fameux noeud sentinelle.

Nombre d'éléments dans la liste

Si la liste chaînée est plus souple que le tableau en matière d'ajout/suppression d'éléments, l'accès à ces éléments y est nécessairement séquentiel, par opposition à l'accès direct par indice dans le cas du tableau. Il faut en effet accéder à chaque noeud pour trouver l'adresse de son successeur. Cet accès séquentiel  oblige à parcourir l'intégralité de la liste pour en compter le nombre d'élément.
La complexité d'une telle opération est donc en O(n), c'est à dire que l'algorithme nécessite un nombre d'opération exactement proportionel au nombre n d'éléments de la liste.
 
Primitive 'NbreElements' en Pseudo-Code :

  1. entier: fonction NbreElements (liste L) :
  2. entier: compt=0
  3. x :=tete[L]
  4. Si (x=NULL) #- vérifie que la liste n'est pas vide -#
  5. Retourner 0
  6. FinSi
  7. #- parcours de la liste et compage des éléments -#
  8. TantQue (succ[x] non NULL) faire
  9. x :=succ[x] #- décalage vers le suivant -#
  10. compt:=compt+1 #- comptage de l'élémen -#
  11. FinTantQue
  12. Retourner compt
  13. FinFonction

Insertion dans une liste triée

L'insertion dans une liste chaînée est un processus à bien comprendre. L'ordre des étapes d'insertion d'un élément est primordial car il garanti l'intégrité de la liste chaînée résultante et le succès de la procédure. Dans l'exemple ci-dessous, nous allons en plus considérer une insertion dans une liste triée: nous aurons donc à chercher l'emplacement où insérer l'élément.
 
Schema d'insertion dans une liste simplement chainee
Schéma d'insertion dans une liste simplement chaînée
 
Les étapes de l'insertion dans une liste simplement chaînée dépendent de ce que 'connaît' le programme, c'est à dire à quelle information il a accès. L'exécution dispose pour l'insertion de l'élément à insérer et de l'élément juste avant. Les étapes sont donc:
  1. Créer le lien 1 entre le nouvel élément et son futur suivant. L'adresse du futur suivant est accessible via le successeur de l'élément Val2 (selon le lien 3).
  2. Créer le lien 2 entre l'élément précédent et le nouvel élément. Cela a pour effet de supprimer le lien 3 désormais inutile.
Logo attention
Ordre des étapes:
L'ordre des étapes est important: si le lien 2 est crée avant le lien 1 la liste chaînée serait détruite. Pour connaitre l'adresse de l'élément Val3, le lien 3 est en effet nécessaire...
 
Primitive 'InsertionListeSimplementChainee' en Pseudo-Code :

  1. fonction InsertionListeSimplementChainee (liste: L, element nouvElement) :
  2. Si ( isAvant(nouvElement, L) ou L=NULL ) alors
  3. succ[nouvElement] := tete[L]
  4. tete[L]:=nouvElement
  5. FinSi
  6.  
  7. tmpElement := tete[L]
  8. #- parcours de la liste à la recherche de l'emplacement pour nouvElement - #
  9. TantQue (succ[tmpElement] non NULL et que isAvant(tmpElement, succ[nouvElement]) est FAUX)
  10. tmpElement := succ[tmpElement]
  11. FinTantQue
  12.  
  13. #- Insertion de nouvElement -#
  14. succ[nouvElement]:=succ[tmpElement]
  15. succ[tmpElement]:=nouvElement
  16. FinFonction

Suppression d'un élément dans une liste simplement chaînée

La suppression est l'opération inverse à l'insertion. En reprenant les notations de la figure précédente, supprimer l'élément NouvVal de la liste chaînée revient à supprimer les liens 1 et 2 pour créer le lien 3. L'ordre des étapes est alors le suivant:
  1. Création du lien 3 dont la destination est celle du lien 1 suivi du lien 2.
  2. Suppression de l'élément 
Primitive 'SupprimerElementListeSimplementChainee' en Pseudo-Code :

  1. fonction SupprimerElementListeSimplementChainee (liste: L, element Element) :
  2. Si (tete[L] = NULL) alors
  3. erreur
  4. FinSi
  5.  
  6. Si (tete[L] = Element) alors
  7. L := succ[Element]
  8. FinSi
  9.  
  10. tmpElement := tete[L]
  11. #- parcours de la liste à la recherche de l'élément - #
  12. TantQue (succ[tmpElement] non NULL et que succ[tmpElement] n'est pas Element)
  13. tmpElement := succ[tmpElement]
  14. FinTantQue
  15.  
  16. #- Suppression de nouvElement -#
  17. succ[tmpElement]:=succ[Element]
  18. supprimer(Element)
  19. FinFonction

Logo astuce
Cas de la liste simplement chaînée circulaire:
Dans le cas d'une liste simplement chaînée circulaire, le dernier élément de la liste pointe sur le premier. Il appartiendra au lecteur de vérifier sa compréhension de l'article en réécrivant les différents algorithmes afin de les adapter à la circularité.
Les principaux changements seront sur la condition de fin de boucle. Il ne s'agira plus de vérifier si le successeur d'un noeud est NULL mais plutôt s'il renvoit vers la tête de la liste.

Liste doublement chaînée

Logo définition
Liste doublement chaînée:
Une liste doublement chaînée est une liste à accès séquentiel, où chaque élément contient une valeur et une référence à son élément précédent et son élément suivant dans la liste. Dans le cas d'une liste doublement chaînée circulaire, le dernier élément indique le premier élément de la liste comme étant son suivant.

Structure

Un élément d'une liste doublement chaînée est constitué d'une clé (la valeur de l'élément: ici nous utiliserons un  élément de type MonType), d'une référence à l'élément suivant (un pointeur vers élément) mais également d'une référence arrière vers l'élément précédent. Par convention l'accès à une liste doublement chaînée est simplement un pointeur vers le premier élément de cette liste.
 
Structure d'une liste doublement chaînée en Pseudo-Code :

  1. Structure d'un élément de liste doublement chaînée:
  2. - MonType: valeur
  3. - pointeur vers l'élément suivant
  4. - pointeur vers l'élément précédent
  5. Fin de structure

Représentation d'une liste doublement chaînée
Représentation d'une liste doublement chaînée
 
Représentation d'une liste doublement chaînée circulaire
Représentation d'une liste doublement chaînée circulaire

Primitives

Dans le cas d'une liste doublement chaînée, les primitives restent identiques à ceci près que l'insertion et la suppression doivent prendre en compte le double lien entre les éléments.

Insertion dans une liste doublement chaînée

L'insertion dans une liste doublement chaînée est un processus légèrement plus complexe que l'insertion dans une liste simplement chaînée mais qui reste parfaitement logique. Il est donc bien important de comprendre pourquoi l'ordre de création/suppression des liens est important. Comme expliqué précédemment, tout tient aux informations accessibles au programme: à aucun moment il ne doit perdre l'accès aux éléments nécessaires pour le maintient de l'intégrité de la liste chaînée.
 
Schéma d'insertion dans une liste doublement chaînée
Schéma d'insertion dans une liste doublement chaînée
 
L'insertion d'un élément NouvVal entre deux éléments Val5 et Val6 d'une liste doublement chaînée s'effectue selon les étapes suivantes:
  1. Créer le lien 1 entre le nouvel élément et son futur suivant. L'adresse du futur suivant est accessible via le successeur de l'élément Val5 (selon le lien a).
  2. Créer le lien 2 entre l'élément précédent et le nouvel élément. Cela a pour effet de supprimer le lien 3 désormais inutile.
  3. Créer le lien 3 entre l'élément à insérer et l'élément précédent.
  4. Créer le lien 4 entre l'élément suivant et le nouvel élément: ceci a pour effet de supprimer le lien b.
Primitive 'InsertionListeDoublementChainee' en Pseudo-Code :

  1. fonction InsertionListeDoublementChainee (liste: L, element nouvElement) :
  2. Si ( isAvant(nouvElement, L) ou L=NULL ) alors
  3. succ[nouvElement] := tete[L]
  4. precedent[tete[L]] := nouvElement
  5. tete[L] := nouvElement
  6. FinSi
  7.  
  8. tmpElement := tete[L]
  9. #- parcours de la liste à la recherche de l'emplacement pour nouvElement - #
  10. TantQue (succ[tmpElement] non NULL et que isAvant(tmpElement, succ[nouvElement]) est FAUX)
  11. tmp[Element] := succ[tmpElement]
  12. FinTantQue
  13.  
  14. #- Insertion de nouvElement -#
  15. succ[nouvElement] := succ[tmpElement];
  16. succ[tmpElement] := nouvElement;
  17. prec[nouvElement] := tmpElement;
  18. prec[succ[nouvElement]] := nouvElement;
  19. FinFonction

Suppression d'un élément dans une liste doublement chaînée

La suppression d'un élément dans une liste doublement chaînée suit le processus inverse à celui de l'insertion :
  1. Créer le lien b ce qui a pour effet de détruire le lien 4.
  2. Créer le lien a ce qui a pour effet de détruire le lien 2.

Pour aller plus loin...

En pratique il est d'usage courant de créer un élément appelé sentinelle qui sera systématiquement placé en tête de liste. Cet élément factice permettra de faciliter la manipulation de la liste et pourra éventuellement vous permettre de distinguer la notion de liste de celle d'élément en créant le type "liste" comme pointeur sur sentinelle.
 
Nous laissons au lecteur le soin d'adapter les algorithmes pour le cas de listes avec sentinelles. N'hésitez pas à nous envoyer vos algorithmes et/ou vos questions en commentaires à cet article.
Votre note : Aucun(e) Moyenne : 5 (3 votes)

Commentaires

Utilisateur non enregistré

svp qui peut m aidez et donnez la solusion de ce probleme et voila le Sujet : Pour jouer à AM-STRAM-GRAM, n enfants forment une ronde, choisissent l’un d’eux comme le premier, commencent à compter à partir de lui et décident que le kième enfant doit quitter la ronde, puis le 2kième, et ainsi de suite.
En simulant la ronde par une liste circulaire, écrire un programme qui donne la liste des enfants dans l’ordre où ils sont sortis de la ronde :
1/ pour une représentation contiguë,
2/ pour une représentation chaînée accessible par pointeur,
3/ pour une représentation chaînée accessible par maillon.
je vous remercier :))

Portrait de Miroslav
Bonjour,
 
Pour simuler la ronde par liste circulaire, c'est très simple: reprenez l'exemple de l'article où un maillon est un enfant. Vous pouvez par exemple représenter cet enfant par une classe ou par une structure, suivant les critères de votre devoir et/ou du langage utilisé.
 
Liste circulaire signifie que le dernier élément de la liste pointera vers le premier.
 
Pour ce qui est de l'énoncé, je pense que vous devriez demander quelque précisions à votre professeur:
- pour moi une liste contiguë n'est pas une liste chaînée mais un simple tableau (cf notre l'article sur les tableaux). Il vous faudra alors gérer la suppression d'un élément, le redimensionnement du tableau etc..
- pour ce qui est de la liste chaînée accessible par pointeur, c'est exactement comme dans l'article: vous commencez la chaîne à un endroit choisi, puis parcourez k élément, et supprimez le k-ième de la liste circulaire (en stockant son indice dans une structure réponse). Et recommencez le tout dans une boucle "tantque" il reste des enfants dans la ronde.
- pour la troisième question, je la comprend pas: accessible par maillon ? Un maillon de la chaîne est un élément de la chaîne, accessible via un pointeur de l'élément précédent. demandez donc quelques précisions sur ce qui est attendu ici. Est-ce une surcharge d'un opérateur [] (cas du C++) pour accéder de manière plus transparente au k-ième élément de la liste ?
 
Miro.
 

To the engineer, the world is a toy box full of suboptimized and feature-poor toys. (Adams Scott)
www.axiomcafe.fr

Utilisateur non enregistré

Viagra No Prescription Required Viagra Prix Pharmacie Paris Cephalexin Sulfameth Trimethoprim Seborrheic Dermatitis generic levitra on line Kamagra Pas Cher 100 Mg Cilalis For Cheap