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 !!
Version imprimable
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 logiqueCitation:
Envoyé par Devilju69
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...Citation:
Envoyé par Devilju69
ET de prendre beaucoup moins de place memoire lorsuqe l'on doit faire varier le nombre d'elements grandement....Citation:
Envoyé par Sve@r
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 reallocCitation:
Envoyé par souviron34
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.Citation:
Envoyé par corentin59
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.
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...
Ouais mais bon, ca venait ptet aussi du programmeur...:mouarf:Citation:
Envoyé par souviron34
:aie: nonCitation:
Envoyé par 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....
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 :P
Vu => Fragmentation de l'espace libre de la mémoire...Citation:
Envoyé par souviron34
:mrgreen: voila..
C'est pour ca que pour moi c'est vrament l'avantage inegalable, comme tu dis...
Maintenant, l'autre aussi :D
Donc je mettrais au pluriel :D