Quand utiliser LinkedList sur ArrayList en Java?

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 un LinkedList est "beaucoup plus" qu'un ArrayList, j'ai donc fait un certain nombre de calculs pour démontrer exactement combien les deux listes prennent pour N références null.

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

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

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

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

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

ArrayList:

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

LinkedList:

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

ArrayList c'est ce que tu veux. LinkedList est presque toujours un bogue (de performance).

Pourquoi LinkedList suce:

• Il utilise beaucoup de 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 localisation de 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 si ArrayList était utilisé.
• Obtenir de bonnes performances est délicat.
• Même lorsque les performances de big-O sont les mêmes que ArrayList, elles seront probablement beaucoup plus lentes de toute façon.
• Il est choquant de voir LinkedList dans la source car c'est probablement le mauvais choix.

En tant que personne qui fait de l'ingénierie des performances opérationnelles 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 à l'état stable de LinkedList est pire et pourrait donc conduire à l'achat de plus de matériel the le comportement de ArrayList sous pression pourrait conduire à des applications dans un cluster étendant leurs tableaux en quasi synchronicité et pour les grandes tailles de tableaux pourrait conduire à un manque de réactivité dans l'application et un panne, sous pression, ce qui est un comportement catastrophique.

De même, vous pouvez obtenir un meilleur débit dans une application à partir du garbage collector tenured de débit par défaut, mais une fois que vous obtenez des applications java avec des tas de 10 Go, vous pouvez verrouiller l'application pendant 25 secondes pendant un GCs complet, ce qui provoque des délais d'attente et des échecs dans les applications SOA Même si le collecteur CMS prend plus de ressources et n'atteint pas le même débit brut, il est beaucoup mieux 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 performance est le débit et que vous pouvez ignorer la latence. Dans mon expérience à mon travail, je ne peux pas ignorer la latence du pire des cas.

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

Algorithmes: Notation Big-Oh

ArrayLists sont bons pour write-once-read-many ou appenders, mais mauvais pour ajouter/supprimer de l'avant ou du milieu.

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

LinkedList estpresque toujours le mauvais choix, en termes de performances. Il existe des algorithmes très spécifiques pour lesquels une LinkedList est appelée, mais ceux-ci sont très, très rares et l'algorithme dépendra 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 y en a 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 une ArrayBlockingQueue (si vous pouvez déterminer une limite supérieure sur la taille de votre file d'attente à l'avance et que vous pouvez vous permettre d'allouer toute la mémoire à l'avance), ou cette implémentation CircularArrayList. (Oui, c'est de 2001, vous devrez donc le généraliser, mais j'ai des ratios de performance comparables à ce qui est cité dans l'article juste maintenant dans une JVM récente)

C'est une question d'efficacité. LinkedList est rapide pour ajouter et supprimer des éléments, mais lent pour accéder à un élément spécifique. ArrayList est rapide pour accéder à un élément spécifique mais peut être lent à ajouter à chaque extrémité, et surtout lent à supprimer au milieu.

Tableau vs ArrayList vs LinkedList vs Vecteur va plus en profondeur, comme le fait Liste chaînée .

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

Modifier/Supprimer un est plus rapide dans LinkedList que ArrayList.

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

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

ArrayList est essentiellement un tableau. LinkedList est implémenté sous la forme d'une double liste chaînée.

Le get est assez clair. O (1) pour ArrayList, parce que ArrayList permet l'accès aléatoire en utilisant index. O (n) pour LinkedList, car il doit d'abord trouver l'index. Remarque: il existe différentes versions de add et remove.

LinkedList est plus rapide d'ajouter et de supprimer, mais plus lent à obtenir. En bref, {[1] } devrait être préféré si:

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

=== ArrayList ===

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

=== Liste de liens ===

• Ajouter(E e)

  • ajouter au fin de la liste
  • O (1)

• Ajouter (int index, E element)

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

Voici un schéma de programcreek.com (add et remove sont du premier type, c'est à dire, ajouter un élément à la fin de la liste et supprimer l'élément à la position spécifiée dans la liste.):

