Bonjour voila j'ai du mal a comprendre les listes chainées... Comment peut on la parcourir itérativement ? ou récursivement ? Cela m'énerve un peu, je préfère les tableaux mais je voudrais bien comprendre quand même les listes chainées !!
Bonjour voila j'ai du mal a comprendre les listes chainées... Comment peut on la parcourir itérativement ? ou récursivement ? Cela m'énerve un peu, je préfère les tableaux mais je voudrais bien comprendre quand même les listes chainées !!
bah une mini-recherche ici t'aurais amene a ce fil :
http://www.developpez.net/forums/sho...d.php?t=495214
C'est une liste où chaque élément, quelle que soit sa position en mémoire, connait l'adresse de l'élément qui le suit de façon logique
En général c'est effectivement plus facile. Mais la liste chainée possède l'avantage inégalable de pouvoir insérer n'importe quel nouvel élément à n'importe quelle place. L'élément qui s'insère récupère l'adresse du suivant et l'élément placé avant récupère l'adresse de l'élément qui s'insère et c'est tout. Avec un tableau faut tout décaler...
Mon Tutoriel sur la programmation «Python»
Mon Tutoriel sur la programmation «Shell»
Sinon il y en a pleins d'autres. N'oubliez pas non plus les différentes faq disponibles sur ce site
Et on poste ses codes entre balises [code] et [/code]
Euh, dites-moi si je me trompe mais une liste chainée prend a priori plus de place mémoire qu'un tableau dans la mesure où il faut, pour chaque élément, stocker en plus un pointeur vers l'élément suivant et/ou précédent. Par contre, quand le nombre d'éléments varie beaucoup, c'est plus lourd à gérer pour les tableaux car on peut être amené à faire des realloc
Et comme on veut limiter ceux-ci, on alloue plus, ce qui a un cout en memoire. En fait, de ce point de vue l'avantage va a l'un ou a l'autre suivant la strategie de reallocation, la taille des valeurs mises dans la liste et la presence ou non d'effacements.
Un facteur qui peut etre a l'avantage du tableau, c'est que le fait qu'il soit contigu donne generalement une meilleure utilisation des caches a divers niveaux.
Et, je dirais que pour certaines applications les allocations dynamiques de mémoire sont pénalisantes en perf. Donc si on a besoin d'implémenter les listes chainées, on est bon pour implémenter un mécanisme d'attribution de mémoire pré-alouée.
Partager