octobre
2011
Dans le cas de l’arraylist, les données sont stockées dans un tableau. A l’instanciation, un tableau est créé et rempli en faisant des add. Le problème, c’est que si on ajoute trop d’éléments, le tableau va etre trop petit. Il va donc devoir être recréé et recopié. Pire, si on supprime un élément en plein milieu de la liste, il faut décaler tous les éléments suivants.
L’arraylist est donc bien adapté pour stocker des données qu’on ne va pas supprimer ensuite.
La linkedList, elle, stocke les données sous forme de liste chainée. On peut donc ajouter autant d’élément qu’on veut, il n’y a pas de problème. Et en cas de suppression, il suffit de faire pointer le maillon précédent sur le maillon suivant pour supprimer un maillon. Par contre, pour l’élément l’indice n, il faut parcourir n éléments. Cette liste n’est donc pas adaptée pour accéder aux éléments d’après leur indice.
Le choix du bon type de liste/map peut changer les performances d’une application.
Les accès :
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).
Dans les faits :
Une ArrayList est adaptée aux accès directs et aux listes de taille fixe. Elle peut devenir un trou de performance dans le cas ou la capacité de la liste varie brutalement et rapidement dans le temps (ce qui implique de multiple allocations / recopies de tableaux).
Une LinkedList est adaptée aux listes de taille dynamique avec ajout/retrait en début ou fin de liste ou via une position pointée par un itérateur (et non un indice). Elle peut devenir un trou de performance en cas d’un nombre important d’accès directs via des indices (encore plus si la liste est grande).
En théorie le parcours via itérateur devrait être un poil plus rapide sur une ArrayList que sur une LinkedList de par sa structure contiguë.