¿Cuándo usar LinkedList sobre ArrayList?

Siempre he sido de los que simplemente uso:

List names = new ArrayList(); 

Utilizo la interfaz como el nombre de tipo de portabilidad , por lo que cuando hago preguntas como estas, puedo volver a trabajar mi código.

¿Cuándo se debería utilizar LinkedList sobre ArrayList y viceversa?

Resumen ArrayList con ArrayDeque es preferible en muchos más casos de uso que LinkedList . No estoy seguro, solo comience con ArrayList .


LinkedList y ArrayList son dos implementaciones diferentes de la interfaz de la Lista. LinkedList implementa con una lista doblemente vinculada. ArrayList implementa con una matriz de redimensionamiento dynamic.

Al igual que con la lista enlazada estándar y las operaciones de matriz, los diversos métodos tendrán diferentes tiempos de ejecución algorítmicos.

Para LinkedList

  • get(int index) es O (n) (con n / 4 pasos en promedio)
  • add(E element) es O (1)
  • add(int index, E element) es O (n) (con n / 4 pasos en promedio), pero O (1) cuando index = 0 <--- beneficio principal de LinkedList
  • remove(int index) es O (n) (con n / 4 pasos en promedio)
  • Iterator.remove() es O (1) . <--- beneficio principal de LinkedList
  • ListIterator.add(E element) es O (1) Este es uno de los principales beneficios de LinkedList

Nota: Muchas de las operaciones necesitan n / 4 pasos en promedio, cantidad constante de pasos en el mejor de los casos (por ejemplo, índice = 0) y n / 2 pasos en el peor de los casos (en el medio de la lista)

Para ArrayList

  • get(int index) es O (1) <--- principal beneficio de ArrayList
  • add(E element) es O (1) amortizado, pero O (n) el peor de los casos ya que la matriz debe redimensionarse y copiarse
  • add(int index, E element) es O (n) (con n / 2 pasos en promedio)
  • remove(int index) es O (n) (con n / 2 pasos en promedio)
  • Iterator.remove() es O (n) (con n / 2 pasos en promedio)
  • ListIterator.add(E element) es O (n) (con n / 2 pasos en promedio)

Nota: Muchas de las operaciones necesitan n / 2 pasos en promedio, cantidad constante de pasos en el mejor de los casos (final de la lista), n pasos en el peor de los casos (inicio de la lista)

LinkedList permite inserciones o eliminaciones de tiempo constante mediante iteradores , pero solo acceso secuencial de elementos. En otras palabras, puede recorrer la lista hacia adelante o hacia atrás, pero encontrar un puesto en la lista lleva tiempo proporcional al tamaño de la lista. Javadoc dice que “las operaciones que indexan en la lista atravesarán la lista desde el principio o el final, lo que esté más cerca” , por lo que esos métodos son O (n) ( n / 4 pasos) en promedio, aunque O (1) para index = 0 .

ArrayList , por otro lado, permite un rápido acceso de lectura aleatorio, por lo que puede tomar cualquier elemento en tiempo constante. Pero agregar o eliminar desde cualquier lugar menos el final requiere desplazar todos los últimos elementos, ya sea para abrir o llenar el espacio. Además, si agrega más elementos que la capacidad de la matriz subyacente, se asigna una nueva matriz (1,5 veces el tamaño) y la matriz anterior se copia a la nueva, por lo que agregar a una ArrayList es O (n) en el el peor caso pero constante en promedio.

Entonces, dependiendo de las operaciones que pretenda hacer, debe elegir las implementaciones en consecuencia. Iterar sobre cualquiera de los tipos de listas es prácticamente igual de barato. (La iteración sobre una ArrayList es técnicamente más rápida, pero a menos que esté haciendo algo realmente sensible al rendimiento, no debe preocuparse por esto; ambas son constantes).

Los principales beneficios del uso de LinkedList surgen cuando reutiliza los iteradores existentes para insertar y eliminar elementos. Estas operaciones se pueden realizar en O (1) cambiando solo la lista localmente. En una lista de matriz, el rest de la matriz debe moverse (es decir, copiarse). Por otro lado, buscar en LinkedList significa seguir los enlaces en O (n) ( n / 2 pasos) para el peor caso, mientras que en ArrayList la posición deseada se puede calcular matemáticamente y se puede acceder en O (1) .

Otro beneficio de usar LinkedList surge cuando agrega o quita del encabezado de la lista, ya que esas operaciones son O (1) , mientras que son O (n) para ArrayList . Tenga en cuenta que ArrayDeque puede ser una buena alternativa a LinkedList para agregar y eliminar desde el ArrayDeque , pero no es una List .