ArrayList est accessible au hasard, tandis que LinkedList est vraiment bon marché pour développer et supprimer des éléments. Dans la plupart des cas, ArrayList est correct.

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

1) Recherche: L'opération de recherche ArrayList est assez rapide par rapport à l'opération de recherche LinkedList. get (int index) dans ArrayList donne les performances de O(1) tandis que les performances de LinkedList sont O(n).

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

2) Suppression: L'opération LinkedList remove donne des performances O(1) tandis que ArrayList donne 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 de l'élément LinkedList est plus rapide par rapport à ArrayList.

Raison: Chacun des éléments de LinkedList maintient deux pointeurs (adresses), qui pointez sur les deux éléments voisins de la liste. Par conséquent, la suppression ne nécessite qu'un changement de l'emplacement du pointeur dans les deux nœuds voisins (éléments) du nœud qui va être supprimé. Dans ArrayList, tous les éléments doivent être décalés pour remplir l'espace créé par l'élément supprimé.

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

4) Mémoire Surcharge: ArrayList maintient les index et les données d'élément tandis que LinkedList maintient les données d'élément et deux pointeurs pour les nœuds voisins, d'où la consommation de mémoire est élevée dans LinkedList comparativement.

Il y a peu de similitudes entre ces classes qui sont les suivantes:

ArrayList et LinkedList sont des implémentations de List interface. Ils maintiennent tous les deux l'ordre d'insertion des éléments ce qui signifie tout en affichant les éléments ArrayList et LinkedList le résultat set 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 Collections.Méthode synchronizedList. L'itérateur et le listIterator renvoyés par ces classes sont rapides à l'échec (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 via les propres méthodes remove ou add de l'itérateur, l'itérateur lancera un ConcurrentModificationException).

Quand utiliser LinkedList et quand utiliser ArrayList?

1) Comme expliqué ci-dessus, les opérations insert et remove donnent de bonnes performances (O(1)) dans LinkedList par rapport à ArrayList(O(n)). Par conséquent, s'il y a une exigence d'ajout et de suppression fréquents dans une application, LinkedList est le meilleur choix.

2) Les opérations de recherche (méthode get) sont rapides dans ArrayList (O(1)) mais pas dans LinkedList (O(n)) donc s'il y a moins d'add et supprimer les opérations et plus besoin d'opérations de recherche, ArrayList serait votre meilleur pari.

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.

Je sais que c'est un ancien post, mais honnêtement, je ne peux pas croire que personne n'ait mentionné que LinkedList implémente Deque. Il suffit de regarder les méthodes de Deque (et Queue); si vous voulez une comparaison équitable, essayez d'exécuter LinkedList contre ArrayDeque et faire une fonction de comparaison des fonctionnalités.

Si votre code a add(0) et remove(0), utiliser un LinkedList et il est plus joli addFirst() et removeFirst() méthodes. Sinon, utilisez ArrayList.

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

Voici la notation Big-O dans ArrayList et LinkedList et aussi CopyOnWrite-ArrayList:

ArrayList

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

Liste de liens

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 avec les 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 doublement liée de l'interface de liste.

2. Les performances

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

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

  LinkedList get(int index) l'exécution de l'opération 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 le plus proche) pour récupérer le nœud au niveau spécifié index de l'élément.

• Opération Insert() ou add(Object)

  Les insertions dansLinkedList 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 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 add dans ArrayList O(n), sinon c'est O (1).

• Supprimer(int) opération

  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. l'un est de supprimer() sans 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 int passé en tant que paramètre. Cette méthode traverse LinkedList jusqu'à ce qu'il trouve l'objet et le dissocie de la liste d'origine. Par conséquent, cette méthode d'exécution est O(n).

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

3. Itérateur inverse

LinkedList peut être itéré dans le sens inverse en utilisant descendingIterator () tandis que

Il n'y a pas de descendingIterator () dans ArrayList , nous devons donc écrire notre propre code pour itérer sur la ArrayList dans le 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 ne construit que la liste vide sans aucune capacité initiale.

5. Frais généraux de mémoire

La surcharge de mémoire dans LinkedList est plus par rapport à ArrayList en tant que nœud dans LinkedList doit conserver les adresses des nœuds suivant et précédent. Alors que

