Algorithme - Les listes contiguës et chaînées

Pourquoi les listes ?

On trouve souvent les listes dans la vie quotidienne telles que:
  • Individus dans une salle d'attente.
  • Etudiants inscrits dans une spécialité.
  • Voitures attendent le feu rouge.
  • etc.
Le but est de représenter ces exemples de la vie réelle et les traiter en informatique.

Quelles sont les caractéristiques d'une liste ?

  • Ils sont traitées d'une manière séquentielles.
  • Délimitée par les deux extrémités <tête> et <queue>.
  • Il est possible d'ajouter ou supprimer des éléments.
  • Structure dynamique (la taille varie).
Représentation

1 - Représentation contiguë

On a vu qu'on peut représenter une liste avec un tableau T[1..max] mais sa structure est statique (sa taille est fixe au moment ou on définit la dans la déclaration).



type liste : Article
                 {
                      T: tableau[1..lmax] de élément
                       longueur: 0..lmax
                  }

Les opérations les plus importantes


      Les avantages

      • Accès directe.
      • Suppression et insertion en fin de liste.
      • Implémentation facile.

      Inconvénients

      • Il faut savoir modifier la longueur.
      • les suppressions et les insertions impliquent des décalages.

      2- Représentation chaînée 

      Elle est composée d'une suite de maillon (bloc) et chaque maillon est constitué de deux champs:
      • Un champ élément.
      • Un champ adresse qui pointe vers l'élément suivant.

      L: pointeur sur le premier maillon.
      Une liste chaînée vide est représentée par L=null.

      type ptr: pointeur sur maillon
      type maillon: article
                            {
                                 val;élément
                                 lien: ptr
                             }
      type listechaînée : maillon
      var L: listechaînée

      Les opérations les plus importantes

      • Le parcours.
        • Procédure parcours(L:liste)
          Début
             pp := L.lien // tête de L
             tantque pp != null
             faire
                 traiter(L.T[i])
                 pp := *pp.lien
             finfaire
           Fin


        Avantages

        • Parcours séquentiel.
        • Suppression d'un maillon.
        • Insertion d'un maillon.

        Inconvénients

        • Accès indirecte à un élément, il faut parcourir i-1 maillons pour atteindre le ième maillon.
        • Perte de place mémoire pour les liens.