Quand utiliser LinkedList sur ArrayList en Java?

3123

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

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

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

Quand faut- LinkedListil l'utiliser plus ArrayListet vice-versa?

sdellysse
la source
4
Voir aussi: Tableau versus liste liée
Hawkeye Parker
1
Consultez la citation de l'auteur de LinkedList stackoverflow.com/a/42529652/2032701 et vous aurez une idée pratique du problème.
Ruslan
Voir la publication Java LinkedList vs ArrayList , qui décrit les différences et inclut des tests de performances.
alonana

Réponses:

3371

Les résumés ArrayList avec ArrayDequesont préférables dans beaucoup plus de cas d'utilisation que LinkedList. Si vous n'êtes pas sûr, commencez par ArrayList.


LinkedListet ArrayListsont deux implémentations différentes de l'interface List. LinkedListl'implémente avec une liste doublement liée. ArrayListl'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 O (n) (avec n / 4 pas en moyenne), mais O (1) quand index = 0ou index = list.size() - 1(dans ce cas, vous pouvez également utiliser getFirst()et getLast()). L'un des principaux avantages de LinkedList<E>
  • add(int index, E element)est O (n) (avec n / 4 pas en moyenne), mais O (1) quand index = 0ou index = list.size() - 1(dans ce cas, vous pouvez également utiliser addFirst()et addLast()/ add()). L'un des principaux avantages de LinkedList<E>
  • remove(int index)est O (n) (avec n / 4 pas en moyenne), mais O (1) quand index = 0ou index = list.size() - 1(dans ce cas, vous pouvez également utiliser removeFirst()et removeLast()). L'un des principaux avantages de LinkedList<E>
  • Iterator.remove()est O (1) . L'un des principaux avantages de LinkedList<E>
  • ListIterator.add(E element)est O (1) . L'un des principaux avantages de LinkedList<E>

Remarque: De nombreuses opérations nécessitent en moyenne n / 4 étapes, un nombre constant 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) amorti, mais O (n) dans le pire des cas puisque le tableau doit être redimensionné et copié
  • add(int index, E element)est O (n) (avec n / 2 pas en moyenne)
  • remove(int index)est O (n) (avec n / 2 pas en moyenne)
  • Iterator.remove()est O (n) (avec n / 2 pas en moyenne)
  • ListIterator.add(E element)est O (n) (avec n / 2 pas en moyenne)

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

LinkedList<E>permet des insertions ou des suppressions à temps constant à l' aide d'itérateurs , mais uniquement un accès séquentiel aux é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 proportionnel à la taille de la liste. Javadoc dit que "les opérations qui indexent dans la liste traverseront la liste du début ou de la fin, selon ce qui est le plus proche" , donc ces méthodes sont O (n) ( n / 4 étapes) en moyenne, bien que O (1) pour index = 0.

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

Ainsi, selon les opérations que vous envisagez 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 ArrayListest 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 de a LinkedListsurviennent lorsque vous réutilisez des itérateurs existants pour insérer et supprimer des éléments. Ces opérations peuvent ensuite être effectuées dans O (1) en modifiant la liste localement uniquement. Dans une liste de tableaux, le reste du tableau doit être déplacé (c'est-à-dire copié). D'un autre côté, la recherche d'un LinkedListmoyen suivant les liens dans O (n) ( n / 2 étapes) pour le pire des cas, alors que dans une ArrayListposition souhaitée peut être calculée mathématiquement et accessible dans O (1) .

Un autre avantage de l'utilisation de a LinkedListsurvient lorsque vous ajoutez ou supprimez de la tête de la liste, car ces opérations sont O (1) , alors qu'elles sont O (n) pour ArrayList. Notez que cela ArrayDequepeut être une bonne alternative à l' LinkedListajout et au retrait de la tête, mais ce n'est pas un List.

De plus, 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 LinkedLista plus de surcharge, car les pointeurs vers les éléments suivants et précédents sont également stockés. ArrayListsn'ont pas ces frais généraux. Cependant, ArrayListsoccupez 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 ArrayListest assez petite (10 de Java 1.4 - 1.8). Mais comme 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 ArrayListavec une capacité initiale plus élevée.

Jonathan Tran
la source
183
J'ai oublié de mentionner les frais d'insertion. Dans une LinkedList, une fois que vous avez la bonne position, l'insertion coûte O (1), tandis que dans une ArrayList elle monte à O (n) - tous les éléments au-delà du point d'insertion doivent être déplacés.
David Rodríguez - dribeas
26
En ce qui concerne l'utilisation de Vector: il n'est vraiment pas nécessaire de recourir à Vector. Pour ce faire, utilisez l'implémentation de votre liste préférée et un appel à synchronizedList pour lui donner un wrapper synchronisé. Voir: java.sun.com/docs/books/tutorial/collections/implementations/…
Ryan Cox
69
Non, pour une LinkedList, get est toujours O (n) même si vous connaissez la position, car pour arriver à cette position, l'implémentation sous-jacente doit parcourir les pointeurs "suivants" de la liste liée pour arriver à la valeur de cette position. L'accès aléatoire n'existe pas. Pour la position 2, marcher sur les pointeurs pourrait être bon marché, mais pour la position 1 million, pas si bon marché. Le fait est que c'est proportionnel à la position, ce qui signifie que c'est O (n).
Jonathan Tran
53
@Kevin Il peut être important que la mémoire soit "rapprochée". Le matériel mettra en cache des blocs de mémoire contigus (RAM dynamique) dans une RAM statique plus rapide dans le cache L1 ou L2. En théorie et la plupart du temps pratiquement, la mémoire peut être traitée comme un accès aléatoire. Mais en réalité, la lecture séquentielle de la mémoire sera légèrement plus rapide que dans un ordre aléatoire. Pour une boucle critique en termes de performances, cela peut être important. Ils l'appellent «localité spatiale» ou localité de référence .
Jonathan Tran
92
Il n'y a rien de tel que O(n/2)ou O(n/4). La grande notation O vous indique comment une opération évolue avec un n plus grand . et une opération nécessitant des n/2étapes évolue exactement comme une opération nécessitant des nétapes, ce qui explique pourquoi les sommations ou facteurs constants sont supprimés. O(n/2)et O(n/4)sont tous deux justes O(n). LinkedListet ArrayListont de toute façon différents facteurs constants, de sorte qu'il ne serait pas logique de comparer l'un O(n/2)de l'un avec O(n/4)l'autre, les deux dénotent simplement des opérations de mise à l'échelle linéaire.
Holger
630

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 a LinkedListest "beaucoup plus" qu'un an ArrayList, j'ai donc effectué un certain nombre de calculs pour démontrer exactement combien les deux listes occupent pour N références nulles.

Étant donné que 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 LinkedListset ArrayLists.

Remarque: Les tailles indiquées pour les ArrayListlignes sont pour les listes découpées - En pratique, la capacité du tableau de sauvegarde dans un ArrayListest généralement plus grande que son nombre d'éléments actuel.

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


Graphique de LinkedList et ArrayList Nombre d'éléments x octets


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

Les formules que j'ai utilisées suivent, faites-moi savoir si j'ai fait quelque chose de mal et je vais le réparer. «b» est soit 4 ou 8 pour les systèmes 32 ou 64 bits, et «n» est le nombre d'éléments. Notez que la raison des mods est que tous les objets en java prendront un multiple de 8 octets, qu'ils soient tous utilisés ou non.

Liste des tableaux:

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)