Además, si tiene listas grandes, tenga en cuenta que el uso de la memoria también es diferente. Cada elemento de LinkedList tiene más sobrecarga ya que los punteros a los elementos siguiente y anterior también se almacenan. ArrayLists no tiene esta sobrecarga. Sin embargo, ArrayLists toma tanta memoria asignada para la capacidad, independientemente de si los elementos se han agregado realmente.

La capacidad inicial predeterminada de una ArrayList es bastante pequeña (10 de Java 1.4 – 1.8). Pero dado que la implementación subyacente es una matriz, la matriz debe redimensionarse si agrega muchos elementos. Para evitar el alto costo del cambio de tamaño cuando sabe que va a agregar muchos elementos, construya el ArrayList con una capacidad inicial más alta.

Hasta ahora, nadie parece haber abordado la huella de memoria de cada una de estas listas, además del consenso general de que una LinkedList es “mucho más” que una LinkedList de ArrayList así que hice algunos cálculos numéricos para demostrar exactamente cuánto ocupan ambas listas para N referencias nulas. .

Como las referencias son 32 o 64 bits (incluso cuando son nulas) en sus sistemas relativos, he incluido 4 conjuntos de datos para LinkedLists y ArrayLists de 32 y 64 bits.

Nota: Los tamaños mostrados para las líneas ArrayList son para listas recortadas . En la práctica, la capacidad de la matriz de respaldo en una ArrayList es generalmente mayor que su conteo de elementos actual.

Nota 2: (gracias BeeOnRope) Como CompressedOops está predeterminado ahora a partir de mediados de JDK6 y superior, los valores siguientes para máquinas de 64 bits básicamente coincidirán con sus contrapartes de 32 bits, a menos, por supuesto, que específicamente lo desactive.


Gráfico de LinkedList y ArrayList No. de elementos x Bytes


El resultado muestra claramente que LinkedList es mucho más que ArrayList , especialmente con un alto número de elementos. Si la memoria es un factor, manténgase alejado de LinkedLists .

Las fórmulas que utilicé siguen, avíseme si he hecho algo mal y lo arreglaré. ‘b’ es 4 u 8 para sistemas de 32 o 64 bits, y ‘n’ es la cantidad de elementos. Tenga en cuenta que el motivo de los mods se debe a que todos los objetos en java ocuparán un múltiplo de 8 bytes de espacio independientemente de si se usa todo o no.

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 es lo que quieres. LinkedList es casi siempre un error (de rendimiento).

Por qué LinkedList apesta:

  • Utiliza muchos objetos de memoria pequeños y, por lo tanto, afecta el rendimiento en todo el proceso.
  • Muchos objetos pequeños son malos para la localidad de caché.
  • Cualquier operación indexada requiere un recorrido, es decir, tiene un rendimiento O (n). Esto no es obvio en el código fuente, lo que lleva a que los algoritmos O (n) sean más lentos que si se usara ArrayList .
  • Obtener un buen rendimiento es complicado.
  • Incluso cuando el rendimiento del gran O sea el mismo que ArrayList , probablemente sea significativamente más lento de todos modos.
  • Es desagradable ver a LinkedList en su fuente porque probablemente sea la opción incorrecta.

Como alguien que ha estado haciendo ingeniería de rendimiento operativo en servicios web SOA a gran escala durante aproximadamente una década, preferiría el comportamiento de LinkedList sobre ArrayList. Si bien el rendimiento en estado estable de LinkedList es peor y por lo tanto podría llevar a comprar más hardware, el comportamiento de ArrayList bajo presión podría llevar a que las aplicaciones de un clúster expandieran sus matrices casi sincronicidad y para grandes tamaños de matriz podría llevar a falta de capacidad de respuesta en la aplicación y una interrupción, bajo presión, que es un comportamiento catastrófico.

De manera similar, puede obtener un mejor rendimiento en una aplicación del recolector de basura temporal predeterminado, pero una vez que obtiene aplicaciones Java con montones de 10 GB puede cerrar la aplicación durante 25 segundos durante un GC completo que causa tiempos de espera y fallas en las aplicaciones SOA y explota tus SLA si ocurre con demasiada frecuencia. Aunque el recostackdor de CMS necesita más recursos y no logra el mismo rendimiento sin procesar, es una opción mucho mejor porque tiene una latencia más predecible y menor.

ArrayList es solo una mejor opción para el rendimiento si lo único que quiere decir es rendimiento y puede ignorar la latencia. En mi experiencia en mi trabajo, no puedo ignorar la latencia del peor de los casos.

 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) 

Algoritmos: notación Big-Oh

ArrayLists es bueno para write-once-read-many o appenders, pero es malo para agregar / eliminar de la parte frontal o central.

Sí, lo sé, esta es una pregunta antigua, pero voy a dar mi granito de arena:

