« Programmation algorithmique/Listes doublement chaînées » : différence entre les versions

Un livre de Wikilivres.
Contenu supprimé Contenu ajouté
Création : == Introduction == ''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'e...
(Aucune différence)

Version du 29 mars 2007 à 21:28

Introduction

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 utilise un pointeur supplémentaire par élément. Il faut donc maintenir cohérent 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ée 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 = ELEMENT
   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