Discussion :

[Devilju69]

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 !!

[souviron34]

bah une mini-recherche ici t'aurais amene a ce fil :

http://www.developpez.net/forums/sho...d.php?t=495214

[Sve@r]

Bonjour voila j'ai du mal a comprendre les listes chainées...

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

je préfère les tableaux

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...

[souviron34]

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.

ET de prendre beaucoup moins de place memoire lorsuqe l'on doit faire varier le nombre d'elements grandement....

[corentin59]

ET de prendre beaucoup moins de place memoire lorsuqe l'on doit faire varier le nombre d'elements grandement....

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

[Jean-Marc.Bourguet]

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.

[valefor]

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.

[souviron34]

je mentionnais simplement parce que cela me semble être plus l'avantage déterminant que le fait d'insérer à n'importe quel endroit...


J'ai eu à manipuler des variations de 0 à 300 000+ éléments en continu 7j/7, et avec des tableaux et des reallocs, ça finissait par crasher...

Mais en fait c'est Jean-Marc qui a raison... c'est surtout dépendant de quel type de données on dispose et de de leur nombre et de la stratégie que l'on veut utiliser...

[Sve@r]

J'ai eu à manipuler des variations de 0 à 300 000+ éléments en continu 7j/7, et avec des tableaux et des reallocs, ça finissait par crasher...

Ouais mais bon, ca venait ptet aussi du programmeur...

[souviron34]

Ouais mais bon, ca venait ptet aussi du programmeur...

non

mais a cause du free qui ne libere pas et du realloc, si tu avais par exemple 200 000, puis 50, puis 25 000, puis 350 000, avec des allocs d'autre chose au milieu, la memoire utilisee augmente de maniere constante....

Alors qu'avec une liste chainee, vu que la taille est petite, si tu as entre temps alloue et/ou desalloue disons une chaine temporaire, un petit tableau, etc, tu trouveras toujours un petit coin pour stocker ta structure.. Donc en gros, ta memoire reste stable une fois que tu as atteint une fois ton max...

T'en fais pas, j'avais commence par un tableau ... Et c'est apres avoir eu crash, et fouille des semaines, que je me suis rendu compte que le free ne liberais pas vraiment, et que du coup un realloc ne faisait qu'augmenter la memoire... Alors que des que j'ai remplace par une liste chainee, tout s'est bien passe

[Sve@r]

mais a cause du free qui ne libere pas et du realloc, si tu avais par exemple 200 000, puis 50, puis 25 000, puis 350 000, avec des allocs d'autre chose au milieu, la memoire utilisee augmente de maniere constante....

Vu => Fragmentation de l'espace libre de la mémoire...

[souviron34]

voila..

C'est pour ca que pour moi c'est vrament l'avantage inegalable, comme tu dis...

Maintenant, l'autre aussi

Donc je mettrais au pluriel