une - liste java




Quand utiliser LinkedList sur ArrayList en Java? (20)

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 à l'une ou l'autre extrémité, et particulièrement lent à supprimer au milieu.

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

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

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

J'utilise l'interface comme nom de type pour la portabilité . Ainsi, lorsque je pose des questions de ce type, je peux retravailler mon code.

Quand LinkedList doit-il être utilisé sur ArrayList et inversement?


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

L'édition / suppression est plus rapide dans LinkedList que dans ArrayList .

ArrayList , soutenu par Array , qui doit être deux fois plus volumineux, est pire dans les applications à grand volume.

Vous trouverez ci-dessous le résultat du test unitaire pour chaque opération. Le chronométrage est donné 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);
    }
}

Jusqu'ici, personne ne semble avoir abordé l'empreinte mémoire de chacune de ces listes, mis à part le consensus général selon lequel une liste LinkedList est "beaucoup plus" qu'une liste ArrayList . J'ai donc procédé à une compression des chiffres pour démontrer à quel point les deux listes occupent N références nulles. .

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

Remarque: les tailles indiquées pour les lignes ArrayList correspondent à des listes coupées . En pratique, la capacité du tableau de sauvegarde dans une ArrayList est généralement supérieure à son nombre d'éléments actuel.

Note 2: (merci BeeOnRope) Comme CompressedOops est la valeur par défaut à partir de la mi JDK6, les valeurs ci-dessous pour les machines 64 bits correspondront à leurs contreparties 32 bits, à moins que vous ne la désactiviez spécifiquement.

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

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

ArrayList :

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

LinkedList :

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

Oui, je sais, c'est une question ancienne, mais je vais ajouter mes deux sous:

LinkedList est presque toujours le mauvais choix en termes de performances. Il existe certains algorithmes très spécifiques pour lesquels une liste liée est demandée, mais ceux-ci sont extrêmement rares et l'algorithme dépend généralement de la capacité de LinkedList d'insérer et de 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. Toutefois, si votre objectif est la performance, au lieu de LinkedList, vous devriez également envisager d’utiliser une ArrayBlockingQueue (si vous pouvez déterminer une limite supérieure de la taille de votre file d’attente à l’avance et pouvoir vous permettre d’allouer toute la mémoire à l’avance), ou cette implémentation de CircularArrayList. . (Oui, c'est à partir de 2001, vous aurez donc besoin de le générer, mais j'ai obtenu des ratios de performance comparables à ceux cités dans l'article dans une machine virtuelle récente)


ArrayList est essentiellement un tableau. LinkedList est implémenté sous forme de liste à double liaison.

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

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

  1. il n'y a pas 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
  • add (int index, élément E)
    • ajouter à une position d'index spécifique
    • nécessite un décalage et un éventuel coût de redimensionnement de la mémoire
    • Sur)
  • remove (int index)
    • supprimer un élément spécifié
    • nécessite un décalage et un éventuel coût de redimensionnement de la mémoire
    • Sur)
  • retirer (objet o)
    • supprimer la première occurrence de l'élément spécifié de cette liste
    • nécessité de rechercher l'élément en premier, puis de décaler et de redimensionner le coût possible de la mémoire
    • Sur)

=== LinkedList ===

  • ajouter (E e)

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

    • insérer à la position spécifiée
    • besoin de trouver le poste en premier
    • Sur)
  • retirer()
    • supprimer le premier élément de la liste
    • O (1)
  • remove (int index)
    • Supprimer l'élément avec l'index spécifié
    • besoin de trouver l'élément en premier
    • Sur)
  • retirer (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 il removes’agit 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):


ArrayListest accessible au hasard, alors qu’il LinkedListest vraiment pas cher d’agrandir et d’enlever des éléments. Dans la plupart des cas, ArrayListça va.

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


1) Structure de données sous-jacente

La première différence entre ArrayList et LinkedList réside dans le fait que ArrayList est pris en charge par Array, tandis que LinkedList est soutenu par LinkedList. Cela entraînera de nouvelles différences de performance.

2) LinkedList implémente Deque

Une autre différence entre ArrayList et LinkedList est que, hormis l'interface List, LinkedList implémente également l'interface Deque, qui fournit les opérations premier entré, premier sorti pour add () et poll (), ainsi que 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 elle devient O (log (n)). Par contre, ajouter un élément dans LinkedList est une opération O (1), car elle ne nécessite aucune navigation.

4) Retirer un élément 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 rapproche de O (n), tandis que LinkedList doit passer à ce point, ce qui le rend également O (n / 2). , car il peut traverser 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 le numéro d'un élément.

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

L'opération get (index) est O (1) dans ArrayList alors que son O (n / 2) dans LinkedList, car elle doit être parcourue jusqu'à cette entrée. Cependant, dans la notation Big O, O (n / 2) est simplement O (n) car nous ignorons les constantes.

7) mémoire

LinkedList utilise un objet wrapper, Entry, qui est une classe imbriquée statique pour le stockage de données et deux nœuds next et previous, tandis que ArrayList stocke uniquement des données dans Array.

Par conséquent, les besoins en mémoire semblent moins, dans le cas de ArrayList, que dans LinkedList, sauf dans le cas où Array effectue l'opération de redimensionnement lorsqu'il copie le contenu d'un tableau à un autre.

Si Array est suffisamment grand, cela peut prendre beaucoup de mémoire et déclencher un Garbage Collection, ce qui peut ralentir le temps de réponse.