LinkedList es casi siempre la opción incorrecta, en cuanto a rendimiento. Existen algunos algoritmos muy específicos en los que se necesita una lista enlazada, pero estos son muy, muy raros y el algoritmo generalmente dependerá específicamente de la capacidad de LinkedList para insertar y eliminar elementos en el medio de la lista con relativa rapidez, una vez que haya navegado allí con un ListIterator.

Hay un caso de uso común en el que LinkedList supera a ArrayList: el de una cola. Sin embargo, si su objective es el rendimiento, en lugar de LinkedList también debería considerar usar un ArrayBlockingQueue (si puede determinar un límite superior en el tamaño de su cola antes de tiempo, y puede permitirse asignar toda la memoria por adelantado) o esta implementación CircularArrayList . (Sí, es del 2001, por lo que deberá generarlo, pero obtuve índices de rendimiento comparables a lo que se cita en el artículo recientemente en una JVM reciente)

Es una pregunta de eficiencia. LinkedList es rápido para agregar y eliminar elementos, pero ralentiza el acceso a un elemento específico. ArrayList es rápido para acceder a un elemento específico, pero puede ser lento para agregar a cualquier extremo, y especialmente lento para eliminar en el medio.

Array vs ArrayList vs LinkedList vs Vector va más en profundidad, al igual que Linked List .

Correcto o incorrecto: ¡ejecuta la prueba localmente y decide por ti mismo!

Editar / Eliminar es más rápido en LinkedList que ArrayList .

ArrayList , respaldado por Array , que necesita ser el doble del tamaño, es peor en la aplicación de gran volumen.

A continuación se muestra el resultado de la prueba de la unidad para cada operación. El tiempo se da en nanosegundos.


 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 

Aquí está el código:

 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 stringList = Arrays.asList(strings); List arrayList = new ArrayList(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 stringList = Arrays.asList(strings); watch.start(); List linkedList = new LinkedList(); 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 arrayList = new ArrayList(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 linkedList = new LinkedList(); 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 stringList = Arrays.asList(strings); List arrayList = new ArrayList(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 stringList = Arrays.asList(strings); List linkedList = new LinkedList(); 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 stringList = Arrays.asList(strings); List arrayList = new ArrayList(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 linkedList = new LinkedList(); 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 stringList = Arrays.asList(strings); List arrayList = new ArrayList(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 linkedList = new LinkedList(); 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 es esencialmente una matriz. LinkedList se implementa como una lista de doble LinkedList .

El get es bastante claro. O (1) para ArrayList , porque ArrayList permite el acceso aleatorio mediante el uso de índice. O (n) para LinkedList , porque necesita encontrar el índice primero. Nota: hay diferentes versiones de add y remove .

LinkedList es más rápido en agregar y eliminar, pero más lento en obtener. En resumen, LinkedList debería ser preferido si:

  1. no hay una gran cantidad de acceso aleatorio de elemento
  2. hay una gran cantidad de operaciones de agregar / eliminar

=== ArrayList ===

  • agregar (E e)
    • agregar al final de ArrayList
    • requiere un costo de redimensionamiento de la memoria.
    • O (n) peor, O (1) amortizado
  • add (índice int, elemento E)
    • agregar a una posición de índice específica
    • requiere cambio y posible cambio de tamaño de la memoria
    • En)
  • eliminar (índice int)
    • eliminar un elemento especificado
    • requiere cambio y posible cambio de tamaño de la memoria
    • En)
  • eliminar (Objeto o)
    • eliminar la primera aparición del elemento especificado de esta lista
    • primero debe buscar el elemento y luego cambiar y modificar el costo de redimensionamiento de la memoria
    • En)

=== LinkedList ===

  • agregar (E e)

    • agregar al final de la lista
    • O (1)
  • add (índice int, elemento E)

    • insertar en la posición especificada
    • necesito encontrar el puesto primero
    • En)
  • retirar()
    • eliminar el primer elemento de la lista
    • O (1)
  • eliminar (índice int)
    • eliminar elemento con índice especificado
    • necesita encontrar el elemento primero
    • En)
  • eliminar (Objeto o)
    • eliminar la primera aparición del elemento especificado
    • necesita encontrar el elemento primero
    • En)

Aquí hay una figura de programcreek.com ( add y remove son el primer tipo, es decir, agregar un elemento al final de la lista y eliminar el elemento en la posición especificada en la lista):

enter image description here

ArrayList es accesible al azar, mientras que LinkedList es realmente barato de expandir y eliminar elementos. Para la mayoría de los casos, ArrayList está bien.

A menos que haya creado grandes listas y medido un cuello de botella, probablemente nunca tenga que preocuparse por la diferencia.

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 retrieve 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. Mientras

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


Fuente

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 retrieval 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 trigger 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) Retrieving 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 trigger 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.
Actuación
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(String[] 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 trick 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)