Quand utiliser LinkedList plutôt que ArrayList en Java ?

Question

J'ai toujours été du genre à utiliser simplement :

List<String> names = new ArrayList<>();

J'utilise l'interface comme nom de type pour portabilité afin que, lorsque je pose des questions de ce type, je puisse retravailler mon code.

Quand faut-il LinkedList être utilisé sur ArrayList et vice-versa ?

Answer 1

Résumé ArrayList con ArrayDeque sont préférables dans beaucoup de plus de cas d'utilisation que LinkedList . Si vous n'êtes pas sûr - commencez simplement par ArrayList .

---

TLDR, dans ArrayList l'accès à un élément prend un temps constant [O(1)] et l'ajout d'un élément prend un temps O(n) [pire cas]. Dans LinkedList, l'ajout d'un élément prend un temps O(n) et l'accès prend également un temps O(n) mais LinkedList utilise plus de mémoire que ArrayList.

LinkedList y ArrayList sont deux implémentations différentes de l'interface List. LinkedList l'implémente avec une liste doublement liée. ArrayList l'implémente avec un tableau qui se redimensionne dynamiquement.

Comme pour les opérations standard sur les listes et tableaux liés, les diverses méthodes auront des temps d'exécution algorithmiques différents.

Pour LinkedList<E>

• get(int index) es O(n) (avec n/4 pas en moyenne), mais O(1) quand index = 0 ou index = list.size() - 1 (dans ce cas, vous pouvez également utiliser getFirst() y getLast() ). L'un des principaux avantages de LinkedList<E>
• add(int index, E element) es O(n) (avec n/4 pas en moyenne), mais O(1) quand index = 0 ou index = list.size() - 1 (dans ce cas, vous pouvez également utiliser addFirst() y addLast() / add() ). L'un des principaux avantages de LinkedList<E>
• remove(int index) es O(n) (avec n/4 pas en moyenne), mais O(1) quand index = 0 ou index = list.size() - 1 (dans ce cas, vous pouvez également utiliser removeFirst() y removeLast() ). L'un des principaux avantages de LinkedList<E>
• Iterator.remove() es O(1) . L'un des principaux avantages de LinkedList<E>
• ListIterator.add(E element) es O(1) . L'un des principaux avantages de LinkedList<E>

Remarque : de nombreuses opérations nécessitent n/4 pas en moyenne, constant nombre d'étapes dans le meilleur des cas (par exemple, indice = 0), et n/2 étapes dans le pire des cas (milieu de la liste)

Pour ArrayList<E>

• get(int index) es O(1) . Principal avantage de ArrayList<E>
• add(E element) es O(1) amortis, mais O(n) le pire cas puisque le tableau doit être redimensionné et copié
• add(int index, E element) es O(n) (avec n/2 pas en moyenne)
• remove(int index) es O(n) (avec n/2 pas en moyenne)
• Iterator.remove() es O(n) (avec n/2 pas en moyenne)
• ListIterator.add(E element) es O(n) (avec n/2 pas en moyenne)

Remarque : de nombreuses opérations nécessitent n/2 pas en moyenne, constant nombre d'étapes dans le meilleur des cas (fin de la liste), n étapes dans le pire des cas (début de la liste)

LinkedList<E> permet des insertions ou des retraits en temps constant utiliser des itérateurs mais seulement l'accès séquentiel des éléments. En d'autres termes, vous pouvez parcourir la liste en avant ou en arrière, mais trouver une position dans la liste prend un temps proportionnel à la taille de la liste. La Javadoc dit "les opérations qui indexent la liste parcourront la liste depuis le début ou la fin, selon ce qui est le plus proche". Ces méthodes sont donc O(n) ( n/4 pas) en moyenne, bien que O(1) para index = 0 .

ArrayList<E> D'autre part, ils permettent un accès rapide à la lecture aléatoire, de sorte que vous pouvez saisir n'importe quel élément en temps constant. Mais l'ajout ou la suppression d'un élément à partir de n'importe quel endroit sauf l'extrémité nécessite de déplacer tous les derniers éléments, soit pour créer une ouverture, soit pour combler le vide. De plus, si vous ajoutez plus d'éléments que la capacité du tableau sous-jacent, un nouveau tableau (1,5 fois la taille) est alloué, et l'ancien tableau est copié dans le nouveau. ArrayList es O(n) dans le pire des cas mais constante en moyenne.

Ainsi, selon les opérations que vous avez l'intention d'effectuer, vous devez choisir les implémentations en conséquence. L'itération sur l'un ou l'autre type de liste est pratiquement aussi bon marché. (L'itération sur une ArrayList est techniquement plus rapide, mais à moins que vous ne fassiez quelque chose de vraiment sensible aux performances, vous ne devriez pas vous soucier de cela -- ce sont toutes deux des constantes).

