[Liste] Différence entre LinkedList et ArrayList ?

**wafiwafi** · 04/10/2010, 22h18

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** · 04/10/2010, 22h32

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** · 04/10/2010, 22h48

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** · 04/10/2010, 23h20

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** · 05/10/2010, 14h42

Envoyé par wafiwafi

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.

Envoyé par wafiwafi

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** · 05/10/2010, 22h36

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** · 05/10/2010, 22h53

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.

**wafiwafi** · 06/10/2010, 09h07

c'est très clair.
Pas de confusions; les choses sont bien à leurs places.
Merci à toi

**wafiwafi** · 07/10/2010, 20h56

Bonjour,
Si List est une interface alors ses méthodes sont vides. Dans ce cas tout ce qui hérite de List implémentent les méthodes.
Est ce que Liste est déclarée comme interface pour habituellement jouir du polymorphisme ou il y a une autre raison (que je ne vois d'ailleurs pas)?. Puisqu'il y a héritage, pourquoi n'a t on pas simplement déclaré List comme une classe mère abstraite avec des implémentations par défaut des méthodes de List. Est ce pour éviter l'héritage multiple?
Pour résumer et être clair, la question est :
Pourquoi List est déclarée comme une interface?
Merci à vous

**tchize_** · 07/10/2010, 22h03

une List n'est pas une classe parce que
-> il n'y a aucun code par défaut associé (quel serait dont alors l'intérêt d'en faire une classe)
-> Ca empecherait n'importe qui d'etre une liste, car on serait obligé d'étendre la classe mère (hors ce n'est pas nécessairement le cas).

**thelvin** · 08/10/2010, 00h24

Ça n'empêcherait pas vraiment... Disons que ce serait moins propre à faire, de une, parce que toute implémentation de liste devrait être sous-classe d'une classe dont elle redéfinit absolument tout. De deux, ça limiterait beaucoup les possibilités de polymorphisme, parce qu'une classe peut implémenter autant d'interfaces qu'elle veut, mais étendre une seule classe.

**wafiwafi** · 09/10/2010, 14h24

C'est bien ce que je pensais; c'est une question d'héritage multiple que supporte le concept interface.
Merci à vous.

**CyberChouan** · 09/10/2010, 15h35

Envoyé par wafiwafi

Puisqu'il y a héritage, pourquoi n'a t on pas simplement déclaré List comme une classe mère abstraite avec des implémentations par défaut des méthodes de List. Est ce pour éviter l'héritage multiple?

Mais ça a été fait. Si List est une interface, l'API de Java contient également une classe abstraite AbstractList.

Cette classe abstraite implémente l'interface List, et définit un certain nombre de méthodes de la classe.

Ainsi, pour accélérer le développement d'une liste concrète, on peut implémenter List... et étendre AbstractList (dans ce cas, implémenter List est d'ailleurs redondant).

C'est d'ailleurs ce qui se passe pour les classes de l'API : ArrayList et LinkedList étendent toutes les deux la classe AbstractList.

**mbntic** · 23/10/2010, 12h03

vos explications sont limpides !

je voulais poser la question sur la différence entre ArrayList et Vector à partir de la version 1.5 ?

**Rei Ichido** · 23/10/2010, 13h46

Vector est synchronisée, et pas ArrayList.

**mbntic** · 23/10/2010, 15h14

hmmm on m'a deja repondu ca !

sauf que je ne sais pas ce que cela veut dire synchronisé.....

**thelvin** · 23/10/2010, 18h17

Ça veut dire que toutes les méthodes de Vector ont le modificateur synchronized. Plus qu'à potasser ce mot-clé.

Pour faire simple, ça veut dire que plusieurs threads peuvent se permettre de lire et d'écrire dans un même Vector en même temps : normalement il y aurait risque que des écritures simultanées mettent l'objet dans un état incohérent, mais les méthodes étant synchronized, un seul thread n'y accède à la fois, les autres attendant que l'accès se libère.

Le mécanisme de synchronisation a un coût, et il est inutile de payer ce coût quand un seul thread utilise la collection. Par conséquent, On ne veut pas toujours un Vector.

(À noter qu'on peut obtenir une List synchronisée avec Collections.synchronizedList(). Vector serait un raccourci, et ressemble aussi un peu à une classe obsolète, vestige d'une ancienne façon de voir.)