Numeron
la source
2
Assez intéressant de voir que LinkedList nécessite autant de mémoire que ArrayList pour stocker un seul élément. Quelle intuition! Que se passe-t-il si vous exécutez votre exemple avec -XX: + UseCompressedOops?
jontejj
215
Le problème avec vos mathématiques est que votre graphique exagère considérablement l'impact. Vous modélisez des objets qui ne contiennent chacun qu'un int, donc 4 ou 8 octets de données. Dans la liste chaînée, il y a essentiellement 4 "mots" de surcharge. Votre graphique donne ainsi l'impression que les listes liées utilisent "cinq fois" le stockage des listes de tableaux. C'est faux. La surcharge est de 16 ou 32 octets par objet, en tant qu'ajustement additif, et non comme facteur d'échelle.
Heath Hunnicutt
6
Aucun des objets ArrayList / LinkedList / Node ne contient uniquement un int, donc je ne comprends pas ce que vous dites là. J'ai reformulé 'overhead d'objet' en 'en-tête d'objet' pour clarfy - il y a un en-tête de 8 octets pour chaque objet quel que soit le système, et oui qui inclut tous les objets Node dans LinkedList, qui sont tous comptés correctement autant que je peux dire. Soit dit en passant, en le regardant à nouveau, j'ai trouvé quelques autres problèmes avec mes calculs dans LinkedList, ce qui aggrave la division et ArrayList . Je suis heureux de continuer à le mettre à jour, alors n'hésitez pas à clarifier et à élaborer davantage.
Numeron
6
Il convient de noter que CompressedOopsest maintenant par défaut dans tous les JDKs récents (7, 8 et mises à jour de 6 pour quelques années), de sorte que 64 bits ne sera pas faire une différence dans ArrayListou LinkedListtailles, à moins que vous avez explicitement désactivé oops comprimé pour quelque raison.
BeeOnRope
1
@jontejj l'augmentation de capacité par défaut est de 50%, donc lorsque vous remplissez un ArrayListsans spécifier de capacité initiale, il utilisera toujours beaucoup moins de mémoire qu'un LinkedList.
Holger
244

ArrayListc'est ce que tu veux. LinkedListest presque toujours un bogue (de performance).

Pourquoi LinkedListsuce:

  • Il utilise de nombreux petits objets mémoire et a donc un impact sur les performances tout au long du processus.
  • Beaucoup de petits objets sont mauvais pour la localité du cache.
  • Toute opération indexée nécessite une traversée, c'est-à-dire a des performances O (n). Ce n'est pas évident dans le code source, ce qui conduit à des algorithmes O (n) plus lents que s'ils ArrayListétaient utilisés.
  • Obtenir de bonnes performances est délicat.
  • Même lorsque les performances du 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 LinkedListdans la source car c'est probablement le mauvais choix.
Tom Hawtin - sellerie
la source
237
Désolé. vous a marqué. LinkedList ne craint pas. Dans certaines situations, LinkedList est la classe correcte à utiliser. Je suis d'accord qu'il n'y a pas beaucoup de situations où c'est mieux qu'un arrayliste, mais elles existent. Éduquez les gens qui font des choses stupides!
David Turner
40
Désolé de voir que vous avez obtenu beaucoup de votes négatifs pour cela. Il y a en effet très peu de raisons d'utiliser LinkedList de Java. En plus des mauvaises performances, il utilise également beaucoup plus de mémoire que les autres classes List concrètes (chaque nœud a deux pointeurs supplémentaires et chaque nœud est un objet wrapper séparé avec les octets de surcharge supplémentaires qui vont avec).
Kevin Brock
42
C'est l'une des réponses les plus utiles ici. C'est dommage tant de programmeurs ne parviennent pas à comprendre (a) la différence entre les types de données abstraits et les implémentations concrètes, et (b) l'importance réelle des facteurs constants et des surcharges de mémoire dans la détermination des performances.
Porculus
50
-1: Ceci est une vue plutôt aveuglée. Oui, c'est vrai qu'ArrayList est un outil très polyvalent. Cependant, il a ses limites. Il y a des cas où cela vous causera des problèmes et vous devrez utiliser LinkedList. Bien sûr, c'est une solution très spécialisée et, comme tout outil spécialisé, dans la plupart des cas, il est surpassé par un outil polyvalent. Mais cela ne signifie pas qu'il "suce" ou quelque chose comme ça, il suffit de savoir quand l'utiliser.
Malcolm
27
@DavidTurner: Ils existent, mais je pense que le point de Tom était que si vous devez demander, vous voulez probablement ArrayList.
user541686
139

En tant que personne qui fait de l'ingénierie de performance opérationnelle sur des services Web SOA à très grande échelle depuis environ une décennie, je préférerais le comportement de LinkedList à 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 d'ArrayList sous pression pourrait conduire les applications d'un cluster à étendre leurs baies en quasi synchronicité et pour les grandes tailles de baies pourrait conduire à un manque de réactivité dans 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 à partir du ramasse-miettes par défaut, mais une fois que vous obtenez des applications java avec des tas de 10 Go, vous pouvez finir par verrouiller l'application pendant 25 secondes pendant un GC complet, ce qui provoque des délais d'attente et des échecs dans les applications SOA et souffle vos SLA si cela se produit 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 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. D'après mon expérience dans mon travail, je ne peux pas ignorer la pire latence.

lamont
la source
8
Une autre solution ne gérerait-elle pas la taille de la liste par programme en utilisant la méthode EnsureCapacity () d'ArrayList? Ma question est pourquoi tant de choses sont-elles stockées dans un tas de structures de données fragiles alors qu'elles pourraient mieux être stockées dans un mécanisme de mise en cache ou db? L'autre jour, j'ai eu une interview où ils ont juré de haut en bas sur les maux d'ArrayList, mais je viens ici et je trouve que l'analyse de la complexité est meilleure partout! GRAND POINT DE DISCUSSION, BIEN QUE. MERCI!
ingyhere
22
une fois que vous obtenez des applications java avec des tas de 10 Go, vous pouvez terminer le verrouillage de l'application pendant 25 secondes pendant un GC complet, ce qui provoque des délais d'attente En fait, avec LinkedList vous assassinez le garbage collector pendant les GC complets, il doit itérer la trop grande LinkedList avec cache manquant chaque nœud.
bestsss
5
C'est ... une horrible solution. vous êtes fondamentalement tributaire du nettoyage du GC pour vous, ce qui est incroyablement cher, quand vous pouvez simplement appeler assureCapacity () sur un arraylist à la place ...
Philip Devine
5
@Andreas: A alloue LinkedList toujours cinq fois plus de mémoire qu'un simple tableau de références, donc un ArrayList2,5 fois temporairement nécessaire consomme toujours beaucoup moins de mémoire, même si la mémoire n'est pas récupérée. Étant donné que l'allocation de grandes baies contourne l'espace Eden, elles n'ont aucun impact sur le comportement du GC, à moins qu'il n'y ait vraiment pas assez de mémoire, auquel cas, elles ont LinkedListexplosé beaucoup plus tôt…
Holger
5
@Andreas L'autre problème est de savoir comment la mémoire est allouée. LinkedListn'a besoin que d'un petit morceau de mémoire libre pour allouer à l'élément suivant. ArrayListaura besoin d'un grand espace libre et continu pour allouer le tableau redimensionné. Si le tas est fragmenté, le GC peut finir par réorganiser le tas entier juste pour libérer un seul bloc de mémoire approprié.
Piotr Kusmierczyk
128
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