Les principaux avantages de l'utilisation d'un LinkedList surviennent lorsque vous réutilisez des itérateurs existants pour insérer et supprimer des éléments. Ces opérations peuvent alors être effectuées dans O(1) en modifiant la liste localement seulement. Dans une liste de type tableau, le reste du tableau doit être déplacé (c'est-à-dire copié). D'un autre côté, la recherche dans un LinkedList signifie suivre les liens dans O(n) ( n/2 étapes) dans le pire des cas, alors que dans un ArrayList la position souhaitée peut être calculée mathématiquement et accessible en O(1) .

Un autre avantage de l'utilisation d'un LinkedList se produit lorsque vous ajoutez ou retirez de la tête de la liste, car ces opérations sont O(1) alors qu'ils sont O(n) para ArrayList . Notez que ArrayDeque peut être une bonne alternative à LinkedList pour ajouter et enlever de la tête, mais ce n'est pas une List .

En outre, si vous avez de grandes listes, n'oubliez pas que l'utilisation de la mémoire est également différente. Chaque élément d'une LinkedList est plus coûteux car les pointeurs vers les éléments suivants et précédents sont également stockés. ArrayLists n'ont pas ces frais généraux. Cependant, ArrayLists occupent autant de mémoire que celle qui est allouée à la capacité, que des éléments aient été effectivement ajoutés ou non.

La capacité initiale par défaut d'un ArrayList est assez faible (10 de Java 1.4 à 1.8). Mais comme l'implémentation sous-jacente est un tableau, ce dernier doit être redimensionné si vous ajoutez beaucoup d'éléments. Pour éviter le coût élevé du redimensionnement lorsque vous savez que vous allez ajouter beaucoup d'éléments, construisez la balise ArrayList avec une capacité initiale plus élevée.

Si l'on utilise la perspective des structures de données pour comprendre les deux structures, une LinkedList est fondamentalement une structure de données séquentielle qui contient un nœud de tête. Le Node est une enveloppe pour deux composants : une valeur de type T [acceptée par les génériques] et une autre référence au Node qui lui est lié. Ainsi, nous pouvons affirmer qu'il s'agit d'une structure de données récursive (un Node contient un autre Node qui a un autre Node et ainsi de suite...). L'ajout d'éléments prend un temps linéaire dans LinkedList comme indiqué ci-dessus.

Une ArrayList est un tableau évolutif. C'est exactement comme un tableau ordinaire. Lorsqu'un élément est ajouté et que la liste de tableaux est déjà pleine, elle crée un autre tableau dont la taille est supérieure à la taille précédente. Les éléments sont alors copiés du tableau précédent vers le nouveau et les éléments qui doivent être ajoutés sont également placés aux indices spécifiés.

Answer 2

Jusqu'à maintenant, personne ne semble avoir abordé l'empreinte mémoire de chacune de ces listes en outre, le consensus général qu'un LinkedList est "beaucoup plus" que l' ArrayList donc j'ai fait quelques calculs pour démontrer exactement comment beaucoup les deux listes prendre pour N références nulles.

Depuis références sont soit 32 ou 64 bits (même quand null) de leurs systèmes, j'ai inclus les 4 ensembles de données de 32 bits et 64 LinkedLists et ArrayLists.

Note: Les montants indiqués pour l' ArrayList des lignes sont pour garnis de listes - Dans la pratique, la capacité de la sauvegarde de tableau dans une ArrayList est généralement supérieure à celle de son élément en cours de comptage.

Note 2: (merci BeeOnRope) Comme CompressedOops la valeur par défaut est maintenant à partir de la mi JDK6, les valeurs ci-dessous pour les ordinateurs 64 bits sera essentiellement correspondent à leurs 32 bits homologues, à moins bien sûr que vous avez spécifiquement l'éteindre.

Le résultat montre clairement que LinkedList est un ensemble beaucoup plus que ArrayList, surtout avec un très fort élément de comptage. Si la mémoire est un facteur, évitez LinkedLists.

Les formules que j'ai utilisé à suivre, laissez-moi savoir si j'ai fait quelque chose de mal et je vais le corriger. " b "est de 4 ou 8 32 ou 64 bits des systèmes, et" n " est le nombre d'éléments. La raison pour le mods est parce que tous les objets en java va prendre un multiple de 8 octets de l'espace, qu'il soit utilisé ou non.

ArrayList:

ArrayList object header + size integer + modCount integer + array reference + (array oject header + b * n) + MOD(array oject, 8) + MOD(ArrayList object, 8) == 8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8) + MOD(8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8), 8)

LinkedList:

LinkedList object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) * n) + MOD(node object, 8) * n + MOD(LinkedList object, 8) == 8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n + MOD(8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n, 8)

Answer 3

