Quand utiliser LinkedList sur ArrayList en Java?

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?

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.

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.

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)

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.

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.

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.

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)

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 .

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);
    }
}

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.):

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.

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.

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):

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

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:

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

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.

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é.

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. :)

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

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    |
|--------------------------------------|

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).

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.

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.

Voir les Tutoriels Java - Liste des implémentations .

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?

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.

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.

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.

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é.

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.

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;
}

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.

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)