Parmi toutes les différences entre ArrayList et LinkedList ci-dessus, 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 plutôt que remove () ou get ().

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

En d'autres termes, il n'est pas nécessaire 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.


En raison de l'architecture informatique moderne, TL; DRArrayList sera nettement plus efficace dans presque tous les cas d'utilisation possibles - et LinkedListdoit donc être évité, sauf dans des cas extrêmes et tout à fait uniques.

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

De plus, l'ajout d'un élément au milieu d'une liste devrait être très efficace.

La pratique est très différente, car LinkedList est une structure Cache Hostile Data. De performance POV - il y a très peu de cas où il LinkedListpourrait être plus performant que le cache-friendly ArrayList .

Voici les résultats d'un test de référence en insérant des éléments dans des emplacements aléatoires. Comme vous pouvez le constater - la liste de tableaux est beaucoup plus efficace, même si en théorie chaque insertion au milieu de la liste nécessitera le "déplacement" des n éléments suivants du tableau (les valeurs les plus basses sont les meilleures):

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

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

Il y a deux raisons principales pour cela:

  1. Principalement - que les nœuds du LinkedListsont dispersés aléatoirement 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 de tels extractions sont fréquentes, les pages de la mémoire cache doivent être remplacées à tout moment -> les erreurs de cache -> le cache n'est pas efficace. ArrayListles éléments sont stockés dans une mémoire continue - ce qui correspond exactement à l'optimisation de l'architecture de processeur moderne.

  2. Secondaire LinkedList requis pour conserver les pointeurs en arrière / en aval, ce qui représente 3 fois la consommation de mémoire par valeur stockée par rapport à ArrayList.

DynamicIntArray , btw, est une implémentation personnalisée de ArrayList Int(type primitif) et non des objets. Par conséquent, toutes les données sont réellement stockées de manière adjacente - et donc encore plus efficaces.

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 de 1 Mo de mémoire séquentielle est jusqu'à 400 fois plus rapide que de lire 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: numéros de latence que chaque programmeur devrait connaître

Pour que ce soit encore plus clair, veuillez vérifier si vous ajoutez des éléments au début de la liste. C'est un cas d'utilisation où, en théorie, le produit LinkedListdevrait vraiment briller et ArrayListprésenter des résultats médiocres, voire pire:

Remarque: il s'agit d'un test de performances de la bibliothèque C ++ Std, mais mon expérience précédente montrait que les résultats C ++ et Java étaient très similaires. Code source

Copie d' une masse séquentielle de la mémoire est une opération optimisée par les processeurs modernes - la théorie en évolution et en fait faire, encore une fois, ArrayList/ Vectorbeaucoup plus efficace

Crédits: Tous les points de repère affichés ici sont créés par Kjell Hedström . On trouve encore plus de données sur son blog


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, cela est plus rapide que d'effectuer n itérations avec LinkedList.

En revanche, l’insertion et la suppression dans une LinkedList sont beaucoup plus faciles car il vous suffit de changer les pointeurs, alors qu’un ArrayList implique l’utilisation d’une opération shift pour toute insertion ou suppression.

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


Cela dépend des opérations que vous ferez 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 traitant de la différence entre les tableaux et les listes chaînées.


J'ai lu les réponses, mais il existe un scénario dans lequel j'utilise toujours une liste LinkedList sur une liste ArrayList que je souhaite partager pour entendre les opinions:

Chaque fois que j'ai eu une méthode qui retourne une liste de données obtenue à partir d'une base de données, j'utilise toujours une LinkedList.

Mon raisonnement était qu’étant donné qu’il était impossible de savoir exactement combien de résultats puis-je obtenir, la mémoire ne serait pas gaspillée (comme dans ArrayList avec la différence entre la capacité et le nombre réel d’éléments), et il n’y aurait aucune perte de temps à essayer de dupliquer la capacité.

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


Joshua Bloch, l'auteur de LinkedList:

Est-ce que quelqu'un utilise réellement LinkedList? Je l'ai écrit et je ne l'utilise jamais.

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

Je suis désolé pour la réponse qui n’a pas été aussi informative que les autres réponses, mais j’ai pensé que ce serait la solution la plus intéressante et la plus explicite.


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

La classe LinkedList étend AbstractSequentialList et implémente les interfaces List, Deque et Queue.
Performance
arraylist.get()est O (1) alors que linkedlist.get()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()est O (1)
dans arraylist
iterator.remove()est O (n)
alors que dans la liste chaînée
iterator.remove()est O (1)


En plus des autres bons arguments ci-dessus, vous devriez remarquer que ArrayListimplements RandomAccessinterface, tandis que LinkedListimplémente Queue.

Ils abordent donc des problèmes légèrement différents, avec des différences d'efficacité et de comportement (voir la liste de leurs méthodes).


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

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


L'un des tests que j'ai vus ici ne fait que le test une fois. Mais ce que j’ai remarqué, c’est que vous devez exécuter ces tests à plusieurs reprises et que leurs temps vont finalement converger. Fondamentalement, la machine virtuelle Java doit se réchauffer. Pour mon cas d'utilisation particulier, je devais ajouter / supprimer des éléments à un dernier élément d'environ 500 éléments. Au cours de mes tests, les résultats ont LinkedListété plus rapides: LinkedList50 000 NS environ ont été couplés et ArrayList90 000 NS environ… à peu près. 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;
}

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

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


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) (+ overhead de certaines réaffectations) 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 rapide pour la liste chaînée en Java?


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

ArrayList

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






linked-list