Les listes de tableaux sont bonnes pour les écritures à lecture unique ou les ajouteurs, mais mauvaises pour ajouter / supprimer à l'avant ou au milieu.

Michael Munsey
la source
42
Vous ne pouvez pas comparer directement les valeurs big-O sans penser à des facteurs constants. Pour les petites listes (et la plupart des listes sont petites), O (N) d'ArrayList est plus rapide que O (1) de LinkedList.
Porculus
4
Je ne me soucie pas des performances des petites listes, et mon ordinateur non plus, sauf s'il est utilisé en boucle d'une manière ou d'une autre.
Maarten Bodewes
45
LinkedList ne peut pas vraiment insérer au milieu O(1). Il doit parcourir la moitié de la liste pour trouver le point d'insertion.
Thomas Ahle
8
LinkedList: insérer au milieu O (1) - est faux! J'ai découvert que même l'insertion en 1 / 10ème position de la taille LinkedList est plus lente que l'insertion d'un élément en 1 / 10ème position d'un ArrayList. Et pire encore: la fin de la collecte. l'insertion dans les dernières positions (pas la toute dernière) d'ArrayList est plus rapide que dans les dernières positions (pas la toute dernière) de LinkedList
kachanov
14
@kachanov L'insertion dans un LinkedList est O(1) si vous avez un itérateur à la position d'insertion , c'est ListIterator.add-à- dire est censé être O(1)pour un LinkedList.
A QUIT - Anony-Mousse
107

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

LinkedList est presque toujours le mauvais choix, en termes de performances. Il existe des algorithmes très spécifiques pour lesquels une LinkedList est requise, mais ceux-ci sont très, très rares et l'algorithme dépend généralement 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 surpasse ArrayList: celui d'une file d'attente. Cependant, si votre objectif est la performance, au lieu de LinkedList, vous devriez également envisager d'utiliser un ArrayBlockingQueue (si vous pouvez déterminer à l'avance une limite supérieure sur la taille de votre file d'attente et pouvez vous permettre d'allouer toute la mémoire à l'avance), ou cette implémentation CircularArrayList . (Oui, il s'agit de 2001, vous devrez donc le générer, mais j'ai obtenu des ratios de performances comparables à ceux cités dans l'article dans une récente JVM)

Daniel Martin
la source
39
Depuis Java 6, vous pouvez utiliser ArrayDeque. docs.oracle.com/javase/6/docs/api/java/util/ArrayDeque.html
Thomas Ahle
1
ArrayDequeest plus lent qu'à LinkedListmoins que toutes les opérations soient à la même fin. C'est OK lorsqu'il est utilisé comme une pile mais cela ne fait pas une bonne file d'attente.
Jeremy List
2
Faux - au moins pour l'implémentation d'Oracle dans jdk1.7.0_60 et dans le test suivant. J'ai créé un test où je boucle 10 millions de fois et j'ai un Deque de 10 millions d'entiers aléatoires. À l'intérieur de la boucle, j'interroge un élément et propose un élément constant. Sur mon ordinateur, LinkedList est plus de 10 fois plus lent qu'ArrayDeque et utilise moins de mémoire). La raison est que, contrairement à ArrayList, ArrayDeque conserve un pointeur vers la tête du tableau afin qu'il ne doive pas déplacer tous les éléments lorsque la tête est supprimée.
Henno Vermeulen
6
ArrayDequeest susceptible d'être plus rapide que Stacklorsqu'il est utilisé comme une pile, et plus rapide que LinkedListlorsqu'il est utilisé comme une file d'attente.
akhil_mittal
3
Notez que le commentaire de akhil_mittal est une citation de la ArrayDequedocumentation.
Stuart marque
65

C'est une question d'efficacité. LinkedListest rapide pour ajouter et supprimer des éléments, mais lent pour accéder à un élément spécifique. ArrayListest rapide pour accéder à un élément spécifique mais peut être lent à ajouter aux deux extrémités, et particulièrement lent à supprimer au milieu.

Array vs ArrayList vs LinkedList vs Vector va plus en profondeur, tout comme la liste liée .

dgtized
la source
54

Correct ou incorrect: veuillez exécuter le test localement et décider par vous-même!

Modifier / Supprimer est plus rapide LinkedListque ArrayList.

ArrayList, soutenu par Array, qui doit être le double de la taille, est pire dans les applications à grand volume.

Vous trouverez ci-dessous le résultat du test unitaire pour chaque opération. La synchronisation est donnée en nanosecondes.


Operation                       ArrayList                      LinkedList  

AddAll   (Insert)               101,16719                      2623,29291 

Add      (Insert-Sequentially)  152,46840                      966,62216

Add      (insert-randomly)      36527                          29193

remove   (Delete)               20,56,9095                     20,45,4904

contains (Search)               186,15,704                     189,64,981

Voici le code:

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

public class ArrayListVsLinkedList {
    private static final int MAX = 500000;
    String[] strings = maxArray();

