Quand utiliser LinkedList sur ArrayList?

J’ai toujours été un à utiliser simplement:

List names = new ArrayList(); 

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

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

    Résumé ArrayList avec ArrayDeque est préférable dans beaucoup plus de cas d’utilisation que LinkedList . Pas sûr – commencez par ArrayList .


    LinkedList et ArrayList sont deux implémentations différentes de l’interface List. LinkedList implémente avec une liste doublement liée. ArrayList implémente avec un tableau de redimensionnement dynamic.

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

    Pour LinkedList

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

    Remarque: la plupart des opérations nécessitent en moyenne n / 4 étapes, 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

    • get(int index) est O (1) < --- principal avantage de ArrayList
    • add(E element) est O (1) amorti, mais O (n) pire 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 n / 2 étapes en moyenne, nombre constant d’étapes dans le meilleur des cas (fin de liste), n étapes dans le pire des cas (début de liste)

    LinkedList permet des insertions ou des retraits à temps constant à l’ aide d’iterators , mais uniquement un access séquentiel des éléments. En d’autres termes, vous pouvez parcourir la liste en avant ou en arrière, mais trouver une position dans la liste prend du temps proportionnellement à la taille de la liste. Javadoc dit “les opérations qui indexent dans la liste vont traverser la liste depuis le début ou la fin, selon celle qui est la plus proche” , donc ces méthodes sont O (n) ( n / 4 étapes) en moyenne, bien que O (1) pour index = 0 .

    ArrayList , d’autre part, permet un access rapide à la lecture aléatoire, de sorte que vous pouvez saisir n’importe quel élément en temps constant. Mais append ou supprimer de n’importe où, mais la fin nécessite de déplacer tous les derniers éléments, soit pour faire une ouverture ou pour combler le vide. 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é sur le nouveau, ce qui signifie que l’ajout à une liste ArrayList est O (n) dans le tableau. pire des cas mais constant en moyenne.

    Ainsi, en fonction des opérations que vous comptez effectuer, vous devez choisir les implémentations en conséquence. Itérer sur n’importe quel type de liste est pratiquement aussi bon marché. (Itérer sur une ArrayList est techniquement plus rapide, mais à moins que vous ne fassiez quelque chose de vraiment sensible aux performances, vous ne devriez pas vous inquiéter de cela – ce sont les deux constantes.)

    Les principaux avantages de l’utilisation d’une LinkedList surviennent lorsque vous réutilisez des iterators existants pour insérer et supprimer des éléments. Ces opérations peuvent alors être effectuées dans O (1) en modifiant uniquement la liste localement. Dans une liste de tableaux, le rest du tableau doit être déplacé (c.-à-d. Copié). D’autre part, rechercher dans un LinkedList signifie suivre les liens dans O (n) ( n / 2 étapes) dans le pire des cas, alors que dans un ArrayList la position souhaitée peut être calculée mathématiquement et accessible dans O (1) .

    L’utilisation d’un LinkedList présente un autre avantage lorsque vous ajoutez ou supprimez de la tête de la liste, puisque ces opérations sont O (1) , alors qu’elles sont O (n) pour ArrayList . Notez que ArrayDeque peut être une bonne alternative à LinkedList pour append et supprimer de la tête, mais ce n’est pas une List .

    En outre, si vous avez de grandes listes, gardez à l’esprit que l’utilisation de la mémoire est également différente. Chaque élément d’une LinkedList a plus de surcharge puisque les pointeurs vers les éléments suivants et précédents sont également stockés. ArrayLists n’ont pas cette surcharge. Toutefois, ArrayLists prend autant de mémoire que ce qui est alloué pour la capacité, que des éléments aient été ajoutés ou non.

    La capacité initiale par défaut d’un ArrayList est assez petite (10 à partir 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 append beaucoup d’éléments, construisez ArrayList avec une capacité initiale plus élevée.

    Jusqu’à présent, personne ne semble avoir abordé l’empreinte mémoire de chacune de ces listes en dehors du consensus général selon lequel une LinkedList est “beaucoup plus” qu’une ArrayList donc j’ai fait quelques calculs pour montrer exactement combien 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 relatifs, j’ai inclus 4 ensembles de données pour les ArrayLists LinkedLists et les ArrayLists 32 et 64 bits.

    Remarque: Les tailles affichées pour les lignes ArrayList sont pour les listes tronqué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 maintenant par défaut à partir du milieu JDK6, les valeurs ci-dessous pour les machines 64 bits correspondront fondamentalement à leurs homologues 32 bits, sauf si vous les désactivez bien sûr.


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


    Le résultat montre clairement que LinkedList est bien plus que ArrayList , surtout 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” est 4 ou 8 pour les systèmes 32 ou 64 bits, et “n” est le nombre d’éléments. Notez que la raison de ces mods est que tous les objects de Java occuperont un espace de 8 octets, qu’il soit utilisé 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) 

    ArrayList est ce que vous voulez. LinkedList est presque toujours un bogue (de performance).

    Pourquoi LinkedList nul:

    • Il utilise beaucoup de petits objects de mémoire et affecte donc les performances du processus.
    • Beaucoup de petits objects sont mauvais pour la localité de cache.
    • Toute opération indexée nécessite une traversée, c’est-à-dire que la performance est O (n). Ce n’est pas évident dans le code source, conduisant aux algorithmes O (n) plus lentement 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 celles de ArrayList , elles seront probablement beaucoup plus lentes.
    • Il est choquant de voir LinkedList dans la source car c’est probablement le mauvais choix.

    En tant que spécialiste de la performance opérationnelle sur de très grands services Web SOA depuis une dizaine d’années, je préférerais le comportement de LinkedList sur ArrayList. Alors que le débit constant de LinkedList est pire et peut donc conduire à acheter plus de matériel – le comportement de ArrayList sous pression pourrait conduire à des applications dans un cluster développant leurs baies de manière quasi synchronisée et pour des tailles de baies importantes pourrait conduire à un manque de réactivité dans l’application et une panne, alors que sous pression, ce qui est un comportement catastrophique.

    De même, vous pouvez obtenir un meilleur débit dans une application à partir du récupérateur de mémoire propriétaire par défaut, mais une fois que vous obtenez des applications Java avec 10 Go de mémoire, vous pouvez fermer l’application pendant 25 secondes lors de tests complets. et souffle vos SLA si cela se produit trop souvent. Même si le collecteur du CMS prend plus de ressources et n’atteint pas le même débit brut, c’est un choix bien meilleur car sa latence est plus prévisible et plus faible.

    ArrayList n’est qu’un meilleur choix pour les performances si tout ce que vous entendez par performance est le débit et que vous pouvez ignorer la latence. D’après mon expérience professionnelle, je ne peux pas ignorer la latence la plus défavorable.

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

    Algorithmes: Notation Big-Oh

    ArrayLists est bon pour write-once-read-many ou appenders, mais mauvais pour add / remove de l’avant ou du milieu.

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

    LinkedList est presque toujours le mauvais choix, du sharepoint vue des performances. Il existe des algorithmes très spécifiques pour lesquels un élément LinkedList est appelé, mais ils sont très rares et l’algorithme dépend généralement 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 queue. Toutefois, si votre objective est la performance, au lieu de LinkedList, vous devriez également envisager d’utiliser ArrayBlockingQueue (si vous pouvez déterminer une limite supérieure de la taille de votre queue à l’avance et pouvoir allouer toute la mémoire) ou cette implémentation CircularArrayList. . (Oui, c’est à partir de 2001, vous devrez donc le générer, mais j’ai obtenu des ratios de performances comparables à ceux cités dans l’article tout à l’heure dans une JVM)

    C’est une question d’efficacité. LinkedList est rapide pour append et supprimer des éléments, mais il est lent pour accéder à un élément spécifique. ArrayList est rapide pour accéder à un élément spécifique mais peut être lent à append à l’une des extrémités, et particulièrement lent à supprimer au milieu.

    Array vs ArrayList vs LinkedList vs Vector va plus en profondeur, tout comme Linked List .

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

    Modifier / Supprimer est plus rapide dans LinkedList que 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. La mesure 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; Ssortingng[] ssortingngs = maxArray(); ////////////// ADD ALL //////////////////////////////////////// @Test public void arrayListAddAll() { Watch watch = new Watch(); List ssortingngList = Arrays.asList(ssortingngs); List arrayList = new ArrayList(MAX); watch.start(); arrayList.addAll(ssortingngList); watch.totalTime("Array List addAll() = ");//101,16719 Nanoseconds } @Test public void linkedListAddAll() throws Exception { Watch watch = new Watch(); List ssortingngList = Arrays.asList(ssortingngs); watch.start(); List linkedList = new LinkedList(); linkedList.addAll(ssortingngList); 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 arrayList = new ArrayList(MAX); watch.start(); for (Ssortingng ssortingng : ssortingngs) arrayList.add(ssortingng); watch.totalTime("Array List add() = ");//152,46840 Nanoseconds } @Test public void linkedListAdd() { Watch watch = new Watch(); List linkedList = new LinkedList(); watch.start(); for (Ssortingng ssortingng : ssortingngs) linkedList.add(ssortingng); 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 ssortingngList = Arrays.asList(ssortingngs); List arrayList = new ArrayList(MAX + MAX / 10); arrayList.addAll(ssortingngList); Ssortingng insertSsortingng0 = getSsortingng(true, MAX / 2 + 10); Ssortingng insertSsortingng1 = getSsortingng(true, MAX / 2 + 20); Ssortingng insertSsortingng2 = getSsortingng(true, MAX / 2 + 30); Ssortingng insertSsortingng3 = getSsortingng(true, MAX / 2 + 40); watch.start(); arrayList.add(insertSsortingng0); arrayList.add(insertSsortingng1); arrayList.add(insertSsortingng2); arrayList.add(insertSsortingng3); watch.totalTime("Array List add() = ");//36527 } @Test public void linkedListInsertOne() { Watch watch = new Watch(); List ssortingngList = Arrays.asList(ssortingngs); List linkedList = new LinkedList(); linkedList.addAll(ssortingngList); Ssortingng insertSsortingng0 = getSsortingng(true, MAX / 2 + 10); Ssortingng insertSsortingng1 = getSsortingng(true, MAX / 2 + 20); Ssortingng insertSsortingng2 = getSsortingng(true, MAX / 2 + 30); Ssortingng insertSsortingng3 = getSsortingng(true, MAX / 2 + 40); watch.start(); linkedList.add(insertSsortingng0); linkedList.add(insertSsortingng1); linkedList.add(insertSsortingng2); linkedList.add(insertSsortingng3); 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 ssortingngList = Arrays.asList(ssortingngs); List arrayList = new ArrayList(MAX); arrayList.addAll(ssortingngList); Ssortingng searchSsortingng0 = getSsortingng(true, MAX / 2 + 10); Ssortingng searchSsortingng1 = getSsortingng(true, MAX / 2 + 20); watch.start(); arrayList.remove(searchSsortingng0); arrayList.remove(searchSsortingng1); watch.totalTime("Array List remove() = ");//20,56,9095 Nanoseconds } @Test public void linkedListRemove() throws Exception { Watch watch = new Watch(); List linkedList = new LinkedList(); linkedList.addAll(Arrays.asList(ssortingngs)); Ssortingng searchSsortingng0 = getSsortingng(true, MAX / 2 + 10); Ssortingng searchSsortingng1 = getSsortingng(true, MAX / 2 + 20); watch.start(); linkedList.remove(searchSsortingng0); linkedList.remove(searchSsortingng1); 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 ssortingngList = Arrays.asList(ssortingngs); List arrayList = new ArrayList(MAX); arrayList.addAll(ssortingngList); Ssortingng searchSsortingng0 = getSsortingng(true, MAX / 2 + 10); Ssortingng searchSsortingng1 = getSsortingng(true, MAX / 2 + 20); watch.start(); arrayList.contains(searchSsortingng0); arrayList.contains(searchSsortingng1); watch.totalTime("Array List addAll() time = ");//186,15,704 } @Test public void linkedListSearch() throws Exception { Watch watch = new Watch(); List linkedList = new LinkedList(); linkedList.addAll(Arrays.asList(ssortingngs)); Ssortingng searchSsortingng0 = getSsortingng(true, MAX / 2 + 10); Ssortingng searchSsortingng1 = getSsortingng(true, MAX / 2 + 20); watch.start(); linkedList.contains(searchSsortingng0); linkedList.contains(searchSsortingng1); 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(Ssortingng s) { stop(); System.out.println(s + (endTime - startTime)); } } private Ssortingng[] maxArray() { Ssortingng[] ssortingngs = new Ssortingng[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é comme une double liste de liens.

    Le get est assez clair. O (1) pour ArrayList , car ArrayList permet un access aléatoire à l’aide d’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 dans add et remove, mais plus lent dans get. En bref, LinkedList devrait être préféré si:

    1. il n’y a pas grand nombre d’access aléatoire de l’élément
    2. il y a un grand nombre d’opérations d’ajout / suppression

    === ArrayList ===

    • append (e e)
      • append à 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)
      • append à une position d’index spécifique
      • nécessite un changement de vitesse et un possible redimensionnement de la mémoire
      • Sur)
    • supprimer (int index)
      • supprimer un élément spécifié
      • nécessite un changement de vitesse et un possible redimensionnement de la mémoire
      • Sur)
    • supprimer (object o)
      • supprimer la première occurrence de l’élément spécifié de cette liste
      • besoin de rechercher l’élément en premier, puis le décalage et le coût possible de redimensionnement de la mémoire
      • Sur)

    === LinkedList ===

    • append (e e)

      • append à la fin de la liste
      • 0 (1)
    • add (int index, é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 (int index)
      • Supprimer l’élément avec l’index spécifié
      • besoin de trouver l’élément en premier
      • Sur)
    • supprimer (object o)
      • supprimer 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 ( add et remove sont le premier type, c.-à-d. Ajouter un élément à la fin de la liste et supprimer l’élément à la position spécifiée dans la liste):

    entrer la description de l'image ici

    ArrayList est accessible aléatoirement, alors que LinkedList est vraiment bon marché pour développer et supprimer des éléments. Dans la plupart des cas, ArrayList est ArrayList .

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

    1) Search: ArrayList search operation is pretty fast compared to the LinkedList search operation. get(int index) in ArrayList gives the performance of O(1) while LinkedList performance is O(n).

    Reason: ArrayList maintains an index based system for its elements as it uses array data structure implicitly which makes it faster for searching an element in the list. On the other side, LinkedList implements a doubly linked list which requires the traversal through all the elements for searching an element.

    2) Deletion: LinkedList remove operation gives O(1) performance while ArrayList gives variable performance: O(n) in the worst case (while removing the first element) and O(1) in the best case (While removing the last element).

    Conclusion: LinkedList element deletion is faster compared to ArrayList.

    Reason: Each of LinkedList’s elements maintains two pointers (addresses), which point to both neighbor elements in the list. Hence removal only requires a change in the pointer location in the two neighbor nodes (elements) of the node which is going to be removed. While In ArrayList all the elements need to be shifted to fill out the space created by removed element.

    3) Inserts Performance: LinkedList add method gives O(1) performance while ArrayList gives O(n) in the worst case. The reason is same as explained for remove.

    4) Memory Overhead: ArrayList maintains indexes and element data while LinkedList maintains element data and two pointers for neighbor nodes hence the memory consumption is high in LinkedList comparatively.

    There are few similarities between these classes which are as follows:

    Both ArrayList and LinkedList are implementations of List interface. They both maintain the elements insertion order which means while displaying ArrayList and LinkedList elements the result set would be having the same order in which the elements got inserted into the List. Both these classes are non-synchronized and can be made synchronized explicitly by using Collections.synchronizedList method. The iterator and listIterator returned by these classes are fail-fast (if the list is structurally modified at any time after the iterator is created, in any way except through the iterator’s own remove or add methods, the iterator will throw a ConcurrentModificationException).

    When to use LinkedList and when to use ArrayList?

    1) As explained above the insert and remove operations give good performance (O(1)) in LinkedList compared to ArrayList(O(n)). Hence if there is a requirement of frequent addition and deletion in an application then LinkedList is the best choice.

    2) Search (get method) operations are fast in ArrayList (O(1)) but not in LinkedList (O(n)) so If there are less add and remove operations and more search operations requirement, ArrayList would be your best bet.

    Joshua Bloch, the author of LinkedList:

    Does anyone actually use LinkedList? I wrote it, and I never use it.

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

    I’m sorry for the answer for being not that informative as the other answers, but I thought it would be the most interesting and self-explanatory.

    I know this is an old post, but I honestly can’t believe nobody mentioned that LinkedList implements Deque . Just look at the methods in Deque (and Queue ); if you want a fair comparison, try running LinkedList against ArrayDeque and do a feature-for-feature comparison.

    If your code has add(0) and remove(0) , use a LinkedList and it’s prettier addFirst() and removeFirst() methods. Otherwise, use ArrayList .

    And of course, Guava ‘s ImmutableList is your best friend.

    Here is the Big-O notation in both ArrayList and LinkedList and also 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) 

    Based on these you have to decide what to choose. 🙂

    Let’s compare LinkedList and ArrayList wrt below parameters:

    1. Implementation

    ArrayList is the resizable array implementation of list interface , while

    LinkedList is the Doubly-linked list implementation of the list interface.


    2. Performance

    • get(int index) or search operation

      ArrayList get(int index) operation runs in constant time ie O(1) while

      LinkedList get(int index) operation run time is O(n) .

      The reason behind ArrayList being faster than LinkedList is that ArrayList uses an index based system for its elements as it internally uses an array data structure, on the other hand,

      LinkedList does not provide index-based access for its elements as it iterates either from the beginning or end (whichever is closer) to resortingeve the node at the specified element index.

    • insert() or add(Object) operation

      Insertions in LinkedList are generally fast as compare to ArrayList. In LinkedList adding or insertion is O(1) operation .

      While in ArrayList , if the array is the full ie worst case, there is an extra cost of resizing array and copying elements to the new array, which makes runtime of add operation in ArrayList O(n), otherwise it is O(1).

    • remove(int) operation

      Remove operation in LinkedList is generally the same as ArrayList ie O(n).

      In LinkedList , there are two overloaded remove methods. one is remove() without any parameter which removes the head of the list and runs in constant time O(1). The other overloaded remove method in LinkedList is remove(int) or remove(Object) which removes the Object or int passed as a parameter. This method traverses the LinkedList until it found the Object and unlink it from the original list. Hence this method runtime is O(n).

      While in ArrayList remove(int) method involves copying elements from the old array to new updated array, hence its runtime is O(n).


    3. Reverse Iterator

    LinkedList can be iterated in reverse direction using descendingIterator() while

    there is no descendingIterator() in ArrayList , so we need to write our own code to iterate over the ArrayList in reverse direction.


    4. Initial Capacity

    If the constructor is not overloaded, then ArrayList creates an empty list of initial capacity 10, while

    LinkedList only constructs the empty list without any initial capacity.


    5. Memory Overhead

    Memory overhead in LinkedList is more as compared to ArrayList as a node in LinkedList needs to maintain the addresses of the next and previous node. Tandis que

    In ArrayList each index only holds the actual object(data).


    La source

    In addition to the other good arguments above, you should notice ArrayList implements RandomAccess interface, while LinkedList implements Queue .

    So, somehow they address slightly different problems, with difference of efficiency and behavior (see their list of methods).

    See the Java Tutorials – List Implementations .

    An array list is essentially an array with methods to add items etc. (and you should use a generic list instead). It is a collection of items which can be accessed through an indexer (for example [0]). It implies a progression from one item to the next.

    A linked list specifies a progression from one item to the next (Item a -> item b). You can get the same effect with an array list, but a linked list absolutely says what item is supposed to follow the previous one.

    It depends upon what operations you will be doing more on the List.

    ArrayList is faster to access an indexed value. It is much worse when inserting or deleting objects.

    To find out more, read any article that talks about the difference between arrays and linked lists.

    I have read the responses, but there is one scenario where I always use a LinkedList over an ArrayList that I want to share to hear opinions:

    Every time I had a method that returns a list of data obtained from a DB I always use a LinkedList.

    My rationale was that because it is impossible to know exactly how many results am I getting, there will be not memory wasted (as in ArrayList with the difference between the capacity and actual number of elements), and there would be no time wasted trying to duplicate the capacity.

    As far a ArrayList, I agree that at least you should always use the constructor with the initial capacity, to minimize the duplication of the arrays as much as possible.

    An important feature of a linked list (which I didn’t read in another answer) is the concatenation of two lists. With an array this is O(n) (+ overhead of some reallocations) with a linked list this is only O(1) or O(2) 😉

    Important : For Java its LinkedList this is not true! See Is there a fast concat method for linked list in Java?

    Operation get(i) in ArrayList is faster than LinkedList, because:
    ArrayList: Resizable-array implementation of the List interface
    LinkedList: Doubly-linked list implementation of the List and Deque interfaces

    Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

    ArrayList and LinkedList both implements List interface and their methods and results are almost identical. However there are few differences between them which make one better over another depending on the requirement.

    ArrayList Vs LinkedList

    1) Search: ArrayList search operation is pretty fast compared to the LinkedList search operation. get(int index) in ArrayList gives the performance of O(1) while LinkedList performance is O(n) .

    Reason: ArrayList maintains index based system for its elements as it uses array data structure implicitly which makes it faster for searching an element in the list. On the other side LinkedList implements doubly linked list which requires the traversal through all the elements for searching an element.

    2) Deletion: LinkedList remove operation gives O(1) performance while ArrayList gives variable performance: O(n) in worst case (while removing first element) and O(1) in best case (While removing last element).

    Conclusion: LinkedList element deletion is faster compared to ArrayList.

    Reason: LinkedList’s each element maintains two pointers (addresses) which points to the both neighbor elements in the list. Hence removal only requires change in the pointer location in the two neighbor nodes (elements) of the node which is going to be removed. While In ArrayList all the elements need to be shifted to fill out the space created by removed element.

    3) Inserts Performance: LinkedList add method gives O(1) performance while ArrayList gives O(n) in worst case. Reason is same as explained for remove.

    4) Memory Overhead: ArrayList maintains indexes and element data while LinkedList maintains element data and two pointers for neighbor nodes

    hence the memory consumption is high in LinkedList comparatively.

    There are few similarities between these classes which are as follows:

    • Both ArrayList and LinkedList are implementation of List interface.
    • They both maintain the elements insertion order which means while displaying ArrayList and LinkedList elements the result set would be having the same order in which the elements got inserted into the List.
    • Both these classes are non-synchronized and can be made synchronized explicitly by using Collections.synchronizedList method.
    • The iterator and listIterator returned by these classes are fail-fast (if list is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException ).

    When to use LinkedList and when to use ArrayList?

    • As explained above the insert and remove operations give good performance (O(1)) in LinkedList compared to ArrayList(O(n)) .

      Hence if there is a requirement of frequent addition and deletion in application then LinkedList is a best choice.

    • Search ( get method ) operations are fast in Arraylist (O(1)) but not in LinkedList (O(n))

      so If there are less add and remove operations and more search operations requirement, ArrayList would be your best bet.

    ArrayList and LinkedList have their own pros and cons.

    ArrayList uses contiguous memory address compared to LinkedList which uses pointers toward the next node. So when you want to look up an element in an ArrayList is faster than doing n iterations with LinkedList.

    On the other hand, insertion and deletion in a LinkedList are much easier because you just have to change the pointers whereas an ArrayList implies the use of shift operation for any insertion or deletion.

    If you have frequent resortingeval operations in your app use an ArrayList. If you have frequent insertion and deletion use a LinkedList.

    1) Underlying Data Structure

    The first difference between ArrayList and LinkedList comes with the fact that ArrayList is backed by Array while LinkedList is backed by LinkedList. This will lead to further differences in performance.

    2) LinkedList implements Deque

    Another difference between ArrayList and LinkedList is that apart from the List interface, LinkedList also implements Deque interface, which provides first in first out operations for add() and poll() and several other Deque functions. 3) Adding elements in ArrayList Adding element in ArrayList is O(1) operation if it doesn’t sortinggger re-size of Array, in which case it becomes O(log(n)), On the other hand, appending an element in LinkedList is O(1) operation, as it doesn’t require any navigation.

    4) Removing an element from a position

    In order to remove an element from a particular index eg by calling remove(index), ArrayList performs a copy operation which makes it close to O(n) while LinkedList needs to traverse to that point which also makes it O(n/2), as it can traverse from either direction based upon proximity.

    5) Iterating over ArrayList or LinkedList

    Iteration is the O(n) operation for both LinkedList and ArrayList where n is a number of an element.

    6) Resortingeving element from a position

    The get(index) operation is O(1) in ArrayList while its O(n/2) in LinkedList, as it needs to traverse till that entry. Though, in Big O notation O(n/2) is just O(n) because we ignore constants there.

    7) Memory

    LinkedList uses a wrapper object, Entry, which is a static nested class for storing data and two nodes next and previous while ArrayList just stores data in Array.

    So memory requirement seems less in the case of ArrayList than LinkedList except for the case where Array performs the re-size operation when it copies content from one Array to another.

    If Array is large enough it may take a lot of memory at that point and sortinggger Garbage collection, which can slow response time.

    From all the above differences between ArrayList vs LinkedList, It looks ArrayList is the better choice than LinkedList in almost all cases, except when you do a frequent add() operation than remove(), or get().

    It’s easier to modify a linked list than ArrayList, especially if you are adding or removing elements from start or end because linked list internally keeps references of those positions and they are accessible in O(1) time.

    In other words, you don’t need to traverse through the linked list to reach the position where you want to add elements, in that case, addition becomes O(n) operation. For example, inserting or deleting an element in the middle of a linked list.

    In my opinion, use ArrayList over LinkedList for most of the practical purpose in Java.

    ArrayList extends AbstractList and implements the List Interface. ArrayList is dynamic array.
    It can be said that it was basically created to overcome the drawbacks of arrays

    The LinkedList class extends AbstractSequentialList and implements List,Deque, and Queue interface.
    Performance
    arraylist.get() is O(1) whereas linkedlist.get() is O(n)
    arraylist.add() is O(1) and linkedlist.add() is 0(1)
    arraylist.contains() is O(n) and linkedlist.contains() is O(n)
    arraylist.next() is O(1) and linkedlist.next() is O(1)
    arraylist.remove() is O(n) whereas linkedlist.remove() is O(1)
    In arraylist
    iterator.remove() is O(n)
    whereas In linkedlist
    iterator.remove() is O(1)

    Both remove() and insert() have a runtime efficiency of O(n) for both ArrayLists and LinkedLists. However, the reason behind the linear processing time comes from two very different reasons:

    In an ArrayList, you get to the element in O(1), but actually removing or inserting something makes it O(n) because all the following elements need to be changed.

    In a LinkedList, it takes O(n) to actually get to the desired element, because we have to start at the very beginning until we reach the desired index. Actually removing or inserting is constant, because we only have to change 1 reference for remove() and 2 references for insert().

    Which of the two is faster for inserting and removing depends on where it happens. If we are closer to the beginning the LinkedList will be faster, because we have to go through relatively few elements. If we are closer to the end an ArrayList will be faster, because we get there in constant time and only have to change the few remaining elements that follow it. When done precisely in the middle the LinkedList will be faster because going through n elements is quicker than moving n values.

    Bonus: While there is no way of making these two methods O(1) for an ArrayList, there actually is a way to do this in LinkedLists. Let’s say we want to go through the entire List removing and inserting elements on our way. Usually, you would start from the very beginning for each element using the LinkedList, we could also “save” the current element we’re working on with an Iterator. With the help of the Iterator, we get an O(1) efficiency for remove() and insert() when working in a LinkedList. Making it the only performance benefit I’m aware of where a LinkedList is always better than an ArrayList.

    One of the tests I saw on here only conducts the test once. But what I have noticed is that you need to run these tests many times and eventually their times will converge. Basically the JVM needs to warm up. For my particular use case I needed to add/remove items to a last that grows to about 500 items. In my tests LinkedList came out faster, with linked LinkedList coming in around 50,000 NS and ArrayList coming in at around 90,000 NS… give or take. See the code below.

     public static void main(Ssortingng[] args) { List 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 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; } 

    When should I use LinkedList ? When working with stacks mostly, or when working with buffers. When should I use ArrayList ? Only when working with indexes, otherwise you can use HashTable with linked list, then you get:

    Hash table + linked list

    • Access by key O(1),
    • Insert by key O(1),
    • Remove by key O(1)
    • and there is a sortingck to implement RemoveAll / SetAll with O(1) when using versioning

    It seems like a good solution, and in most of the cases it is, how ever you should know: HashTable takes a lot of disc space, so when you need to manage 1,000,000 elements list it can become a thing that matters. This can happen in server implementations, in clients it is rarely the case.

    Also take a look at Red-Black-Tree

    • Random access Log(n),
    • Insert Log(n),
    • Remove Log(n)