Question Quand utiliser LinkedList sur ArrayList?


J'en ai toujours été un à utiliser simplement:

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

J'utilise l'interface comme nom de type pour portabilité, de sorte que lorsque je pose des questions comme celles-ci, je peux retravailler mon code.

Quand devrait LinkedList être utilisé sur ArrayList et vice versa?


2565
2017-11-27 01:36


origine


Réponses:


Résumé  ArrayList avec ArrayDeque sont préférables beaucoup plus de cas d'utilisation que LinkedList. Pas sûr - commencez par ArrayList.


LinkedList et ArrayList sont deux implémentations différentes de l'interface List. LinkedList l'implémente avec une liste doublement chaînée. ArrayList l'implémente avec un tableau de redimensionnement dynamique.

Comme pour les opérations de liste chaînée et de tableau standard, les différentes méthodes auront des temps d'exécution algorithmiques différents.

Pour LinkedList<E>

  • get(int index) est Sur) (avec n / 4 étapes en moyenne)
  • add(E element) est O (1)
  • add(int index, E element) est Sur) (avec n / 4 étapes en moyenne), mais O (1) quand index = 0  <--- principal avantage de LinkedList<E>
  • remove(int index) est Sur) (avec n / 4 étapes en moyenne)
  • Iterator.remove() est O (1). <--- principal avantage de LinkedList<E>
  • ListIterator.add(E element) est O (1)  C'est l'un des principaux avantages de LinkedList<E>

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

Pour ArrayList<E>

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

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

LinkedList<E> permet des insertions ou des suppressions à temps constant en utilisant 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 du temps proportionnellement à la taille de la liste. Javadoc dit "les opérations qui indexent dans la liste traverseront la liste depuis le début ou la fin, selon la plus proche", donc ces méthodes sont Sur) (n / 4 étapes) en moyenne, bien que O (1) pour index = 0.

ArrayList<E>, d'autre part, permettent un accès rapide en lecture aléatoire, de sorte que vous pouvez saisir n'importe quel élément dans le temps constant. Mais l'ajout ou le retrait de n'importe où mais la fin exige de déplacer tous ces derniers éléments, soit pour faire une ouverture ou combler le vide. En outre, 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, donc l'ajout à un ArrayList est Sur) dans le pire des cas mais constant en moyenne.

Donc, en fonction des opérations que vous avez l'intention de faire, vous devez choisir les implémentations en conséquence. Itérer sur l'un ou l'autre type de liste est pratiquement aussi bon marché. (Itérer sur un ArrayList est techniquement plus rapide, mais à moins que vous ne fassiez quelque chose de vraiment sensible aux performances, vous ne devriez pas vous en préoccuper - ce sont deux 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 ensuite être effectuées O (1) en changeant la liste localement seulement. Dans une liste de tableaux, le reste du tableau doit être déplacé (c'est-à-dire copié). De l'autre côté, cherchant dans un LinkedList signifie suivre les liens dans Sur) (n / 2 étapes) pour le pire des cas, alors que dans un ArrayList la position désirée peut être calculée mathématiquement et accédée dans O (1).

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

En outre, si vous avez de grandes listes, gardez à l'esprit que l'utilisation de la mémoire est également différente. Chaque élément d'un LinkedList a plus de frais généraux puisque les pointeurs vers les éléments suivants et précédents sont également stockés. ArrayLists ne pas avoir ce frais généraux. cependant, ArrayLists occupe autant de mémoire que celle allouée à la capacité, que des éléments aient été réellement ajoutés ou non.

La capacité initiale par défaut d'un ArrayList est assez petit (10 de Java 1.4 - 1.8). Mais puisque l'implémentation sous-jacente est un tableau, le tableau 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 le ArrayList avec une capacité initiale plus élevée.


2845
2017-10-06 06:46



Jusqu'à présent, personne ne semble avoir abordé l'empreinte mémoire de chacune de ces listes en plus du consensus général selon lequel LinkedList est "beaucoup plus" qu'un ArrayList J'ai donc fait un certain nombre de calculs pour montrer exactement combien les deux listes prennent pour N références nulles.