Dans ArrayList chaque indice ne tient que l'objet réel(données).

Source

En plus des autres bons arguments ci-dessus, vous devriez remarquer ArrayList implémente RandomAccess interface, tandis que LinkedList implémente Queue.

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

Voir Java Tutoriels - Liste des Implémentations.

Une liste de tableaux est essentiellement un tableau avec des méthodes pour ajouter des éléments, etc. (et vous devriez utiliser une liste générique à la place). 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 chaîné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 chaînée indique absolument quel élément est censé suivre le précédent.

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

ArrayList est 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 n'importe quel article qui parle de la différence entre les tableaux et les listes chaînées.

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 les 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 raison d'être était que, parce qu'il est impossible de savoir exactement combien de résultats j'obtiens, il n'y aura pas de mémoire gaspillée (comme dans ArrayList avec la différence entre la capacité et le nombre réel d'éléments), et là ce ne serait pas du 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, pour minimiser autant que possible la duplication des tableaux.

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 son LinkedList ce n'est pas vrai! Voir Existe-t-il une méthode de concat rapide pour la liste chaînée en Java?

L'opération get (i) dans ArrayList est plus rapide que LinkedList, car:
ArrayList: Redimensionnable-implémentation de tableau de l'interface de liste
LinkedList: Implémentation de liste doublement liée des interfaces List et Deque

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

ArrayList et LinkedList deux implémente List interface, leurs méthodes et les résultats sont presque identiques. Cependant, il y a peu de différences entre eux qui rendent l'un meilleur sur l'autre en fonction de l'exigence.

ArrayList Vs LinkedList

1) Search: ArrayList opération de recherche est assez rapide par rapport à la LinkedList opération de recherche. get(int index) dans ArrayList donne la performance de O(1) tout LinkedList performance est O(n).

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

2) Deletion: LinkedList l'opération remove donne des performances O(1) tandis que ArrayList donne 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 de l'élément LinkedList est plus rapide que Liste de tableaux.

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 ArrayList, tous les éléments doivent être décalés pour remplir l'espace créé par l'élément supprimé.

3) Inserts Performance: LinkedList ajouter une méthode donne O(1) les performances tout en ArrayList donne O(n) dans le pire des cas. La raison est la même que celle expliquée pour supprimer.

4) Memory Overhead: ArrayList maintient les index et les données d'élément, tandis que LinkedList maintient l'élément de données et deux pointeurs pour les noeuds voisins

Par conséquent, la consommation de mémoire est élevée dans LinkedList comparativement.

Il y a peu de similitudes entre ces classes qui sont les suivantes:

• ArrayList et LinkedList sont toutes deux une implémentation de List interface.
• Ils maintiennent tous les deux l'ordre d'insertion des éléments, ce qui signifie que lors de l'affichage des é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 en utilisant des Collections.Méthode synchronizedList.
• Les iterator et listIterator renvoyés par ces classes sont fail-fast (si la liste est structurellement modifiée à tout moment après le l'itérateur est créé, de quelque manière que ce soit, sauf via les iterator’s propres méthodes supprimer ou ajouter, l'itérateur sera throw a 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)) dans LinkedList par rapport à ArrayList(O(n)).

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

• Recherche (get method) les opérations sont rapides dans Arraylist (O(1)), mais pas dans LinkedList (O(n))

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

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. Donc, lorsque vous voulez rechercher un élément dans une ArrayList, c'est plus rapide que de faire n itérations avec LinkedList.

D'autre part, 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 de l'opération shift 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 une insertion et une suppression fréquentes, utilisez une liste de liens.

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 d'autres différences de performance.

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 first in first out opérations 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 re-taille du tableau, auquel cas elle devient O(log(n)), d'autre part, ajouter un élément dans LinkedList est une opération O(1), car elle ne nécessite aucune navigation.

4) Suppression d'un élément à partir d'une position

Pour supprimer un élément d'un index particulier, par exemple en appelant remove (index), ArrayList effectue une opération de copie qui le rend proche de O(n) tandis que LinkedList doit traverser jusqu'à ce point qui le rend également O (n/2), car il peut traverser de l'une ou l'autre direction en fonction de la proximité.

