Java ArrayList vs LinkedList

1. Vue d'ensemble

En ce qui concerne les collections, la bibliothèque standard Java propose de nombreuses options. Parmi ces options, il y a deux célèbres implémentations de List appelées ArrayList et LinkedList, chacune avec ses propres propriétés et cas d'utilisation.

Dans ce tutoriel, nous allons voir comment ces deux sont réellement implémentés. Ensuite, nous évaluerons différentes applications pour chacune.

2. ArrayList

En interne, ArrayList utilise un tableau pour implémenter l' interface List . Comme les tableaux sont de taille fixe en Java, ArrayList crée un tableau avec une certaine capacité initiale. En cours de route, si nous devons stocker plus d'éléments que cette capacité par défaut, il remplacera cette baie par une nouvelle et plus spacieuse.

Pour mieux comprendre ses propriétés, évaluons cette structure de données par rapport à ses trois opérations principales: ajouter des éléments, en obtenir un par index et supprimer par index.

2.1. Ajouter

Lorsque nous créons un ArrayList vide , il initialise son tableau de sauvegarde avec une capacité par défaut (actuellement 10):

Ajouter un nouvel élément alors que ce tableau n'est pas encore plein est aussi simple que d'affecter cet élément à un index de tableau spécifique. Cet index de tableau est déterminé par la taille actuelle du tableau puisque nous ajoutons pratiquement à la liste:

backingArray[size] = newItem; size++;

Ainsi, dans les meilleurs et moyens cas, la complexité temporelle de l'opération d'ajout est O (1) , ce qui est assez rapide. Cependant, lorsque le tableau de sauvegarde devient plein, l'implémentation d'ajout devient moins efficace:

Pour ajouter un nouvel élément, nous devons d'abord initialiser une toute nouvelle baie avec plus de capacité et copier tous les éléments existants dans la nouvelle baie. Ce n'est qu'après avoir copié les éléments actuels que nous pouvons ajouter le nouvel élément. Par conséquent, la complexité temporelle est O (n) dans le pire des cas car nous devons d'abord copier n éléments.

Théoriquement, l'ajout d'un nouvel élément s'exécute en temps constant amorti. Autrement dit, l'ajout de n éléments nécessite un temps O (n) . Cependant, certains ajouts simples peuvent mal fonctionner en raison de la surcharge de copie.

2.2. Accès par index

L'accès aux éléments par leurs index est l'endroit où la ArrayList brille vraiment. Pour récupérer un élément à l'index i, il suffit de renvoyer l'élément résidant au ième index du tableau de sauvegarde. Par conséquent, la complexité temporelle pour l'accès par opération d'index est toujours O (1).

2.3. Supprimer par index

Supposons que nous allons supprimer l'index 6 de notre ArrayList, qui correspond à l'élément 15 dans notre tableau de sauvegarde:

Après avoir marqué l'élément souhaité comme supprimé, nous devons déplacer tous les éléments après celui-ci d'un index. Évidemment, plus l'élément est proche du début du tableau, plus nous devons déplacer d'éléments. La complexité temporelle est donc O (1) dans le meilleur des cas et O (n) dans la moyenne et dans le pire des cas.

2.4. Applications et limitations

En général, ArrayList est le choix par défaut pour de nombreux développeurs lorsqu'ils ont besoin d'une implémentation de List . En fait, c'est en fait un choix judicieux lorsque le nombre de lectures est bien supérieur au nombre d'écritures .

Parfois, nous avons besoin de lectures et d'écritures aussi fréquentes. Si nous avons une estimation du nombre maximum d'éléments possibles, il est toujours judicieux d'utiliser ArrayList . Si tel est le cas, nous pouvons initialiser ArrayList avec une capacité initiale:

int possibleUpperBound = 10_000; List items = new ArrayList(possibleUpperBound);

Cette estimation peut éviter de nombreuses copies et allocations de tableaux inutiles.

De plus, les tableaux sont indexés par des valeurs int en Java. Il n'est donc pas possible de stocker plus de 232 éléments dans un tableau Java et, par conséquent, dans ArrayList .

3. LinkedList

LinkedList , comme son nom l'indique, utilise une collection de nœuds liés pour stocker et récupérer des éléments . Par exemple, voici à quoi ressemble l'implémentation Java après l'ajout de quatre éléments:

Chaque nœud maintient deux pointeurs: un pointant vers l'élément suivant et un autre faisant référence au précédent. S'étendant sur cela, la liste à double chaînage comporte deux pointeurs pointant vers le premier et le dernier élément.

Encore une fois, évaluons cette implémentation par rapport aux mêmes opérations fondamentales.

3.1. Ajouter

Afin d'ajouter un nouveau nœud, nous devons d'abord lier le dernier nœud actuel au nouveau nœud:

Et puis mettez à jour le dernier pointeur:

Comme ces deux opérations sont triviales, la complexité temporelle de l'opération d'ajout est toujours O (1) .

3.2. Accès par index

LinkedList, contrairement à ArrayList, ne prend pas en charge l'accès aléatoire rapide. Donc, pour trouver un élément par index, nous devons parcourir une partie de la liste manuellement .

Dans le meilleur des cas, lorsque l'élément demandé est proche du début ou de la fin de la liste, la complexité temporelle serait aussi rapide que O (1). Cependant, dans le scénario moyen et le pire des cas, nous pouvons nous retrouver avec un temps d'accès O (n) car nous devons examiner de nombreux nœuds les uns après les autres.

3.3. Supprimer par index

Afin de supprimer un élément, nous devons d'abord trouver l'élément demandé, puis le dissocier de la liste . Par conséquent, le temps d'accès détermine la complexité temporelle - c'est-à-dire O (1) au meilleur des cas et O (n) en moyenne et dans les pires scénarios.

3.4. Applications

Les LinkedLists conviennent mieux lorsque le taux d'ajout est beaucoup plus élevé que le taux de lecture .

En outre, il peut être utilisé dans des scénarios de lecture intensive lorsque la plupart du temps, nous voulons le premier ou le dernier élément. Il convient de mentionner que LinkedList implémente également l' interface Deque - prenant en charge un accès efficace aux deux extrémités de la collection.

En général, si nous connaissons leurs différences d'implémentation, nous pourrions facilement en choisir une pour un cas d'utilisation particulier.

Par exemple, disons que nous allons stocker de nombreux événements de séries chronologiques dans une structure de données de type liste. Nous savons que nous recevrions des rafales d'événements chaque seconde.

De plus, nous devons examiner périodiquement tous les événements les uns après les autres et fournir des statistiques. Pour ce cas d'utilisation, LinkedList est un meilleur choix car le taux d'ajout est beaucoup plus élevé que le taux de lecture.

De plus, nous lirions tous les éléments, nous ne pouvons donc pas battre la limite supérieure O (n) .

4. Conclusion

Dans ce didacticiel, nous avons tout d'abord abordé la manière dont ArrayList et LinkLists sont implémentés en Java.

Nous avons également évalué différents cas d'utilisation pour chacun d'entre eux.