Listes chaînées
Caractéristiques
* Liste "simplement" chaînée
* Chaînage entre eux des éléments à stocker
* Chaque élément connaît son successeur
* Structure de données flexible
* Pas de limite de capacité (allocation dynamique)
* Ajout / suppression d'un élément très rapide
* Contrairement au tableau
* Accès direct difficile
* Pas d'accès par indice
* Il faut parcourir pour trouver un élément
* Liste "doublement" chaînée
* Chaque élément connaît son prédécesseur et son successeur
Structure (1/2)
* Une liste chaînée est composée de maillons
* Un maillon = élément stocké + pointeurs suivant/précédent
class Maillon {
public:
Element element;
Maillon * suivant;
Maillon * precedent;
};
* La liste référence seulement le premier et le dernier maillon
class Liste {
private:
Maillon * tete;
Maillon * fin;
...
};
Structure (2/2)
Ajouter un élément
* Situation 1: en tête de liste
* Cas liste vide
* Cas liste non vide
* Situation 2: en fin de liste
* Cas liste vide
* Cas liste non vide
* Situation 3: n'importe où dans la liste
* Il faut alors indiquer la position de l'insertion
* C'est-à-dire le maillon avant lequel faire l'insertion
Ajout en tête (1/2)
* Créer un maillon ==> m
* Si liste vide
1) liste.tete = m;
2) liste.fin = m;
Ajout en tête (2/2)
* Si liste non vide
1) m?suivant = liste.tete;
2) liste.tete?precedent = m;
3) liste.tete = m;
Ajout en fin
* Si liste vide ==> idem ajout en tête
* Si liste non vide
1) m?precedent = liste.fin;
2) liste.fin?suivant = m;
3) liste.fin = m;
Ajout n'importe où (1/2)
* Il faut connaître la position d'ajout ==> maillon p
* On choisit d'ajouter juste avant le maillon p
* Si p = 0 ==> ajout en fin
* Si p?precedent = 0 ==> ajout en tête
* Sinon
1) m?precedent = p?precedent;
2) m?suivant = p;
3) p?precedent?suivant = m;
4) p?precedent = m;
Ajout n'importe où (2/2)
Parcourir une liste
* Principe
* Pointer sur le maillon de tête
* Avancer en utilisant le pointeur sur le suivant
* Tant que ce pointeur n'est pas nul
* Algorithme
m = liste.tete;
tant que (m ? 0) faire
TRAITEMENT(m);
m = m?suivant;
fin tant que
Retirer un élément
* Retrait en tête
1) m = liste.tete;
2) liste.tete = m?suivant;
3) liste.tete?precedent = 0;
* Retrait en fin
1) m = liste.fin;
2) liste.fin = m?precedent;
3) liste.fin?suivant = 0;
* Retrait de n'importe quel maillon m
1) m?suivant?precedent = m?precedent;
2) m?precedent?suivant = m?suivant;
* Penser...
* A libérer la mémoire du maillon m
* Aux cas particuliers (liste vide ou avec un seul élément)