5) Itérer sur ArrayList ou LinkedList

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 à partir d'une position

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

7) Mémoire

LinkedList utilise un objet wrapper, Entry, qui est une classe imbriquée statique pour stocker des données et deux nœuds suivant et précédent tandis que ArrayList ne stocke que des données dans un tableau.

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

Si le tableau est assez grand, il peut prendre beaucoup de mémoire à ce moment-là et déclencher la récupération de place, ce qui peut ralentir le temps de réponse.

De toutes les différences ci-dessus entre ArrayList et LinkedList, Il semble que 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 chaînée que ArrayList, surtout si vous êtes ajout ou suppression d'éléments de début ou de fin car la liste chaîné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 chaîné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 chaînée.

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

Remove() et insert() ont une efficacité d'exécution de O(n) pour ArrayLists et LinkedLists. Cependant, la raison derrière le 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 la suppression ou l'insertion de quelque chose le rend O(n) car tous les éléments suivants doivent être modifiés.

Dans une liste de liens, il faut O (n) pour arriver à l'élément souhaité, car nous devons commencer par en commençant jusqu'à ce que nous atteignions l'indice souhaité. En fait, la suppression ou l'insertion est constante, car nous n'avons qu'à changer 1 référence pour remove() et 2 références pour insert().

Lequel des deux est le plus rapide pour l'insertion et la suppression dépend de l'endroit où cela se produit. Si nous sommes plus proches du début, le LinkedList sera plus rapide, car nous devons passer par relativement peu d'éléments. Si nous sommes plus proches de la fin, une liste de tableaux sera plus rapide, car nous y arrivons en temps constant et n'avons pour changer les quelques éléments restants qui le suivent. Lorsque cela est fait précisément au milieu, la LinkedList sera plus rapide car passer par n éléments est plus rapide que de déplacer n valeurs.

Bonus: Bien qu'il n'y ait aucun moyen de faire 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 dès le début pour chaque élément en utilisant le 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 de performance dont je suis conscient où une LinkedList est toujours meilleure qu'une ArrayList.

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

La classe LinkedList étend AbstractSequentialList et implémente l'interface List,Deque et Queue.
Performance
arraylist.get() est O(1) considérant que la linkedlist.get() est O(n)
arraylist.add() est O(1) et linkedlist.add() est 0(1)
arraylist.contains() est O(n) etlinkedlist.contains() est O(n)
arraylist.next() est O(1) et linkedlist.next() est O(1)
arraylist.remove() est O(n) considérant que linkedlist.remove() est O (1)
Dans arraylist
iterator.remove() est O(n)
alors que Dans linkedlist
iterator.remove()est O(1)

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'ai besoin d'ajouter/supprimer des éléments d'un dernier qui pousse à environ 500 articles. Dans mes tests, LinkedList est sorti plus rapidement, avec linked LinkedList environ 50 000 NS et ArrayList environ 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;
}

Quand dois-je utiliser LinkedList? Lorsque vous travaillez avec des piles principalement, ou lorsque vous travaillez avec des tampons. Quand dois-je utiliser ArrayList? Uniquement lorsque vous travaillez avec des index, sinon vous pouvez utiliser HashTable avec une liste chaînée, alors vous obtenez:

Table de hachage + liste chaînée

• Accès par clé O(1),
• Insérer par touche O (1),
• Supprimer par touche O (1)
• et il existe une astuce pour implémenter RemoveAll / SetAll avec O(1) lors de l'utilisation gestion des versions

Cela semble être une bonne solution, et dans la plupart des cas, c'est le cas, comment vous devriez le savoir: HashTable prend beaucoup d'espace disque, donc lorsque vous devez gérer la liste des éléments 1,000,000, il peut devenir une chose qui compte. Cela peut se produire dans les implémentations de serveur, les clients c'est rarement le cas.

Aussi jeter un oeil à Rouge-Noir-Arbre

• Accès aléatoire Log (n),
• {Insérer[8]}Log(n),
• Supprimer Log (n)