    ////////////// ADD ALL ////////////////////////////////////////
    @Test
    public void arrayListAddAll() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        arrayList.addAll(stringList);
        watch.totalTime("Array List addAll() = ");//101,16719 Nanoseconds
    }

    @Test
    public void linkedListAddAll() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);

        watch.start();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);
        watch.totalTime("Linked List addAll() = ");  //2623,29291 Nanoseconds
    }

    //Note: ArrayList is 26 time faster here than LinkedList for addAll()

    ///////////////// INSERT /////////////////////////////////////////////
    @Test
    public void arrayListAdd() {
        Watch watch = new Watch();
        List<String> arrayList = new ArrayList<String>(MAX);

        watch.start();
        for (String string : strings)
            arrayList.add(string);
        watch.totalTime("Array List add() = ");//152,46840 Nanoseconds
    }

    @Test
    public void linkedListAdd() {
        Watch watch = new Watch();

        List<String> linkedList = new LinkedList<String>();
        watch.start();
        for (String string : strings)
            linkedList.add(string);
        watch.totalTime("Linked List add() = ");  //966,62216 Nanoseconds
    }

    //Note: ArrayList is 9 times faster than LinkedList for add sequentially

    /////////////////// INSERT IN BETWEEN ///////////////////////////////////////

    @Test
    public void arrayListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX + MAX / 10);
        arrayList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        arrayList.add(insertString0);
        arrayList.add(insertString1);
        arrayList.add(insertString2);
        arrayList.add(insertString3);

        watch.totalTime("Array List add() = ");//36527
    }

    @Test
    public void linkedListInsertOne() {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(stringList);

        String insertString0 = getString(true, MAX / 2 + 10);
        String insertString1 = getString(true, MAX / 2 + 20);
        String insertString2 = getString(true, MAX / 2 + 30);
        String insertString3 = getString(true, MAX / 2 + 40);

        watch.start();

        linkedList.add(insertString0);
        linkedList.add(insertString1);
        linkedList.add(insertString2);
        linkedList.add(insertString3);

        watch.totalTime("Linked List add = ");//29193
    }


    //Note: LinkedList is 3000 nanosecond faster than ArrayList for insert randomly.

    ////////////////// DELETE //////////////////////////////////////////////////////
    @Test
    public void arrayListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.remove(searchString0);
        arrayList.remove(searchString1);
        watch.totalTime("Array List remove() = ");//20,56,9095 Nanoseconds
    }

    @Test
    public void linkedListRemove() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.remove(searchString0);
        linkedList.remove(searchString1);
        watch.totalTime("Linked List remove = ");//20,45,4904 Nanoseconds
    }

    //Note: LinkedList is 10 millisecond faster than ArrayList while removing item.

    ///////////////////// SEARCH ///////////////////////////////////////////
    @Test
    public void arrayListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> stringList = Arrays.asList(strings);
        List<String> arrayList = new ArrayList<String>(MAX);

        arrayList.addAll(stringList);
        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        arrayList.contains(searchString0);
        arrayList.contains(searchString1);
        watch.totalTime("Array List addAll() time = ");//186,15,704
    }

    @Test
    public void linkedListSearch() throws Exception {
        Watch watch = new Watch();
        List<String> linkedList = new LinkedList<String>();
        linkedList.addAll(Arrays.asList(strings));

        String searchString0 = getString(true, MAX / 2 + 10);
        String searchString1 = getString(true, MAX / 2 + 20);

        watch.start();
        linkedList.contains(searchString0);
        linkedList.contains(searchString1);
        watch.totalTime("Linked List addAll() time = ");//189,64,981
    }

    //Note: Linked List is 500 Milliseconds faster than ArrayList

    class Watch {
        private long startTime;
        private long endTime;

        public void start() {
            startTime = System.nanoTime();
        }

        private void stop() {
            endTime = System.nanoTime();
        }

        public void totalTime(String s) {
            stop();
            System.out.println(s + (endTime - startTime));
        }
    }


    private String[] maxArray() {
        String[] strings = new String[MAX];
        Boolean result = Boolean.TRUE;
        for (int i = 0; i < MAX; i++) {
            strings[i] = getString(result, i);
            result = !result;
        }
        return strings;
    }

    private String getString(Boolean result, int i) {
        return String.valueOf(result) + i + String.valueOf(!result);
    }
}
Cendre
la source
1
Pour être précis, ArrayList n'a pas besoin d'être doublé. Veuillez d'abord vérifier les sources.
Danubian Sailor
Il est à noter que votre exemple est imparfait ... Vous supprimez de la chaîne entre: 18 + [2, 12] octets ("true0false", "true500000false"), en moyenne 25 octets, qui sont les tailles des éléments au milieu. Il est connu que lorsque la taille des octets augmente, la liste liée fonctionne mieux, à mesure que la taille de la liste augmente, un tableau contigu (liste) fera mieux. Plus important encore, vous faites .equals () sur des chaînes - ce qui n'est pas une opération bon marché. Si vous utilisiez plutôt des entiers, je pense qu'il y aurait une différence.
Centril
2
"... est pire dans les applications à grand volume ": il s'agit d'un malentendu. LinkedLista beaucoup plus de mémoire car pour chaque élément il y a un objet nœud avec cinq champs. Sur de nombreux systèmes, cela représente une surcharge de 20 octets. La surcharge de mémoire moyenne par élément pour ArrayListest un mot et demi, ce qui fait 6 octets et 8 octets dans le pire des cas.
Lii
1
J'ai fait une meilleure version de votre référence ici, avec des résultats - les performances d'ajout pour la liste d'arraylist sont artificiellement faibles pour la vôtre, car addAll donne un tableau de stockage de taille initiale EXACTEMENT, donc la première insertion déclenche toujours un arraycopy. En outre, cela inclut des cycles de préchauffage pour permettre la compilation JIT avant la collecte des données.
BobMcGee
4
@BillK depuis Java 8, vous pouvez utiliser removeIf(element -> condition)où il convient, ce qui peut être considérablement plus rapide pour an ArrayList, par rapport au bouclage et à la suppression via l'itérateur, car il n'est pas nécessaire de déplacer le reste entier pour chaque élément individuel. Que cela fonctionne mieux ou moins bien que cela LinkedListdépend du scénario particulier, comme LinkedListest O (1) en théorie, mais la suppression d'un seul nœud nécessite plusieurs accès à la mémoire, ce qui peut facilement dépasser le nombre nécessaire pour la ArrayListlors de la suppression d'un nombre significatif d'éléments .
Holger
50

ArrayListest essentiellement un tableau. LinkedListest implémenté comme une double liste chaînée.

C'est getassez clair. O (1) pour ArrayList, car ArrayListautoriser l'accès aléatoire à l'aide de l'index. O (n) pour LinkedList, car il doit d'abord trouver l'index. Remarque: il existe différentes versions de addet remove.

LinkedListest plus rapide à ajouter et à supprimer, mais plus lent à obtenir. En bref, LinkedListdevrait être préféré si:

  1. il n'y a pas un grand nombre d'accès aléatoire à l'élément
  2. il existe un grand nombre d'opérations d'ajout / suppression

=== ArrayList ===

  • ajouter (E e)
    • ajouter à la fin de ArrayList
    • nécessitent un coût de redimensionnement de la mémoire.
    • O (n) pire, O (1) amorti
  • add (index int, élément E)
    • ajouter à une position d'index spécifique
    • nécessitent un décalage et un éventuel redimensionnement de la mémoire
    • Sur)
  • supprimer (index int)
    • supprimer un élément spécifié
    • nécessitent un décalage et un éventuel redimensionnement de la mémoire
    • Sur)
  • supprimer (objet o)
    • supprimer la première occurrence de l'élément spécifié de cette liste
    • besoin de rechercher l'élément d'abord, puis de déplacer et le coût de redimensionnement de la mémoire possible
    • Sur)

=== LinkedList ===

  • ajouter (E e)

    • ajouter à la fin de la liste
    • O (1)
  • add (index int, élément E)

    • insérer à la position spécifiée
    • besoin de trouver la position en premier
    • Sur)
  • retirer()
    • supprimer le premier élément de la liste
    • O (1)
  • supprimer (index int)
    • supprimer l'élément avec l'index spécifié
    • besoin de trouver l'élément en premier
    • Sur)
  • supprimer (objet o)
    • supprime la première occurrence de l'élément spécifié
    • besoin de trouver l'élément en premier
    • Sur)

Voici une figure de programcreek.com ( addet removesont le premier type, c'est-à-dire, ajoutez un élément à la fin de la liste et supprimez l'élément à la position spécifiée dans la liste.):

entrez la description de l'image ici

Ryan
la source
3
"LinkedList est plus rapide que d'ajouter / supprimer". Incorrect, vérifiez la réponse ci-dessus stackoverflow.com/a/7507740/638670
Nerrve
49

Joshua Bloch, l'auteur de LinkedList:

Quelqu'un utilise-t-il réellement LinkedList? Je l'ai écrit et je ne l'utilise jamais.

Lien: https://twitter.com/joshbloch/status/583813919019573248

Je suis désolé que la réponse ne soit pas aussi informative que les autres réponses, mais je pensais que ce serait la plus intéressante et la plus explicite.

Ruslan
la source
34

ArrayListest accessible au hasard, alors qu'il LinkedListest vraiment bon marché de développer et de supprimer des éléments. Dans la plupart des cas, ArrayListc'est bien.

À moins d'avoir créé de grandes listes et mesuré un goulot d'étranglement, vous n'aurez probablement jamais à vous soucier de la différence.

