Discussion :

[thierryler]

Bonjour,

On parle souvent de ces trois listes en Java.

La différence qui me semble importante entre Vector et ArrayList est la synchro.

On dit souvent (on me dit) que LinkedList est plus performant que ArrayList, mais pourquoi ? Je suppose qu'il y a des cas d'utilisation bien précis pour l'un ou l'autre.

[billynirvana]

Tu as la réponse ici:

http://java.developpez.com/faq/java/...IONS_info_list

[thierryler]

merci au niveau de l'algo c'est clair maintenant.

Donc si je reprend

L'API propose deux implémentations concrètes pour les listes (java.util.List). Une liste est une suite ordonnée d'éléments (les éléments peuvent être ajoutés à plusieurs endroits de la liste).

java.util.ArrayList :
Un java.util.ArrayList utilise un tableau en interne pour ranger les données. Un ArrayList fournit un accès aux éléments par leur indice très performant et est optimisé pour des opérations d'ajout/suppression d'éléments en fin de liste.
Complexité : Les opérations size, isEmpty, get, set, iterator sont exécutées en temps constant.
Les opérations d'ajout/suppression sont exécutées en temps constant amorti (les ajouts/suppressions en fin de liste sont plus rapides).

java.util.LinkedList :
Un java.util.LinkedList utilise une liste chainée pour ranger les données. L'ajout et la suppression d'éléments est aussi rapide quelle que soit la position, mais l'accès aux valeurs par leur indice est très lente.
Complexité : Les opérations size, isEmpty, add, remove, set, get sont exécutées en temps constant. Toutes les méthodes qui font référence à un indice sont exécutées en temps O(n).

java.util.Vector :
La classe java.util.Vector est une classe héritée de Java 1. Elle n'est conservée dans l'API actuelle que pour des raisons de compatiblité ascendante et elle ne devrait pas être utilisée dans les nouveaux programmes. Dans tous les cas, il est préférable d'utiliser un ArrayList.
Note : Cette classe est "thread-safe", c'est-à-dire que plusieurs processus peuvent l'utiliser en même temps sans risque.
Complexité : idem que pour ArrayList, plus le temps de synchronisation des méthodes.

Quand est ce que j'utilise un ArrayList à la place d'un LinkedList ?

[tchize_]

en général:

petite liste (<10 éléments) j'utilise systématiquement une arrayList. Pareil si je sais que je devrais parcourir la liste via son index ou si je crée la liste à partir d'une tableau et que je ne la modifie plus après coup.

Si, au contraire, je sais que je parcourerais la liste uniquement avec un Iterator (pas de get(X) ) et que j'aurais beaucoup d'opérations d'ajout / suppression à faire, la linkelist est préférable.

A noter qu'à taille donnée, une linkedlist prend plus de place en mémoire qu'un arrayList car la linkedList a besoin d'un instance de "Noeud" par élément.