- Définition
Définition 6.1. Une liste est une table d'association à clé unique telle que
- le nombre d'éléments de la table (dimension ou taille) est variable,
- l'accès aux éléments s'effectue indirectement par le contenu de la clé qui le localise appelée pointeur.
La complexité de l'accès à un élément par son pointeur est O(1).
Si p est un pointeur vers un élément alors contenu(p) est l'élément lui-même.
Un pointeur qui n'adresse aucun élément a pour valeur NIL.
On écrit en EXALGO pour déclarer un pointeur
nom_pointeur=^type_predefini;
On écrit en EXALGO pour déclarer une liste
type_liste=liste de type_predefini;
La manipulation des éléments de la liste dépend des fonctions définies comme s'exécutant en temps O(1).
- Liste simplement chainée
Définition 6.2. Une liste est dite
simplement chainée si les opérations suivantes s'effectuent en O(1).
- accès
fonction premier(val L:type_liste):^type_predefini;
fonction suivant(val L:type_liste;
val P:^type_predefini):^type_predefini;
fonction listeVide(val L:type_liste):booléen;
- modification
fonction créer liste(ref L:type_liste):vide;
fonction insérerAprès(val x:type_prédéfini;
ref L:type_liste;
P:^type_predefini):vide;
fonction insérerEnTete(val x:type_prédéfini;
ref L:type_liste):vide;
fonction supprimerAprès(ref L:type_liste;val P:^type_predefini):vide;
fonction supprimerEnTete(ref L:type_liste):vide;
On écrira en EXALGO listeSC pour préciser qu'il s'agit d'une liste simplement chainée.
Test de fin de liste
fonction estDernier(ref L:listeSC de type_prédéfini;
ref P:^type_prédéfini):booléen;
début
retourner(suivant(L,P)=NIL)
fin
finfonction
Chercher un élément dans une liste
fonction chercher(ref L:listeSC de type_prédéfini;
ref E:type_prédéfini):^type_predefini;
début
var p:^type_prédéfini;
début
si listeVide(L) alors
retourner(NIL)
sinon
p=premier(L);
tant que non(estDernier(L,p)) et (contenu(p)!=e) faire
p=suivant(L,p);
fintantque
si (contenu(p)!=e) alors
retourner(NIL)
sinon
retourner(p)
finsi
finsi
fin
finfonction
Complexité:
- minimum : O(1)
- maximum : O(n)
Trouver le dernier élément
fonction trouverDernier(ref L:listeSC de type_prédéfini):^type_predefini;
var p:^type_prédéfini;
début
si listeVide(L) alors
retourner(NIL)
sinon
p=premier(L);
tant que non(estDernier(L,P)) faire
p=suivant(L,p);
fintantque
retourner(p)
finsi
fin
finfonction
Complexité: O(n).
- Liste doublement chainée
Définition 6.3. Une liste doublement chainée est une liste pour laquelle les opérations en temps O(1) sont celles des listes simplement chainées auxquelles on ajoute les fonctions d'accès
fonction dernier(val L:type_liste):^type_predefini;
fonction précédent(val L:type_liste;
val P:^type_predefini):^type_predefini;
On écrira en EXALGO listeDC pour préciser qu'il s'agit d'une liste doublement chainée.
Supprimer un élément
fonction supprimer(ref L:listeDC de type_predefini;
val e: type_prédéfini):booléen;
var p,prec,suiv:^type_prédéfini;
début
p=chercher(L,e);
si p==NIL alors
retourner(FAUX)
sinon
si estPremier(L,p) alors
supprimerEnTete(L)
sinon
prec=précédent(L,p);
supprimerApres(L,prec);
finsi
retourner(VRAI)
finsi
fin
finfonction
Complexité
- minimum : O(1)
- maximum : O(n)
- Quelques algorithmes
Taille
fonction taille(val L:type_liste):entier;
var p:^type_prédéfini;
var t:entier;
début
si listeVide(L) alors
retourner(0)
sinon
retourner(1+taille(suivant(L,premier(L))))
finsi
fin
finfonction
Complexité: O(n).
Insérer dans une liste triée
On suppose la liste triée doublement chainée dans l'ordre croissant
fonction insertionTrie(ref L:listeDC de type_prédéfini;
val e: type_prédéfini):vide;
var p:^type_prédéfini;
début
si listeVide(L) alors
insererEnTete(e,L)
sinon
si contenu(premier(L))>e alors
insererEnTete(e,L)
sinon
insererTrie(suivant(L,premier(L)),e)
finsi
finsi
fin
finfonction
Complexité moyenne: O(n).