Dustin
la source
15
LinkedList n'est pas bon marché pour ajouter des éléments. Il est presque toujours plus rapide d'ajouter un million d'éléments à une ArrayList que de les ajouter à une LinkedList. Et la plupart des listes dans le code du monde réel ne font même pas un million d'éléments.
Porculus
10
À tout moment, vous connaissez le coût de l'ajout d'un élément à votre LinkedList. L'ArrayList que vous n'avez pas (en général). L'ajout d'un seul élément à une ArrayList contenant un million d'éléments peut prendre très longtemps - c'est une opération O (n) plus le double du stockage, sauf si vous avez préalloué de l'espace. L'ajout d'un élément à une LinkedList est O (1). Ma dernière déclaration est valable.
Dustin
4
L'ajout d'un seul élément à une ArrayList est O (1), qu'il s'agisse de 1 million ou 1 milliard. L'ajout d'un élément à une LinkedList est également O (1). "Ajouter" signifie AJOUTER À LA FIN.
kachanov
Vous devez avoir lu l'implémentation différemment de moi. D'après mon expérience, la copie d'un tableau d'un milliard d'éléments prend plus de temps que la copie d'un tableau d'un million d'éléments.
Dustin
6
@kachanov, vous devez mal comprendre Dustin. À moins que vous n'ayez déclaré un tableau d'un milliard d'éléments, vous devrez éventuellement redimensionner votre tableau, auquel cas vous devrez copier tous les éléments dans un nouveau tableau plus grand, d'où parfois vous obtiendrez O (N) mais avec une liste chaînée, vous aurez toujours obtenir O (1)
Stan R.
29

TL; DR en raison de l'architecture informatique moderne, ArrayListsera considérablement plus efficace pour presque tous les cas d'utilisation possibles - et LinkedListdoit donc être évité, sauf dans certains cas très uniques et extrêmes.


En théorie, LinkedList a un O (1) pour le add(E element)

L'ajout d'un élément au milieu d'une liste devrait également être très efficace.

La pratique est très différente, puisque LinkedList est une structure de cache de données hostiles . Du POV de performance - il y a très peu de cas où les LinkedListperformances pourraient être meilleures que celles compatibles avec le cacheArrayList .

Voici les résultats d'un test de référence insérant des éléments dans des emplacements aléatoires. Comme vous pouvez le voir - la liste des tableaux est beaucoup plus efficace, bien qu'en théorie chaque insertion au milieu de la liste nécessite de "déplacer" les n derniers éléments du tableau (les valeurs inférieures sont meilleures):

entrez la description de l'image ici

Travailler sur un matériel de dernière génération (caches plus gros et plus efficaces) - les résultats sont encore plus concluants:

entrez la description de l'image ici

LinkedList prend beaucoup plus de temps pour accomplir le même travail. code source source

Il y a deux raisons principales pour cela:

  1. Principalement - que les nœuds du LinkedListsont dispersés au hasard dans la mémoire. La RAM ("Random Access Memory") n'est pas vraiment aléatoire et des blocs de mémoire doivent être récupérés pour être mis en cache. Cette opération prend du temps, et lorsque ces récupérations se produisent fréquemment - les pages de mémoire dans le cache doivent être remplacées tout le temps -> Le cache manque -> Le cache n'est pas efficace. ArrayListles éléments sont stockés dans une mémoire continue, ce qui est exactement ce que l'architecture CPU moderne optimise.

  2. Secondaire LinkedList requis pour retenir les pointeurs arrière / avant, ce qui signifie 3 fois la consommation de mémoire par valeur stockée par rapport à ArrayList.

DynamicIntArray , btw, est une mise en œuvre personnalisée d'ArrayList Int(type primitif) et non des objets - par conséquent, toutes les données sont réellement stockées de manière adjacente - donc encore plus efficace.

Un élément clé à retenir est que le coût de l'extraction d'un bloc de mémoire est plus important que le coût d'accès à une seule cellule de mémoire. C'est pourquoi le lecteur 1 Mo de mémoire séquentielle est jusqu'à 400 fois plus rapide que la lecture de cette quantité de données à partir de différents blocs de mémoire:

Latency Comparison Numbers (~2012)
----------------------------------
L1 cache reference                           0.5 ns
Branch mispredict                            5   ns
L2 cache reference                           7   ns                      14x L1 cache
Mutex lock/unlock                           25   ns
Main memory reference                      100   ns                      20x L2 cache, 200x L1 cache
Compress 1K bytes with Zippy             3,000   ns        3 us
Send 1K bytes over 1 Gbps network       10,000   ns       10 us
Read 4K randomly from SSD*             150,000   ns      150 us          ~1GB/sec SSD
Read 1 MB sequentially from memory     250,000   ns      250 us
Round trip within same datacenter      500,000   ns      500 us
Read 1 MB sequentially from SSD*     1,000,000   ns    1,000 us    1 ms  ~1GB/sec SSD, 4X memory
Disk seek                           10,000,000   ns   10,000 us   10 ms  20x datacenter roundtrip
Read 1 MB sequentially from disk    20,000,000   ns   20,000 us   20 ms  80x memory, 20X SSD
Send packet CA->Netherlands->CA    150,000,000   ns  150,000 us  150 ms

Source: chiffres de latence que chaque programmeur devrait connaître

Juste pour rendre le point encore plus clair, veuillez vérifier la référence de l'ajout d'éléments au début de la liste. C'est un cas d'utilisation où, en théorie, le LinkedListdevrait vraiment briller, et ArrayListdevrait présenter des résultats médiocres ou pire encore:

entrez la description de l'image ici

Remarque: il s'agit d'une référence de la bibliothèque C ++ Std, mais mon expérience précédente a montré que les résultats C ++ et Java sont très similaires. Code source

Copier une masse séquentielle de mémoire est une opération optimisée par les processeurs modernes - changer la théorie et rendre, encore une fois, ArrayList/ Vectorbeaucoup plus efficace


Crédits: Tous les benchmarks publiés ici sont créés par Kjell Hedström . Encore plus de données peuvent être trouvées sur son blog

Lior Bar-On
la source
Je n'appellerais pas une file d'attente unique ou extrême! Une file d'attente fifo est beaucoup plus facile à implémenter sur une LinkedList au lieu d'une ArrayList. C'est en fait un cauchemar sur une ArrayList car vous devez suivre votre propre démarrage, arrêter et faire votre propre réallocation, vous pourriez aussi bien utiliser un tableau, mais une liste liée est un fifo. Je ne suis pas sûr de l'implémentation de Java, mais une LinkedList peut faire O (1) pour les opérations de file d'attente et de retrait de file d'attente (nécessite un pointeur spécial sur l'élément de queue pour la suppression, ce que je suppose que java a mais je n'ai pas revérifié .)
Projet de loi K du
24

Si votre code a add(0)et remove(0), utilisez un LinkedListet c'est plus joli addFirst()et des removeFirst()méthodes. Sinon, utilisez ArrayList.

Et bien sûr, Guava 's ImmutableList est votre meilleur ami.

Jesse Wilson
la source
3
Pour les petites listes, ArrayList.add (0) va toujours toujours être plus rapide que LinkedList.addFirst ().
Porculus
1
@Porculus J'entends constamment cet argument selon lequel pour les petites listes, ArrayList.add (0) sera plus rapide, ce petit est combien petit? 10 éléments, 10 millions,?
garg10mai
1
@ garg10may small est inférieur à 10.
Jesse Wilson
@Porculus small signifie moins que la capacité maximale du tableau interne sous-jacent à ArrayList.
Janac Meena
21

