- 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).