Discussion :

[wafiwafi]

Bonjour,
On utilise souvent les deux structures LinkedList (liste chainée)et arraylist tableau dynamique.
Question:
Y a t il vraiment une différence entre ces dernières puisque de toute façon, rien n'est garanti quant à la contiguïté des données en mémoire. La JVM fait à sa sauce! En plus n'oublions pas la plateforme sur laquelle tourne la JVM; elle met sa couche de gestion de la mémoire.

merci à vous

[CyberChouan]

La différence se situe surtout au niveau de la façon dont tu dois accéder à tes données.

Une ArrayList est gérée en interne par un tableau. On peut donc accéder en temps constant à n'importe quel élément par "monArrayList.get(nb);".

Avec une LinkedList, une telle commande est catastrophique en termes de performances (il faut passer par les nb-1 premiers éléments pour accéder au nb-ième).

[wafiwafi]

Merci pour ta réponse.

Une ArrayList est gérée en interne par un tableau. On peut donc accéder en temps constant à n'importe quel élément par "monArrayList.get(nb);".

J'ai toujours appris qu'une liste est en accès séquentiel.
Il s'agit bien d'une liste?
Je pensais que la différence venait de la contiguïté des données.

[bouye]

Si les donnees ne sont justement pas contigues, il faut prendre en compte le temps d'acces a l'addresse / decallage memoire pour chacun des elements precedents qui vient justement s'ajouter en cas d'acces direct a l'element n.

Dans les faits :

• Une ArrayList est adaptee aux acces directs et aux listes de taille fixe. Elle peut devenir un trou de performance dans le cas ou la capacite de la liste varie brutalement et rapidement dans le temps (ce qui implique de multiple allocations / recopies de tableaux).
• Une LinkedList est adaptee aux listes de taille dynamique avec ajout/retrait en debut ou fin de liste ou via une position pointee par un iterateur (et non un indice). Elle peut devenir un trou de performance en cas d'un nombre important d'acces directs via des indices (encore plus si la liste est grande).

En theorie le parcours via iterateur devrait etre un poil plus rapide sur une ArrayList que sur une LinkedList de par sa structure contigue.

[thelvin]

J'ai toujours appris qu'une liste est en accès séquentiel.
Il s'agit bien d'une liste?

Une liste est une séquence de choses dont l'ordre ne change pas sans qu'on lui demande.
Son accès peut être séquentiel ou aléatoire selon les besoins.
Toutefois, si on a besoin de la parcourir séquentiellement, il faut le faire explicitement avec un itérateur, plutôt que de faire une boucle d'accès aléatoires. Parce que si une ArrayList le supporterait bien, en revanche ça plairait pas du tout à une LinkedList.

Je pensais que la différence venait de la contiguïté des données.

Cela n'est qu'une conséquence implicite de leurs différences. La différence, c'est que l'une stocke dans un tableau, l'autre maintient une chaîne de références.

Et il s'agit plus de données stockées dans le même tableau, qu'une garantie système de l'utilisation exacte de la mémoire physique. Effectivement, ce genre d'économie de bouts de ficelles est rarement imposable à Java : la JVM sait organiser un tableau, merci bien.
Il existe des cas plus réels où la JVM n'est pas en mesure de choisir la bonne solution, auquel cas, en effet, ça devient compliqué. Dans ce cas-là, ou bien Java fournit des APIs à employer, ou bien il devient nécessaire de développer les siennes en JNI.

[wafiwafi]

Voila ce que j'en déduis :
ArrayList est un tableau; l'accès est donc aléatoire.
LinkedList est une liste chainée; l'accès se fait par un itération.

Par contre, une chose me dérange ou du moins reste ambiguë pour moi :
C'est le cas d'une liste dont les emplacements sont contigües. L'accès dans ce cas peut être aléatoire ou par itération. Or, dans la définition d'une liste (que j'ai vue dans plusieurs documents et livres) et surtout quand on la compare à un tableau, on lui attribue de suite l'aspect séquentiel des accès, ce qui rentre en contradiction avec ce qui précède si on considère que ArrayList est une liste.
Tout ces ouvrages font il allusion à la liste chainée? ou je me trompe?
Merci à vous

[thelvin]

Mais ça c'est très abstrait comme considération, et pas particulièrement lié aux nomenclatures choisies par un langage précis.

En Java, List est simplement une interface, qui étend l'interface Collection.
Une Collection, c'est un machin qui contient des objets, éventuellement en respectant des règles sur la manière de les organiser, l'ordre dans lequel les rendre ou ce genre de choses.
Une List, donc, est aussi un machin qui contient des objets. Mais en plus, qui conserve l'ordre dans lequel on les lui ajoute, et qui propose d'aller regarder/remplacer/enlever/insérer-un-autre-objet-avant celui qui se trouve en i-ième position.

Et ça, il y a grosso-modo deux manières de le faire :
- En stockant dans un tableau, qu'on redimensionne au besoin, et en décalant tout le contenu à chaque suppression/insertion. C'est l'implémentation ArrayList de List.
L'intérêt par rapport à "juste un tableau" c'est que le tableau, il ne se redimensionne pas tout seul et il ne décale rien du tout, bref il ne fait pas ce que l'interface List dit qu'elle fait. C'est utile, pourtant.
- En maintenant une chaîne de références, qu'il va donc falloir se taper chaque fois qu'on veut regarder la position i et pas une autre. C'est l'implémentation LinkedList.

En Java c'est ça que le type List, une interface, est. Elle n'est pas un concept plus abstrait qu'on nomme liste dans les discussions théoriques. En Java, ce concept abstrait se limiterait plutôt à la LinkedList.