Je sais que c'est un ancien poste, mais honnêtement, je ne peux pas croire que personne n'ait mentionné qu'il LinkedListimplémente Deque. Regardez simplement les méthodes dans Deque(et Queue); si vous voulez une comparaison juste, essayez de courir LinkedListcontre ArrayDequeet faites une comparaison fonctionnalité par fonctionnalité.

Ajax
la source
18

Voici la notation Big-O à la fois ArrayListet LinkedListet aussi CopyOnWrite-ArrayList:

Liste des tableaux

get                 O(1)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

LinkedList

get                 O(n)
add                 O(1)
contains            O(n)
next                O(1)
remove              O(1)
iterator.remove     O(1)

CopyOnWrite-ArrayList

get                 O(1)
add                 O(n)
contains            O(n)
next                O(1)
remove              O(n)
iterator.remove     O(n)

Sur cette base, vous devez décider quoi choisir. :)

Rajith Delantha
la source
9
>>>> ArrayList add -> O (1) <- not tru. Dans certains cas, ArrayList devra se développer pour ajouter un élément de plus
kachanov
1
La suppression de LinkedList n'est pas O (1), il faudrait rechercher l'élément à supprimer, donc le pire des cas O (n) et O moyen (n / 2)
garg10mai
Ni l'un ni l'autre LinkedList.add(), bien que la plupart des réponses ici le disent.
Marquis de Lorne
18

Comparons LinkedList et ArrayList par rapport aux paramètres ci-dessous:

1. Mise en œuvre

ArrayList est l'implémentation de tableau redimensionnable de l'interface de liste, tandis que

LinkedList est l'implémentation de liste à double liaison de l'interface de liste.


2. Performance

  • get (int index) ou opération de recherche

    L'opération ArrayList get (int index) s'exécute en temps constant, c'est-à-dire O (1) tandis que

    La durée d'exécution de l'opération LinkedList get (int index) est O (n).

    La raison pour laquelle ArrayList est plus rapide que LinkedList est que ArrayList utilise un système basé sur un index pour ses éléments car il utilise en interne une structure de données de tableau, d'autre part,

    LinkedList ne fournit pas d'accès basé sur l'index pour ses éléments car il itère depuis le début ou la fin (selon ce qui est le plus proche) pour récupérer le nœud à l'index d'élément spécifié.

  • opération insert () ou add (Object)

    Les insertions dans LinkedList sont généralement rapides par rapport à ArrayList. Dans LinkedList, l'ajout ou l'insertion est une opération O (1).

    Dans ArrayList , si le tableau est le cas complet, c'est-à-dire le pire des cas, il y a un coût supplémentaire de redimensionnement du tableau et de copie des éléments dans le nouveau tableau, ce qui rend l'exécution de l'opération d'ajout dans ArrayList O (n), sinon c'est O (1) .

  • supprimer l'opération (int)

    L'opération de suppression dans LinkedList est généralement la même que ArrayList, c'est-à-dire O (n).

    Dans LinkedList , il existe deux méthodes de suppression surchargées. on est remove () sans aucun paramètre qui supprime la tête de la liste et s'exécute en temps constant O (1). L'autre méthode de suppression surchargée dans LinkedList est remove (int) ou remove (Object) qui supprime l'objet ou l'int passé en tant que paramètre. Cette méthode parcourt la LinkedList jusqu'à ce qu'elle trouve l'objet et dissocie-le de la liste d'origine. Par conséquent, le temps d'exécution de cette méthode est O (n).

    Alors que dans la méthode ArrayList remove (int) implique la copie d'éléments de l'ancien tableau vers le nouveau tableau mis à jour, son exécution est donc O (n).


3. Itérateur inversé

LinkedList peut être itéré en sens inverse à l'aide de descendingIterator () tout en

il n'y a pas descendingIterator () dans ArrayList , nous devons donc écrire notre propre code pour itérer sur ArrayList en sens inverse.


4. Capacité initiale

Si le constructeur n'est pas surchargé, alors ArrayList crée une liste vide de capacité initiale 10, tandis que

LinkedList construit uniquement la liste vide sans aucune capacité initiale.


5. Overhead mémoire

La surcharge de la mémoire dans LinkedList est plus comparable à ArrayList car un nœud dans LinkedList doit conserver les adresses du nœud suivant et précédent. Tandis que

Dans ArrayList, chaque index ne contient que l'objet réel (données).


La source

Abhijeet Ashok Muneshwar
la source
18

J'utilise habituellement l'un sur l'autre en fonction de la complexité temporelle des opérations que j'effectuerais sur cette liste particulière.

|---------------------|---------------------|--------------------|------------|
|      Operation      |     ArrayList       |     LinkedList     |   Winner   |
|---------------------|---------------------|--------------------|------------|
|     get(index)      |       O(1)          |         O(n)       | ArrayList  |
|                     |                     |  n/4 steps in avg  |            |
|---------------------|---------------------|--------------------|------------|
|      add(E)         |       O(1)          |         O(1)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     | O(n) in worst case  |                    |            |
|---------------------|---------------------|--------------------|------------|
|    add(index, E)    |       O(n)          |         O(n)       | LinkedList |
|                     |     n/2 steps       |      n/4 steps     |            |
|                     |---------------------|--------------------|            |
|                     |                     |  O(1) if index = 0 |            |
|---------------------|---------------------|--------------------|------------|
|  remove(index, E)   |       O(n)          |         O(n)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     |     n/2 steps       |      n/4 steps     |            |
|---------------------|---------------------|--------------------|------------|
|  Iterator.remove()  |       O(n)          |         O(1)       | LinkedList |
|  ListIterator.add() |                     |                    |            |
|---------------------|---------------------|--------------------|------------|


|--------------------------------------|-----------------------------------|
|              ArrayList               |            LinkedList             |
|--------------------------------------|-----------------------------------|
|     Allows fast read access          |   Retrieving element takes O(n)   |
|--------------------------------------|-----------------------------------|
|   Adding an element require shifting | o(1) [but traversing takes time]  |
|       all the later elements         |                                   |
|--------------------------------------|-----------------------------------|
|   To add more elements than capacity |
|    new array need to be allocated    |
|--------------------------------------|
Gayan Weerakutti
la source
Le ArrayDeque équilibre un peu plus les choses vers les tableaux puisque l'insertion / suppression avant / arrière sont tous O (1) la seule chose sur laquelle Linked List gagne toujours est l'ajout / la suppression pendant la traversée (les opérations Iterator).
Bill K
14

En plus des autres bons arguments ci-dessus, vous devriez remarquer l' interface ArrayListimplements RandomAccess, tandis que LinkedListimplements Queue.

Donc, d'une manière ou d'une autre, ils abordent des problèmes légèrement différents, avec des différences d'efficacité et de comportement (voir leur liste de méthodes).

PhiLho
la source
10

Cela dépend des opérations que vous effectuerez le plus sur la liste.

ArrayListest plus rapide pour accéder à une valeur indexée. C'est bien pire lors de l'insertion ou de la suppression d'objets.

Pour en savoir plus, lisez tout article qui parle de la différence entre les tableaux et les listes liées.

Matthew Schinckel
la source
2
Pour en savoir plus, ne lisez pas, écrivez simplement le code. et vous découvrirez que l'implémentation d'ArrayList est plus rapide que LinkedList lors de l'insertion et de la suppression.
kachanov
8