ArrayList est ce que vous voulez. LinkedList est presque toujours un bug (de performance).

Pourquoi LinkedList craint :

• Il utilise beaucoup de petits objets mémoire, ce qui a un impact sur les performances de l'ensemble du processus.
• Un grand nombre de petits objets est mauvais pour la localité du cache.
• Toute opération indexée nécessite une traversée, c'est-à-dire qu'elle a des performances O(n). Ceci n'est pas évident dans le code source, ce qui conduit à des algorithmes O(n) plus lents que si ArrayList a été utilisé.
• Obtenir de bonnes performances est délicat.
• Même si les performances de big-O sont les mêmes que celles de ArrayList il sera probablement beaucoup plus lent de toute façon.
• C'est choquant de voir LinkedList dans la source parce que c'est probablement le mauvais choix.

Answer 4

En tant qu'ingénieur des performances opérationnelles de services Web SOA à très grande échelle depuis une dizaine d'années, je préfère le comportement de LinkedList à celui de ArrayList. Si le débit en régime permanent de LinkedList est moins bon et peut donc conduire à l'achat de plus de matériel, le comportement d'ArrayList sous pression peut conduire les applications d'un cluster à étendre leurs tableaux de manière quasi-synchrone et, pour les tableaux de grande taille, à un manque de réactivité de l'application et à une panne, sous pression, ce qui est un comportement catastrophique.

De même, vous pouvez obtenir un meilleur débit dans une application grâce au ramasseur d'ordures par défaut, mais une fois que vous avez des applications java avec des tas de 10 Go, vous pouvez vous retrouver à bloquer l'application pendant 25 secondes au cours d'un GC complet, ce qui entraîne des délais d'attente et des échecs dans les applications SOA et fait sauter vos SLA si cela se produit trop souvent. Même si le collecteur CMS consomme plus de ressources et n'atteint pas le même débit brut, il constitue un bien meilleur choix car sa latence est plus prévisible et plus faible.

ArrayList n'est un meilleur choix pour les performances que si tout ce que vous entendez par performances est le débit et que vous pouvez ignorer la latence. Dans mon travail, je ne peux pas ignorer la latence dans le pire des cas.

Mise à jour (27 août 2021 -- 10 ans après) : Cette réponse (qui est aussi celle qui a reçu le plus de votes sur SO) est très probablement fausse (pour les raisons exposées dans les commentaires ci-dessous). J'aimerais ajouter que ArrayList optimisera la lecture séquentielle de la mémoire et minimisera les manques de lignes de cache et de TLB, etc. Le surcoût de la copie lorsque le tableau grandit au-delà des limites est probablement sans conséquence en comparaison (et peut être fait par des opérations efficaces du CPU). Cette réponse va probablement s'aggraver avec le temps, compte tenu des tendances matérielles. Les seules situations où une LinkedList pourrait avoir un sens seraient quelque chose de très artificiel où vous auriez des milliers de Listes, chacune d'entre elles pouvant atteindre la taille d'un Go, mais où aucune bonne estimation ne pourrait être faite au moment de l'allocation de la Liste et où le fait de les définir toutes à la taille d'un Go ferait exploser le tas. Et si vous avez trouvé un problème de ce genre, alors il faut vraiment revoir votre solution, quelle qu'elle soit (et je n'aime pas suggérer à la légère de revoir un vieux code parce que je maintiens moi-même des piles et des piles de vieux code, mais ce serait un très bon cas de figure où la conception originale est simplement à bout de souffle et doit être abandonnée). Je vais quand même laisser mon opinion médiocre, vieille de plusieurs décennies, pour que vous puissiez la lire. Simple, logique et plutôt fausse.

Answer 5

Oui, je sais, c'est une vieille question, mais je vais y mettre mon grain de sel :

LinkedList est presque toujours le mauvais choix, en termes de performances. Il existe des algorithmes très spécifiques pour lesquels une LinkedList est nécessaire, mais ils sont très, très rares et l'algorithme dépend généralement de la capacité de la LinkedList à insérer et à supprimer des éléments au milieu de la liste relativement rapidement, une fois que vous y avez navigué avec un ListIterator.

Il existe un cas d'utilisation courant dans lequel LinkedList est plus performant que ArrayList : celui d'une file d'attente. Cependant, si votre objectif est la performance, au lieu de LinkedList, vous devriez également envisager d'utiliser une ArrayBlockingQueue (si vous pouvez déterminer une limite supérieure de la taille de votre file d'attente à l'avance, et si vous pouvez vous permettre d'allouer toute la mémoire à l'avance), ou ceci Mise en œuvre de CircularArrayList . (Oui, c'est de 2001, donc vous devrez le généraliser, mais j'ai obtenu des ratios de performance comparables à ceux cités dans l'article juste maintenant dans une JVM récente)