Programmation algorithmique/Listes doublement chaînées

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 doublement chaînée permet de gagner en complexité sur l'insertion et la suppression par rapport à la liste simplement chaînée, en plus de permettre un parcours des elements à l'envers. Mais on utilise un pointeur supplémentaire par élément. Il faut donc maintenir cohérentes deux fois plus de variables que dans une liste simplement chaînée.

ELEMENT : ENREGISTREMENT
   CLEF
   SUIVANT   : ELEMENT
   PRECEDENT : ELEMENT
FIN ENREGISTREMENT

LISTE : ENREGISTREMENT
   TETE  : ELEMENT
   QUEUE : ELEMENT
FIN ENREGISTREMENT

Recherche dans une liste chaînée

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

(Idem listes simplement chaînées) Complexité : O(N)

FONCTION DOUBLE_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

(Idem listes simplement chaînées) Complexité : O(1)

FONCTION DOUBLE_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(1)

FONCTION DOUBLE_LISTE:PRECEDENT(LISTE, ELEMENT)
   RETOURNER ELEMENT.PRECEDENT
FIN FONCTION

Insertion

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

Complexité O(1)

FONCTION DOUBLE_LISTE:INSERER_DEVANT(LISTE, NOUVEL_ELEMENT)
   ELEMENT := LISTE.TETE
   LISTE.TETE := NOUVEL_ELEMENT
   NOUVEL_ELEMENT.SUIVANT = ELEMENT
   NOUVEL_ELEMENT.PRECEDENT = NIL
   SI LISTE.QUEUE = NIL ALORS
      LISTE.QUEUE := NOUVEL_ELEMENT
   FIN SI
FIN FONCTION

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

Complexité : O(1)

FONCTION DOUBLE_LISTE:INSERER_APRES(LISTE, ELEMENT, NOUVEL_ELEMENT)
   SI LISTE.TETE = NIL ALORS
       LISTE.TETE := NOUVEL_ELEMENT
       LISTE.QUEUE := NOUVEL_ELEMENT
       NOUVEL_ELEMENT.PRECEDENT := NIL
       NOUVEL_ELEMENT.SUIVANT = NIL
   SINON
       NOUVEL_ELEMENT.PRECEDENT := ELEMENT
       NOUVEL_ELEMENT.SUIVANT := ELEMENT.SUIVANT
       SI ELEMENT.SUIVANT != NIL ALORS
         ELEMENT.SUIVANT.PRECEDENT := NOUVEL_ELEMENT
       SINON
         LISTE.QUEUE := NOUVEL_ELEMENT
       FIN SI
       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(1)

FONCTION DOUBLE_LISTE:INSERER_AVANT(LISTE, ELEMENT, NOUVEL_ELEMENT)
   SI LISTE.TETE = NIL ALORS
       LISTE.TETE := NOUVEL_ELEMENT
       LISTE.QUEUE := NOUVEL_ELEMENT
       NOUVEL_ELEMENT.SUIVANT := NIL
       NOUVEL_ELEMENT.PRECEDENT := NIL
   SINON
       NOUVEL_ELEMENT.SUIVANT := ELEMENT
       NOUVEL_ELEMENT.PRECEDENT := ELEMENT.PRECEDENT
       SI ELEMENT.PRECEDENT != NIL ALORS
          ELEMENT.PRECEDENT.SUIVANT := NOUVEL_ELEMENT
       SINON
          LISTE.TETE := NOUVEL_ELEMENT
       FIN SI
       ELEMENT.PRECEDENT := NOUVEL_ELEMENT
   FIN SI
FIN FONCTION

Suppression

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

Complexité : O(1)

FONCTION DOUBLE_LISTE:SUPPRIMER(LISTE, ELEMENT_SUPPRIME)
   SI ELEMENT_SUPPRIME.PRECEDENT != NULL ALORS
      ELEMENT_SUPPRIME.PRECEDENT.SUIVANT := ELEMENT_SUPPRIME.SUIVANT
   SINON
      LISTE.TETE := ELEMENT_SUPPRIME.SUIVANT
   FIN SI

   SI ELEMENT_SUPPRIME.SUIVANT != NIL ALORS
      ELEMENT_SUPPRIME.SUIVANT.PRECEDENT := ELEMENT_SUPPRIME.PRECEDENT
   SINON
      LISTE.QUEUE := ELEMENT_SUPPRIME.PRECEDENT
   FIN SI
FIN FONCTION