Une liste de tableaux est essentiellement un tableau avec des méthodes pour ajouter des éléments, etc. (et vous devriez plutôt utiliser une liste générique). Il s'agit d'une collection d'éléments accessibles via un indexeur (par exemple [0]). Cela implique une progression d'un élément à l'autre.

Une liste liée spécifie une progression d'un élément à l'autre (élément a -> élément b). Vous pouvez obtenir le même effet avec une liste de tableaux, mais une liste liée indique absolument quel élément est censé suivre le précédent.

kemiller2002
la source
7

Une caractéristique importante d'une liste chaînée (que je n'ai pas lue dans une autre réponse) est la concaténation de deux listes. Avec un tableau c'est O (n) (+ surcharge de certaines réallocations) avec une liste chaînée c'est seulement O (1) ou O (2) ;-)

Important : pour Java, LinkedListce n'est pas vrai! Voir Existe - t-il une méthode de concaténation rapide pour la liste chaînée en Java?

Karussell
la source
2
Comment c'est? Cela peut être vrai avec des structures de données de liste liée, mais pas avec un objet Java LinkList. Vous ne pouvez pas simplement pointer un nextd'une liste vers le premier nœud de la deuxième liste. La seule façon est d'utiliser addAll()qui ajoute des éléments de manière séquentielle, bien que ce soit mieux que de parcourir et d'appeler add()chaque élément. Pour ce faire rapidement dans O (1), vous auriez besoin d'une classe de composition (comme org.apache.commons.collections.collection.CompositeCollection), mais cela fonctionnerait pour tout type de liste / collection.
Kevin Brock
Oui c'est vrai. J'ai modifié la réponse en conséquence. mais voyez cette réponse pour savoir comment le faire avec LinkedList: stackoverflow.com/questions/2494031/…
Karussell
7

ArrayList et LinkedList ont leurs propres avantages et inconvénients.

ArrayList utilise une adresse mémoire contiguë par rapport à LinkedList qui utilise des pointeurs vers le nœud suivant. Ainsi, lorsque vous souhaitez rechercher un élément dans une liste de tableaux est plus rapide que de faire n itérations avec LinkedList.

D'un autre côté, l'insertion et la suppression dans une LinkedList sont beaucoup plus faciles car il suffit de changer les pointeurs alors qu'une ArrayList implique l'utilisation d'une opération de décalage pour toute insertion ou suppression.

Si vous avez des opérations de récupération fréquentes dans votre application, utilisez une ArrayList. Si vous avez des insertions et des suppressions fréquentes, utilisez une LinkedList.

Nesan Mano
la source
6

J'ai lu les réponses, mais il y a un scénario où j'utilise toujours une LinkedList sur une ArrayList que je veux partager pour entendre des opinions:

Chaque fois que j'avais une méthode qui renvoie une liste de données obtenues à partir d'une base de données, j'utilise toujours une LinkedList.

Ma justification était que, comme il est impossible de savoir exactement combien de résultats j'obtiens, il n'y aura pas de perte de mémoire (comme dans ArrayList avec la différence entre la capacité et le nombre réel d'éléments), et il n'y aurait pas de temps perdu à essayer de dupliquer la capacité.

En ce qui concerne une ArrayList, je suis d'accord qu'au moins vous devriez toujours utiliser le constructeur avec la capacité initiale, afin de minimiser autant que possible la duplication des tableaux.

gaijinco
la source
5

ArrayListet LinkedListles outils List interface et leurs méthodes et résultats sont presque identiques. Cependant, il y a peu de différences entre elles qui se rendent meilleures les unes aux autres en fonction des besoins.

ArrayList contre LinkedList

1) l' Search: ArrayListopération de recherche est assez rapide par rapport à l' LinkedListopération de recherche. get(int index)in ArrayListdonne les performances de O(1)tandis que les LinkedListperformances sont O(n).

Reason: ArrayListmaintient un système basé sur l'index pour ses éléments car il utilise implicitement la structure des données du tableau, ce qui le rend plus rapide pour rechercher un élément dans la liste. D'un autre côté, LinkedListimplémente une liste doublement liée qui nécessite la traversée de tous les éléments pour rechercher un élément.

2) l' Deletion: LinkedListopération de suppression donne des O(1)performances tout en ArrayListoffrant des performances variables: O(n)dans le pire des cas (lors de la suppression du premier élément) et O(1)dans le meilleur des cas (lors de la suppression du dernier élément).

Conclusion: la suppression d'élément LinkedList est plus rapide que ArrayList.

Raison: chaque élément de LinkedList conserve deux pointeurs (adresses) qui pointent vers les deux éléments voisins de la liste. Par conséquent, la suppression ne nécessite que la modification de l'emplacement du pointeur dans les deux nœuds voisins (éléments) du nœud qui va être supprimé. Dans In ArrayList, tous les éléments doivent être décalés pour remplir l'espace créé par l'élément supprimé.

3) la Inserts Performance: LinkedListméthode add donne des O(1)performances tandis que ArrayListdonne O(n)dans le pire des cas. La raison est la même que celle expliquée pour la suppression.

4) Memory Overhead: ArrayListgère les index et les données des éléments tout en LinkedListconservant les données des éléments et deux pointeurs pour les nœuds voisins

par conséquent, la consommation de mémoire est relativement élevée dans LinkedList.

Il existe peu de similitudes entre ces classes, à savoir:

  • ArrayList et LinkedList sont tous deux des implémentations de l'interface List.
  • Ils conservent tous les deux l'ordre d'insertion des éléments, ce qui signifie qu'en affichant les éléments ArrayList et LinkedList, le jeu de résultats aurait le même ordre dans lequel les éléments ont été insérés dans la liste.
  • Ces deux classes ne sont pas synchronisées et peuvent être synchronisées explicitement à l'aide de la méthode Collections.synchronizedList.
  • Les iteratoret listIteratorretournés par ces classes sont fail-fast(si la liste est structurellement modifiée à tout moment après la création de l'itérateur, de quelque manière que ce soit, sauf par le biais des iterator’sméthodes propres à supprimer ou ajouter, l'itérateur: throwa ConcurrentModificationException).

Quand utiliser LinkedList et quand utiliser ArrayList?

  • Comme expliqué ci-dessus, les opérations d'insertion et de suppression donnent de bonnes performances (O(1))par LinkedListrapport à ArrayList(O(n)).

    Par conséquent, s'il existe une exigence d'ajout et de suppression fréquents dans l'application, LinkedList est le meilleur choix.

  • Les get methodopérations de recherche ( ) sont rapides Arraylist (O(1))mais pasLinkedList (O(n))

    donc s'il y a moins d'opérations d'ajout et de suppression et plus d'exigences d'opérations de recherche, ArrayList serait votre meilleur pari.

Real73
la source
5

L'opération get (i) dans ArrayList est plus rapide que LinkedList, car:
ArrayList: implémentation de tableau redimensionnable de l'interface List
LinkedList: implémentation de liste à double liaison des interfaces List et Deque

Les opérations qui indexent dans la liste traverseront la liste depuis le début ou la fin, selon la valeur la plus proche de l'index spécifié.

Amitābha
la source
5

1) Structure de données sous-jacente

La première différence entre ArrayList et LinkedList vient du fait que ArrayList est soutenu par Array tandis que LinkedList est soutenu par LinkedList. Cela entraînera de nouvelles différences de performances.

