Section courante

A propos

Section administrative du site

Introduction

La «liste symétrique», aussi appelée la «liste doublement chaînées», une liste d'élément relié chacun les autres à l'aide d'un pointeur vers l'élément précédent ou vers l'élément suivant. Le premier élément de la liste est appelé la tête et le dernier élément de la liste est appelé la queue. Chaque nouvelle élément est ajouté à partir de la mémoire dynamique (dans la mémoire de tas).

Avantage

Algorithme

Voici les algorithmes très simplifiés permettant d'ajouter et de supprimer des éléments dans la liste symétrique. Tout d'abord, la création d'une nouvelle liste symétrique avec un élément au total :

MODULE NouvelleElement(tete,element)
   NOUVEAU BLOC DYNAMIQUE tete
   (teteinfo) ← element
   (teteprécédant) ← NIL
   (tetesuivant) ← NIL

L'algorithme suivant ajoute un élément avant la tête, et devient donc la nouvelle tête. Un peu donc le considérer comme une insertion au début de la liste.

MODULE InsereDebut(tete,element)
   NOUVEAU BLOC DYNAMIQUE P
   (P→info) ← element
   (P→précédant) ← NIL
   (P→suivant) ← tete
   (tete→précédant) ← P
   teteP

L'algorithme suivant ajoute un élément lorsqu'il y au moins élément avant lui et un élément après lui :

MODULE AjoutMilieu(tete, element)
   P1tete
   TANT QUE P1P FAIRE
      P1 ← (P1suivant)
   FIN TANT QUE
   NOUVEAU BLOC DYNAMIQUE P2
   (P2info) ← element
   (P2suivant) ← P
   (P2précédant) ← Pprécédant
   ((Pprécédant)→suivant) ← P2
   (Pprécédant) ← P2

L'algorithme suivant ajoute un élément à la fin complètement de la liste s'il y a des élément existant :

MODULE InsereFin(tete, element)
   Ptete
   TANT QUE P→suivant ≠ NIL FAIRE
      PP→suivant
   FIN TANT QUE
   NOUVEAU BLOC DYNAMIQUE P1
   (P1→info) ← element
   (P1précédant) ← P
   (P1suivant) ← NIL
   (Psuivant) ← P1

L'algorithme suivant permet de supprimer l'élément de la tête et le deuxième élément devient le premier :

MODULE SupprimePremierElement(tete)
   Ptete
   SI tete ≠ NIL ALORS
      tete ← (tetesuivant)
      (teteprécédant) ← NIL
      LIBERE BLOC DYNAMIQUE P
   FIN SI

L'algorithme suivant permet de supprimer un élément dans le milieu de la liste :

MODULE SupprimeMilieu(tete)
   P1tete
   TANT QUE (P1suivant) ≠ P FAIRE
      P1 ← (P1suivant)
   FIN TANT QUE
   (P1suivant) ← (P→suivant)
   LIBERE BLOC DYNAMIQUE P

L'algorithme suivant permet de supprimer le dernier élément de la liste :

MODULE SupprimeQueue(tete)
   P1tete
   TANT QUE (P1suivant) ≠ NIL FAIRE
      P1 ← (P1suivant)
   FIN TANT QUE
   ((P1précédant)→suivant) ← NIL
   LIBERE BLOC DYNAMIQUE P1


Dernière mise à jour : Jeudi, le 6 avril 2017