Programmation algorithmique/Listes simplement chaînées

à étoffer, clarifier, reformuler, etc...

Programmation algorithmique

• Introduction
• Nombre d'opérations optimal
• Mathématiques simples
• Tableaux : parcours, recherches
• Tris de tableaux
• Structures de données
  • Listes simplement chaînées
  • Listes doublement chaînées
  • Arbres

Une liste simplement chaînée est une structure de données pouvant contenir plusieurs éléments. Chaque élément possède un pointeur vers l'élément suivant. La liste est un pointeur vers le premier élément de la liste. Le dernier élément pointe vers une adresse spécifique (notée NIL) pour signifier la fin de la liste.

La clef d'un élément est d'un type quelconque. On peut ajouter des informations utiles aux éléments.

ELEMENT : ENREGISTREMENT
   CLEF
   SUIVANT : ELEMENT
FIN ENREGISTREMENT

LISTE : ENREGISTREMENT
   TETE : ELEMENT
FIN ENREGISTREMENT

Recherche dans une liste chaînée

Recherche d'un élément ayant une clé CLEF dans une liste

Complexité : O(N)

FONCTION SIMPLE_LISTE:RECHERCHER(LISTE, CLEF)
   ELEMENT = LISTE.TETE
   TANT QUE ELEMENT <> NIL ET ELEMENT.CLEF <> CLEF
      ELEMENT = ELEMENT.SUIVANT
   FIN TANT QUE'
   RETOURNER ELEMENT
FIN FONCTION

Recherche de l'élément suivant un élément ELEMENT dans une liste

Complexité : O(1)

FONCTION SIMPLE_LISTE:SUIVANT(LISTE, ELEMENT)
   RETOURNER ELEMENT.SUIVANT
FIN FONCTION

Recherche de l'élément précédent un élément ELEMENT dans une liste

Complexité : O(N)

FONCTION SIMPLE_LISTE:PRECEDENT(LISTE, ELEMENT)
   ELEMENT_COURANT := LISTE.TETE
   TANT QUE ELEMENT_COURANT != NIL ET ELEMENT_COURANT.SUIVANT != ELEMENT
      ELEMENT_COURANT := ELEMENT_COURANT.SUIVANT
   FIN TANT QUE
   RETOURNER ELEMENT_COURANT
FIN FONCTION

Itération contre récursion

De nombreux problèmes sur les listes chaînées peuvent se traiter aussi bien de façon itérative (à l'aide de boucles) que de façon récursive (à l'aide d'appels récursifs de fonctions). La récursion (ou récursivité) se rattache plus à l'algorithmique fonctionnelle qu'à l'algorithmique impérative. Toutefois, les langages impératifs offrent souvent la possibilité de programmer par récursion, alors il est intéressant de choisir entre itération et récursion en toute connaissance de cause.

Voici donc un exemple d'algorithme utilisant la récursion, il s'agit de rechercher un élément dans une liste, comme plus haut.

Recherche d'un élément ayant une clé CLEF dans une liste (version récursive)

Complexité en temps: O(N). Complexité en espace : O(N) ou O(1) selon le support d'exécution.

FONTION SIMPLE_LISTE: RECHERCHE(LISTE,CLEF)
  RETOURNER RECH_REC(LISTE.TETE)
FIN FONCTION

FONCTION SIMPLE_LISTE: RECH_REC(ELEMENT, CLEF)
  SI ELEMENT =  NIL OU ELEMENT.CLEF = CLEF 
    ALORS RETOURNER ELEMENT
    SINON RETOURNER RECH_REC(ELEMENT.SUIVANT)
FIN FONCTION

On notera que dans cet exemple on ne trouve ni affectation (ou assignation), ni séquence (succession inconditionnelle de deux instructions). Il s'agit donc bien d'un algorithme fonctionnel.

Selon le langage et le compilateur utilisé pour réaliser cet algorithme, les appels récursifs successifs seront stockés ou non en mémoire. On parle de pile d'appels récursifs. Dans le cas où le support d'exécution (c'est à dire l'interprète ou le code compilé) utilise une pile d'appels récursifs pour exécuter la fonction RECH_REC, la complexité en espace sera O(N), car pour chaque élément de la liste, on devra stocker en mémoire, sur la pile, l'information sur l'appel en cours. Dans le second cas, où le compilateur est capable de générer du code qui utilise un espace limité sur la pile, la complexité en espace sera O(1), comme pour la version itérative. À titre d'exemple, le compilateur GCC est capable de compiler certaines fonctions récursives écrites en C pour qu'elles utilisent un espace constant sur la pile, alors que l'interprète standard du langage Python empile systématiquement les appels récursifs.

Insertion

Insertion d'un élément NOUVEL_ELEMENT en début de liste

Complexité O(1)

FONCTION SIMPLE_LISTE:INSERER_DEVANT(LISTE, NOUVEL_ELEMENT)
    ELEMENT := LISTE.TETE
    LISTE.TETE := NOUVEL_ELEMENT
    NOUVEL_ELEMENT.SUIVANT = ELEMENT
FIN FONCTION

Insertion d'un élément NOUVEL_ELEMENT dans une liste après un élément ELEMENT

Complexité : O(1)

FONCTION SIMPLE_LISTE:INSERER_APRES(LISTE, ELEMENT, NOUVEL_ELEMENT)
   SI LISTE.TETE = NIL ALORS
       LISTE.TETE := NOUVEL_ELEMENT
       NOUVEL_ELEMENT.SUIVANT = NIL
   SINON
       NOUVEL_ELEMENT.SUIVANT := ELEMENT.SUIVANT
       ELEMENT.SUIVANT := NOUVEL_ELEMENT
   FIN SI
FIN FONCTION
  

Insertion d'un élément NOUVEL_ELEMENT dans une liste avant un élément ELEMENT

Complexité : O(N)

FONCTION SIMPLE_LISTE:INSERER_AVANT(LISTE, ELEMENT, NOUVEL_ELEMENT)
   ELEMENT_PRECEDENT := SIMPLE_LISTE:PRECEDENT(LISTE, ELEMENT)
   SI ELEMENT_PRECEDENT = NIL ALORS
       LISTE.TETE := NOUVEL_ELEMENT
       NOUVEL_ELEMENT.SUIVANT := ELEMENT
   SINON
       ELEMENT_PRECEDENT.SUIVANT := NOUVEL_ELEMENT
       NOUVEL_ELEMENT.SUIVANT := ELEMENT
   FIN SI
FIN FONCTION

Suppression

Suppression d'un élément ELEMENT_SUPPRIME d'une liste

Complexité : O(N)

FONCTION SIMPLE_LISTE:SUPPRIMER(LISTE, ELEMENT_SUPPRIME)
   ELEMENT_PRECEDENT := SIMPLE_LISTE:PRECEDENT(LISTE, ELEMENT_SUPPRIME)
   SI ELEMENT_PRECEDENT != NIL ALORS
      ELEMENT_PRECEDENT.SUIVANT := ELEMENT_SUPPRIME.SUIVANT
   SINON
      LISTE.TETE := ELEMENT_SUPPRIME.SUIVANT
   FIN SI
FIN FONCTION