2) LinkedList implémente Deque

Une autre différence entre ArrayList et LinkedList est qu'en dehors de l'interface List, LinkedList implémente également l'interface Deque, qui fournit des opérations de premier entré, premier sorti pour add () et poll () et plusieurs autres fonctions Deque. 3) Ajouter des éléments dans ArrayList Ajouter un élément dans ArrayList est une opération O (1) si elle ne déclenche pas la redimensionnement de Array, auquel cas il devient O (log (n)), En revanche, ajouter un élément dans LinkedList est une opération O (1), car elle ne nécessite aucune navigation.

4) Supprimer un élément d'une position

Afin de supprimer un élément d'un index particulier, par exemple en appelant remove (index), ArrayList effectue une opération de copie qui le rapproche de O (n) tandis que LinkedList doit traverser ce point qui le rend également O (n / 2) , car il peut traverser dans les deux sens en fonction de la proximité.

5) Itération sur ArrayList ou LinkedList

L'itération est l'opération O (n) pour LinkedList et ArrayList où n est un nombre d'un élément.

6) Récupération d'un élément d'une position

L'opération get (index) est O (1) dans ArrayList tandis que son O (n / 2) dans LinkedList, car elle doit traverser jusqu'à cette entrée. Cependant, en notation Big O, O (n / 2) est juste O (n) car nous ignorons les constantes.

7) Mémoire

LinkedList utilise un objet wrapper, Entry, qui est une classe imbriquée statique pour stocker les données et deux nœuds suivant et précédent tandis qu'ArrayList stocke simplement les données dans Array.

Les besoins en mémoire semblent donc moins importants dans le cas d'ArrayList que dans LinkedList, sauf dans le cas où Array effectue l'opération de redimensionnement lorsqu'il copie le contenu d'un tableau vers un autre.

Si Array est suffisamment grand, cela peut prendre beaucoup de mémoire à ce stade et déclencher le garbage collection, ce qui peut ralentir le temps de réponse.

De toutes les différences ci-dessus entre ArrayList et LinkedList, il semble qu'ArrayList soit le meilleur choix que LinkedList dans presque tous les cas, sauf lorsque vous effectuez une opération add () fréquente que remove () ou get ().

Il est plus facile de modifier une liste liée qu'ArrayList, surtout si vous ajoutez ou supprimez des éléments du début ou de la fin car la liste liée conserve en interne les références de ces positions et elles sont accessibles en temps O (1).

En d'autres termes, vous n'avez pas besoin de parcourir la liste liée pour atteindre la position où vous souhaitez ajouter des éléments, dans ce cas, l'addition devient une opération O (n). Par exemple, insérer ou supprimer un élément au milieu d'une liste liée.

À mon avis, utilisez ArrayList sur LinkedList pour la plupart des applications pratiques en Java.

Anjali Suman
la source
1
Je pense que c'est la meilleure réponse affirmée de l'ensemble du groupe ici. C'est précis et informatif. Je suggérerais de changer la dernière ligne - à la fin ajouter "à part les files d'attente" qui sont des structures très importantes qui n'ont vraiment aucun sens pour une liste chaînée du tout.
Bill K
3

L'un des tests que j'ai vus ici ne fait le test qu'une seule fois. Mais ce que j'ai remarqué, c'est que vous devez exécuter ces tests plusieurs fois et, éventuellement, leurs temps convergeront. Fondamentalement, la JVM doit se réchauffer. Pour mon cas d'utilisation particulier, j'avais besoin d'ajouter / supprimer des éléments à une liste qui atteint environ 500 éléments. Lors de mes tests, je suis LinkedListsorti plus vite, avec LinkedListenviron 50 000 NS et ArrayListenviron 90 000 NS ... à donner ou à prendre. Voir le code ci-dessous.

public static void main(String[] args) {
    List<Long> times = new ArrayList<>();
    for (int i = 0; i < 100; i++) {
        times.add(doIt());
    }
    System.out.println("avg = " + (times.stream().mapToLong(x -> x).average()));
}

static long doIt() {
    long start = System.nanoTime();
    List<Object> list = new LinkedList<>();
    //uncomment line below to test with ArrayList
    //list = new ArrayList<>();
    for (int i = 0; i < 500; i++) {
        list.add(i);
    }

    Iterator it = list.iterator();
    while (it.hasNext()) {
        it.next();
        it.remove();
    }
    long end = System.nanoTime();
    long diff = end - start;
    //uncomment to see the JVM warmup and get faster for the first few iterations
    //System.out.println(diff)
    return diff;
}
Jose Martinez
la source
2

Remove () et insert () ont une efficacité d'exécution de O (n) à la fois pour ArrayLists et LinkedLists. Cependant, la raison du temps de traitement linéaire vient de deux raisons très différentes:

Dans une ArrayList, vous accédez à l'élément dans O (1), mais en réalité, la suppression ou l'insertion de quelque chose le rend O (n) car tous les éléments suivants doivent être modifiés.

Dans une LinkedList, il faut O (n) pour atteindre réellement l'élément souhaité, car nous devons commencer au tout début jusqu'à ce que nous atteignions l'index souhaité. En fait, la suppression ou l'insertion est constante, car il suffit de modifier 1 référence pour remove () et 2 références pour insert ().

Lequel des deux est plus rapide pour l'insertion et le retrait dépend de l'endroit où cela se produit. Si nous sommes plus proches du début, la LinkedList sera plus rapide, car nous devons passer par relativement peu d'éléments. Si nous sommes plus près de la fin, une ArrayList sera plus rapide, car nous y arriverons en temps constant et n'aurons qu'à changer les quelques éléments restants qui la suivent. Lorsqu'elle est effectuée précisément au milieu, la LinkedList sera plus rapide car parcourir n éléments est plus rapide que déplacer n valeurs.

Bonus: Bien qu'il n'y ait aucun moyen de rendre ces deux méthodes O (1) pour une ArrayList, il existe en fait un moyen de le faire dans LinkedLists. Disons que nous voulons parcourir toute la liste en supprimant et en insérant des éléments sur notre chemin. Habituellement, vous commenceriez depuis le tout début pour chaque élément en utilisant la LinkedList, nous pourrions également «enregistrer» l'élément actuel sur lequel nous travaillons avec un itérateur. Avec l'aide de l'itérateur, nous obtenons une efficacité O (1) pour remove () et insert () lorsque vous travaillez dans une LinkedList. Ce qui en fait le seul avantage en termes de performances, je sais où une LinkedList est toujours meilleure qu'une ArrayList.

pietz
la source
1

ArrayList étend AbstractList et implémente l'interface de liste. ArrayList est un tableau dynamique.
On peut dire qu'elle a été essentiellement créée pour surmonter les inconvénients des tableaux.

La classe LinkedList étend AbstractSequentialList et implémente l'interface List, Deque et Queue.
La performance
arraylist.get()est O (1) alors que linkedlist.get()est O (n)
arraylist.add()est O (1) et linkedlist.add()est 0 (1)
arraylist.contains()est O (n) et linkedlist.contains()est O (n)
arraylist.next()est O (1) et linkedlist.next()est O (1)
arraylist.remove()est O (n) alors que linkedlist.remove()O (1)
dans arraylist
iterator.remove()est O (n)
tandis que dans LinkedList
iterator.remove()est O (1)

Randhawa
la source