Puisque les références sont soit 32 ou 64 bits (même lorsqu'elles sont nulles) sur leurs systèmes relatifs, j'ai inclus 4 ensembles de données pour 32 et 64 bits LinkedLists et ArrayLists.

Remarque: Les tailles indiquées pour le ArrayList les lignes sont pour listes rognées - En pratique, la capacité du backing array dans un ArrayList est généralement plus grand que son nombre actuel d'éléments.

Note 2:  (merci BeeOnRope) Comme CompressedOops est désormais par défaut à partir du milieu JDK6 et supérieur, les valeurs ci-dessous pour les machines 64 bits correspondront essentiellement à leurs homologues 32 bits, à moins bien sûr que vous ne le désactiviez spécifiquement.


Graph of LinkedList and ArrayList No. of Elements x Bytes


Le résultat montre clairement que LinkedList est beaucoup plus que ArrayList, surtout avec un nombre d'éléments très élevé. Si la mémoire est un facteur, évitez LinkedLists.

Les formules que j'ai utilisées suivent, faites-moi savoir si j'ai fait quelque chose de mal et je réparerai. 'b' est 4 ou 8 pour les systèmes 32 ou 64 bits, et 'n' est le nombre d'éléments. Notez que la raison de ces mods est que tous les objets de Java prendront un multiple de 8 octets, qu'ils soient tous utilisés 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)

534
2017-11-27 14:20



ArrayList est ce que tu veux. LinkedList est presque toujours un bug (performance).

Pourquoi LinkedList suce:

  • Il utilise beaucoup d'objets mémoire de petite taille et a donc un impact sur les performances tout au long du processus.
  • Beaucoup de petits objets sont mauvais pour le cache-localité.
  • Toute opération indexée nécessite une traversée, c'est-à-dire une performance O (n). Ce n'est pas évident dans le code source, conduisant à des algorithmes O (n) plus lents que si ArrayLista été utilisé.
  • Obtenir de bonnes performances est difficile.
  • Même lorsque la performance big-O est la même que ArrayList, il va probablement être beaucoup plus lent de toute façon.
  • C'est discordant de voir LinkedList dans la source parce que c'est probablement le mauvais choix.

190
2018-01-01 20:23



En tant que quelqu'un qui a fait de l'ingénierie de performance opérationnelle sur des services web SOA à très grande échelle pendant environ une décennie, je préférerais le comportement de LinkedList sur ArrayList. Alors que le débit en régime permanent de LinkedList est pire et pourrait donc conduire à acheter plus de matériel - le comportement de ArrayList sous pression pourrait conduire à des applications dans un cluster élargissant leurs réseaux en quasi synchronicité et pour les grandes tailles de tableau pourrait entraîner un manque de réactivité dans l'application et une panne, tandis que sous pression, ce qui est un comportement catastrophique.

De même, vous pouvez obtenir un meilleur débit dans une application du garbage collector à débit par défaut, mais une fois que vous obtenez des applications java avec 10Go, vous pouvez verrouiller l'application pendant 25 secondes pendant un GC complet qui provoque des délais et des échecs dans les applications SOA et souffle vos SLA si cela arrive trop souvent. Même si le collecteur CMS prend plus de ressources et n'atteint pas le même débit brut, c'est un bien meilleur choix car il a une latence plus prévisible et plus petite.

ArrayList est seulement un meilleur choix pour la performance si tout ce que vous entendez par performance est le débit et vous pouvez ignorer la latence. Dans mon expérience à mon travail, je ne peux pas ignorer le pire des cas de latence.


125
2018-04-08 20:33



Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

Algorithmes: Notation Big-Oh

ArrayLists est bon pour write-once-read-many ou appenders, mais mauvais à ajouter / supprimer à l'avant ou au milieu.


111
2018-05-19 11:21



Oui, je sais, c'est une question ancienne, mais je vais jeter dans mes deux cents:

LinkedList est presque toujours le mauvais choix, en termes de performances. Il y a des algorithmes très spécifiques où un LinkedList est demandé, mais ils sont très, très rares et l'algorithme dépendra spécifiquement de la capacité de 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 surclasse ArrayList: celui d'une file d'attente. Cependant, si votre objectif est la performance, au lieu de LinkedList vous devriez aussi envisager d'utiliser une ArrayBlockingQueue (si vous pouvez déterminer une limite supérieure de votre taille de file d'attente à l'avance, et vous permettre d'allouer toute la mémoire) Implémentation de CircularArrayList. (Oui, c'est à partir de 2001, donc vous aurez besoin de le générer, mais j'ai obtenu des ratios de performance comparables à ce qui est cité dans l'article tout à l'heure dans une JVM récente)


92
2017-11-27 01:39



C'est une question d'efficacité. LinkedList est rapide pour l'ajout et la suppression d'éléments, mais lent pour accéder à un élément spécifique. ArrayList est rapide pour accéder à un élément spécifique, mais peut être lent à ajouter à l'une ou l'autre fin, et surtout lent à supprimer au milieu.

Array vs ArrayList vs LinkedList vs vecteurva plus en profondeur, comme le fait Liste liée.


50
2017-09-21 22:59