Liste chainées
didy_gwatinik
Messages postés
352
Date d'inscription
Statut
Membre
Dernière intervention
-
Marco la baraque Messages postés 996 Date d'inscription Statut Contributeur Dernière intervention -
Marco la baraque Messages postés 996 Date d'inscription Statut Contributeur Dernière intervention -
Bonjour,
Est-il possible de parcourir un liste chainée simple à l'envers pour afficher les saisies dans l'ordre inverse? Je vosi pas trop comment je pourrai faire?
Sinon je pense à faire une copie de ma liste chainée et de supprimer au fur et à mesure chaue partie de la liste jusqu'à ce que j'arrive au début, mais c'est un peu "tirer par les cheveux" d'en arriver jusque là, non? et je pense que j'aurai encore le même soucis pour arriver au pointeur précédent.
Est-il possible de parcourir un liste chainée simple à l'envers pour afficher les saisies dans l'ordre inverse? Je vosi pas trop comment je pourrai faire?
Sinon je pense à faire une copie de ma liste chainée et de supprimer au fur et à mesure chaue partie de la liste jusqu'à ce que j'arrive au début, mais c'est un peu "tirer par les cheveux" d'en arriver jusque là, non? et je pense que j'aurai encore le même soucis pour arriver au pointeur précédent.
A voir également:
- Liste chainées
- Liste déroulante excel - Guide
- Liste déroulante en cascade - Guide
- Liste code ascii - Guide
- Site dangereux liste - Guide
- Liste site streaming illégal - Accueil - Services en ligne
1 réponse
Bonsoir,
Le principe de la liste chainée, c'est d'avoir que chaque maillon a deux attributs :
- l'élément qu'il contient (les données)
- un pointeur vers l'élément suivant de la chaîne
Autrement dit, une liste chainée ne peut être parcourue que dans un seul sens.
Pour parcourir une liste chainée en sens inverse (autrement dit, pour trouver l'élément précédent chaque élément), l'algorithme a une complexité en O(n²).
L'idéal dans ton cas est donc d'utiliser une liste doublement chainée, qui te permet un parcours dans les deux sens (en gardant une complexité en O(n) pour le parcours). Pour cela, chaque maillon a trois attributs :
- l'élément qu'il contient (les données)
- un pointeur vers l'élément suivant de la chaine
- un pointeur vers l'élément précédent de la chaine.
Par contre il va sans doute te falloir implémenter cette structure car elle n'existe pas dans la plupart des langages de programmation (quoiqu'en cherchant bien peut-être que tu peux la trouver dans des bibliothèques externes).
Bien cordialement,
Le principe de la liste chainée, c'est d'avoir que chaque maillon a deux attributs :
- l'élément qu'il contient (les données)
- un pointeur vers l'élément suivant de la chaîne
Autrement dit, une liste chainée ne peut être parcourue que dans un seul sens.
Pour parcourir une liste chainée en sens inverse (autrement dit, pour trouver l'élément précédent chaque élément), l'algorithme a une complexité en O(n²).
L'idéal dans ton cas est donc d'utiliser une liste doublement chainée, qui te permet un parcours dans les deux sens (en gardant une complexité en O(n) pour le parcours). Pour cela, chaque maillon a trois attributs :
- l'élément qu'il contient (les données)
- un pointeur vers l'élément suivant de la chaine
- un pointeur vers l'élément précédent de la chaine.
Par contre il va sans doute te falloir implémenter cette structure car elle n'existe pas dans la plupart des langages de programmation (quoiqu'en cherchant bien peut-être que tu peux la trouver dans des bibliothèques externes).
Bien cordialement,