Liste chainées
Fermé
didy_gwatinik
Messages postés
352
Date d'inscription
samedi 17 novembre 2007
Statut
Membre
Dernière intervention
30 mars 2010
-
25 oct. 2008 à 13:36
Marco la baraque Messages postés 996 Date d'inscription vendredi 9 mai 2008 Statut Contributeur Dernière intervention 5 novembre 2009 - 25 oct. 2008 à 21:00
Marco la baraque Messages postés 996 Date d'inscription vendredi 9 mai 2008 Statut Contributeur Dernière intervention 5 novembre 2009 - 25 oct. 2008 à 21:00
A voir également:
- Liste chainées
- Liste déroulante excel - Guide
- Liste déroulante en cascade - Guide
- Liste groupe whatsapp - Guide
- Liste site streaming illégal - Accueil - Services en ligne
- Liste de diffusion whatsapp - Guide
1 réponse
Marco la baraque
Messages postés
996
Date d'inscription
vendredi 9 mai 2008
Statut
Contributeur
Dernière intervention
5 novembre 2009
329
25 oct. 2008 à 21:00
25 oct. 2008 à 21:00
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,