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

Un livre de Wikilivres.
Contenu supprimé Contenu ajouté
JulienCo (discussion | contributions)
m Ajout du sommaire + lissage du premier paragraphe
Ligne 1 : Ligne 1 :
{{Programmation Algorithmique}}
== 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''
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'''
ELEMENT : '''ENREGISTREMENT'''

Version du 10 septembre 2013 à 12:46


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