Programmation Algorithmique/Listes simplement chaînées
Un livre de Wikibooks.
Sections |
[modifier] Introduction
à étoffer, clarrifier, reformuler, etc...
Une liste simplement chaînée est une structure de données pouvent 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
[modifier] Recherche dans une liste chaînée
[modifier] Recherche d'un élément ayant une clée 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
[modifier] 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
[modifier] 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
[modifier] Insertion
[modifier] 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
[modifier] 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
[modifier] 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 := ELEMENT
SINON
ELEMENT_PRECEDENT.SUIVANT := NOUVEL_ELEMENT
NOUVEL_ELEMENT.SUIVANT := ELEMENT
FIN SI
FIN FONCTION
[modifier] Suppression
[modifier] 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
