Java : quand recourir au couple LinkedList - ArrayList ?
Les classes LinkedList et ArrayList sont utilisées pour stocker une série d'éléments les uns à la suite des autres.
Les classes LinkedList et ArrayList sont toutes les deux des implémentations de l'interface List. Elles sont utilisées pour stocker une série d'éléments les uns à la suite des autres. Leur fonctionnement est cependant différent car elles ne sont pas gérées de la même manière en mémoire. C'est à vous de choisir quelle classe correspondra le mieux à vos besoins dans votre développement.
Dans une LinkedList, chaque élément est stocké en mémoire avec l'adresse du suivant et du précédent. Cela permet l'utilisation d'itérateurs pour ajouter ou supprimer des éléments à la volée. De plus, il est très rapide d'insérer un élément au début car il suffit de modifier l'élément qui était auparavant le premier pour lui ajouter l'adresse du nouvel élément. A l'inverse, cette disposition en mémoire oblige à parcourir la liste si l'on veut trouver un élément au milieu. Dans ce cas, l'algorithme part du début ou de la fin de la liste, selon la position de l'élément que l'on veut récupérer. L'opération prend alors plus de temps que pour une ArrayList.
Lorsqu'on utilise une ArrayList, les éléments sont stockés en mémoire de manière à ce que leur position soit calculée par l'algorithme. Il est donc très facile d'accéder à n'importe quel élément situé n'importe où dans une ArrayList. Si vous devez insérer un élément autre part qu'à la fin de la liste, tous les éléments suivants doivent être décalés, ce qui prend plus de temps que pour une LinkedList. Si l'ajout d'un élément entraîne une modification de la taille de la ArrayList, alors une nouvelle liste plus grande sera créée et les éléments y seront copiés, ce qui prend du temps. Si vous savez à l'avance que vous avez besoin d'une grande capacité, pensez à définir une grande taille à la création de la liste (dans les versions 1.4 à 1.8 de Java, la taille par défaut est 10). Un autre avantage de la classe ArrayList est qu'elle prend moins de place dans la mémoire qu'une LinkedList car il n'y a pas de pointeur vers les éléments suivants et précédents à stocker.