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
- La taille des éléments peut avoir des tailles de données variables.
- Consomme moins de mémoire qu'un tableau à taille fixe.
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 (tete→info) ← element (tete→précédant) ← NIL (tete→suivant) ← 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 tete ← P |
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) P1 ← tete TANT QUE P1 ≠ P FAIRE P1 ← (P1→suivant) FIN TANT QUE NOUVEAU BLOC DYNAMIQUE P2 (P2→info) ← element (P2→suivant) ← P (P2→précédant) ← P→précédant ((P→précédant)→suivant) ← P2 (P→pré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) P ← tete TANT QUE P→suivant ≠ NIL FAIRE P ← P→suivant FIN TANT QUE NOUVEAU BLOC DYNAMIQUE P1 (P1→info) ← element (P1→précédant) ← P (P1→suivant) ← NIL (P→suivant) ← 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) P ← tete SI tete ≠ NIL ALORS tete ← (tete→suivant) (tete→pré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) P1 ← tete TANT QUE (P1→suivant) ≠ P FAIRE P1 ← (P1→suivant) FIN TANT QUE (P1→suivant) ← (P→suivant) LIBERE BLOC DYNAMIQUE P |
L'algorithme suivant permet de supprimer le dernier élément de la liste :
|
MODULE SupprimeQueue(tete) P1 ← tete TANT QUE (P1→suivant) ≠ NIL FAIRE P1 ← (P1→suivant) FIN TANT QUE ((P1→précédant)→suivant) ← NIL LIBERE BLOC DYNAMIQUE P1 |