que - ¿Cuándo usar LinkedList sobre ArrayList en Java?

linkedlist vs arraylist

Question

Siempre he sido uno para usar simplemente:

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

Utilizo la interfaz como el nombre de tipo para la portabilidad , de modo que cuando hago preguntas como éstas puedo volver a trabajar mi código.

¿Cuándo se debe utilizar LinkedList sobre ArrayList y viceversa?

Answer 1

1) Búsqueda: la operación de búsqueda de ArrayList es bastante rápida en comparación con la operación de búsqueda de LinkedList. get (int index) en ArrayList proporciona el rendimiento de O (1) mientras que el rendimiento de LinkedList es O (n).

Motivo: ArrayList mantiene un sistema basado en índices para sus elementos, ya que utiliza implícitamente la estructura de datos de la matriz, lo que lo hace más rápido para buscar un elemento en la lista. En el otro lado, LinkedList implementa una lista doblemente enlazada que requiere el recorrido a través de todos los elementos para buscar un elemento.

2) Eliminación: La operación de eliminación de LinkedList da un rendimiento O (1), mientras que ArrayList ofrece un rendimiento variable: O (n) en el peor de los casos (al eliminar el primer elemento) y O (1) en el mejor de los casos (Al eliminar el último elemento) .

Conclusión: la eliminación del elemento LinkedList es más rápida en comparación con ArrayList.

Motivo: cada uno de los elementos de LinkedList mantiene dos punteros (direcciones), que apuntan a los dos elementos vecinos en la lista. Por lo tanto, la eliminación solo requiere un cambio en la ubicación del puntero en los dos nodos vecinos (elementos) del nodo que se eliminará. Mientras que en ArrayList, todos los elementos deben cambiarse para completar el espacio creado por el elemento eliminado.

3) Rendimiento de inserciones: el método de adición LinkedList proporciona O (1) rendimiento, mientras que ArrayList proporciona O (n) en el peor de los casos. La razón es la misma que se explica para eliminar.

4) Sobrecarga de memoria: ArrayList mantiene índices y datos de elementos, mientras que LinkedList mantiene datos de elementos y dos punteros para nodos vecinos, por lo que el consumo de memoria es alto en LinkedList comparativamente.

Hay pocas similitudes entre estas clases que son las siguientes:

Tanto ArrayList como LinkedList son implementaciones de la interfaz de lista. Ambos mantienen el orden de inserción de los elementos, lo que significa que al mostrar los elementos ArrayList y LinkedList, el conjunto de resultados tendría el mismo orden en el que los elementos se insertaron en la Lista. Ambas clases no están sincronizadas y se pueden sincronizar explícitamente mediante el método Collections.synchronizedList. El iterador y el listIterator devueltos por estas clases son a prueba de fallas (si la lista se modifica estructuralmente en cualquier momento después de que se crea el iterador, de cualquier manera, excepto a través de los métodos de eliminación o adición propios del iterador, el iterador emitirá una excepción de modificación concurrente).

¿Cuándo usar LinkedList y cuándo usar ArrayList?

1) Como se explicó anteriormente, las operaciones de inserción y extracción dan un buen rendimiento (O (1)) en LinkedList en comparación con ArrayList (O (n)). Por lo tanto, si hay un requisito de adición y eliminación frecuentes en una aplicación, entonces LinkedList es la mejor opción.

2) Las operaciones de búsqueda (método de obtención) son rápidas en ArrayList (O (1)) pero no en LinkedList (O (n)) por lo que si hay menos operaciones de agregar y eliminar y más requisitos de operaciones de búsqueda, ArrayList sería su mejor apuesta.

Answer 2

Como alguien que ha estado haciendo ingeniería de rendimiento operacional 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 hacer que las aplicaciones de un clúster expandan sus arreglos casi en sincronicidad y, por lo tanto, una gran cantidad de arreglos podría generar una falta de respuesta en la aplicación y una interrupción, mientras que bajo presión, que es un comportamiento catastrófico.

Del mismo modo, puede obtener un mejor rendimiento en una aplicación del recolector de basura predeterminado, pero una vez que obtenga aplicaciones java con pilas de 10 GB, puede terminar bloqueando la aplicación durante 25 segundos durante un GC completo que causa tiempos de espera y fallos en las aplicaciones SOA. y sopla sus SLAs si ocurre demasiado a menudo. A pesar de que el recopilador de CMS toma más recursos y no logra el mismo rendimiento en bruto, es una opción mucho mejor porque tiene una latencia más previsible y más pequeña.

ArrayList es solo una mejor opción para el rendimiento si todo lo que quiere decir con rendimiento es rendimiento y puede ignorar la latencia. En mi experiencia en mi trabajo, no puedo ignorar la latencia más desfavorable.

Answer 3

Correcto o incorrecto: ¡Ejecute la prueba localmente y decida usted mismo!

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

ArrayList , respaldado por Array , que debe ser el doble del tamaño, es peor en aplicaciones de gran volumen.

A continuación se muestra el resultado de la prueba de 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<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);
}
}

Answer 4

Es una pregunta de eficiencia. LinkedList es rápido para agregar y eliminar elementos, pero tarda en acceder a un elemento específico. ArrayList es rápido para acceder a un elemento específico, pero puede demorarse en agregarse a cualquiera de los extremos y, especialmente, demorarse en eliminarse en el medio.

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

Answer 5

Hasta ahora, parece que nadie se ha ocupado de la huella de memoria de cada una de estas listas, aparte del consenso general de que una lista LinkedList es "mucho más" que una lista de ArrayList por lo que hice algunos cálculos numéricos para demostrar exactamente cuánto ocupan ambas listas para N referencias nulas. .

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

Nota: los tamaños que se muestran para las líneas de ArrayList son para listas recortadas : en la práctica, la capacidad de la matriz de respaldo en un ArrayList es generalmente mayor que la cantidad actual de elementos.

Nota 2: (gracias a BeeOnRope) Como CompressedOops está predeterminado ahora desde mediados de JDK6 y superiores, los valores a continuación para máquinas de 64 bits básicamente coincidirán con sus equivalentes de 32 bits, a menos que, por supuesto, lo desactiven específicamente.

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 las LinkedLists .

A continuación, las fórmulas que utilicé, avíseme si he hecho algo incorrecto y lo arreglaré. ''b'' es 4 u 8 para sistemas de 32 o 64 bits, y ''n'' es el número de elementos. Tenga en cuenta que la razón de los mods es que todos los objetos en java ocuparán un espacio de múltiplos de 8 bytes, independientemente de si se usan todos 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)

Answer 6

Sí, lo sé, esta es una pregunta antigua, pero voy a tirar mis dos centavos:

LinkedList es casi siempre la elección equivocada, en cuanto al rendimiento. Hay algunos algoritmos muy específicos para los que se requiere una lista enlazada, pero esos son muy, muy raros y el algoritmo generalmente dependerá específicamente de la capacidad de la lista para insertar y eliminar elementos en el centro de la lista de manera relativamente rápida, 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 objetivo es el rendimiento, en lugar de LinkedList, también debe 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 de 2001, por lo que deberá generarlo, pero obtuve una relación de rendimiento comparable a la que se cita en el artículo de una JVM reciente).

Answer 7

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 primero debe encontrar el índice. Nota: hay diferentes versiones de add y remove .

LinkedList es más rápido en agregar y quitar, pero más lento en obtener. En resumen, LinkedList debe ser preferido si:

1. No hay gran cantidad de acceso aleatorio de elemento.
2. Hay un gran número de operaciones de agregar / quitar

=== ArrayList ===

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

=== LinkedList ===

• añadir (E e)

  • añadir al final de la lista
  • O (1)

• agregar (índice int, elemento E)

  • inserte 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
  • Necesito encontrar el elemento primero
  • En)
• eliminar (Objeto o)
  • Eliminar la primera aparición del elemento especificado.
  • Necesito 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):

Answer 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 transversal, es decir, tiene un rendimiento O (n). Esto no es obvio en el código fuente, lo que lleva a los algoritmos O (n) más lentos que si se usara ArrayList .
• Conseguir un buen rendimiento es complicado.
• Incluso cuando el rendimiento de big-O es el mismo que ArrayList , probablemente será mucho más lento de todos modos.
• Es desconcertante ver a LinkedList en la fuente porque probablemente sea la elección equivocada.

Answer 9

ArrayListes aleatoriamente accesible, mientras que LinkedListes realmente barato expandir y eliminar elementos de. Para la mayoría de los casos, ArrayListestá bien.

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

Answer 10

ArrayListy LinkedListambos implementos List interfacey sus métodos y resultados son casi idénticos. Sin embargo, hay pocas diferencias entre ellas que hacen que una sea mejor que otra dependiendo del requisito.

ArrayList Vs LinkedList

1) la Search: ArrayListoperación de búsqueda es bastante rápida en comparación con la LinkedListoperación de búsqueda. get(int index)En ArrayListda el rendimiento de O(1)mientras que el LinkedListrendimiento es O(n).

Reason: ArrayListmantiene el sistema basado en índices para sus elementos, ya que utiliza implícitamente la estructura de datos de la matriz, lo que hace que sea más rápido para buscar un elemento en la lista. En el otro lado LinkedListimplementa una lista doblemente enlazada que requiere el recorrido a través de todos los elementos para buscar un elemento.

2) la Deletion: LinkedListoperación de eliminación da O(1)rendimiento mientras que ArrayListproporciona rendimiento variable: O(n)en el peor de los casos (al eliminar el primer elemento) y O(1)en el mejor de los casos (al eliminar el último elemento).

Conclusión: la eliminación del elemento LinkedList es más rápida en comparación con ArrayList.

Motivo: el elemento LinkedList mantiene dos punteros (direcciones) que apuntan a los dos elementos vecinos en la lista. Por lo tanto, la eliminación solo requiere un cambio en la ubicación del puntero en los dos nodos vecinos (elementos) del nodo que se va a eliminar. Mientras que en ArrayList, todos los elementos deben cambiarse para completar el espacio creado por el elemento eliminado.

3) Inserts Performance: LinkedListAñadir método da O(1)rendimiento mientras que ArrayListda O(n)en el peor de los casos. La razón es la misma que se explica para eliminar.

4) Memory Overhead: ArrayListmantiene índices y datos de elementos mientras LinkedListmantiene datos de elementos y dos punteros para nodos vecinos

por lo tanto el consumo de memoria es alto en LinkedList comparativamente.

Hay pocas similitudes entre estas clases que son las siguientes:

• Tanto ArrayList como LinkedList son implementaciones de la interfaz de lista.
• Ambos mantienen el orden de inserción de los elementos, lo que significa que al mostrar los elementos ArrayList y LinkedList, el conjunto de resultados tendría el mismo orden en el que los elementos se insertaron en la Lista.
• Ambas clases no están sincronizadas y se pueden sincronizar explícitamente mediante el método Collections.synchronizedList.
• Las iteratory listIteratordevueltas por estas clases son fail-fast(si la lista se modifica estructuralmente en cualquier momento después de que se crea el iterador, de cualquier forma, excepto a través de los iterator''smétodos propios de eliminación o adición, el iterador throwa ConcurrentModificationException).

¿Cuándo usar LinkedList y cuándo usar ArrayList?

• Como se explicó anteriormente, las operaciones de inserción y extracción dan un buen rendimiento (O(1))en LinkedListcomparación con ArrayList(O(n)).

  Por lo tanto, si hay un requisito de adición y eliminación frecuentes en la aplicación, entonces LinkedList es la mejor opción.

• Las get methodoperaciones de búsqueda ( ) son rápidas Arraylist (O(1))pero no enLinkedList (O(n))

  así que si hay menos operaciones de agregar y eliminar y más requisitos de operaciones de búsqueda, ArrayList sería su mejor apuesta.

Answer 11

1) Estructura de datos subyacente

La primera diferencia entre ArrayList y LinkedList viene con el hecho de que ArrayList está respaldado por Array, mientras que LinkedList está respaldado por LinkedList. Esto conducirá a más diferencias en el rendimiento.

2) LinkedList implementa Deque

Otra diferencia entre ArrayList y LinkedList es que, aparte de la interfaz de la Lista, LinkedList también implementa la interfaz de Deque, que proporciona las primeras operaciones de entrada y salida () y varias funciones de Deque. 3) Agregar elementos en ArrayList Agregar elementos en ArrayList es una operación O (1) si no activa el cambio de tamaño de Array, en cuyo caso se convierte en O (log (n)), por otro lado, agregar un elemento en LinkedList es una operación O (1), ya que no requiere ninguna navegación.

4) Eliminar un elemento de una posición

Para eliminar un elemento de un índice en particular, por ejemplo, llamando a remove (índice), ArrayList realiza una operación de copia que lo acerca a O (n), mientras que LinkedList debe atravesar ese punto que también lo hace O (n / 2) , ya que puede atravesar desde cualquier dirección en función de la proximidad.

5) Iterando sobre ArrayList o LinkedList

La iteración es la operación O (n) para LinkedList y ArrayList donde n es un número de un elemento.

6) Recuperar el elemento de una posición

La operación de obtención (índice) es O (1) en ArrayList, mientras que su O (n / 2) en LinkedList, ya que debe atravesar hasta esa entrada. Sin embargo, en Big O, la notación O (n / 2) es solo O (n) porque ignoramos las constantes allí.

7) memoria

LinkedList usa un objeto envoltorio, Entry, que es una clase anidada estática para almacenar datos y dos nodos a continuación y anteriores, mientras que ArrayList solo almacena datos en Array.

Por lo tanto, el requisito de memoria parece menor en el caso de ArrayList que en LinkedList, excepto en el caso en que Array realiza la operación de cambio de tamaño cuando copia contenido de un Array a otro.

Si Array es lo suficientemente grande, puede necesitar mucha memoria en ese punto y desencadenar la recolección de basura, lo que puede ralentizar el tiempo de respuesta.

De todas las diferencias anteriores entre ArrayList y LinkedList, parece que ArrayList es la mejor opción que LinkedList en casi todos los casos, excepto cuando realiza una operación add () frecuente que remove () o get ().

Es más fácil modificar una lista vinculada que ArrayList, especialmente si está agregando o eliminando elementos del inicio o el final, ya que la lista vinculada mantiene las referencias de esas posiciones internamente y se puede acceder a ellas en tiempo O (1).

En otras palabras, no necesita atravesar la lista enlazada para llegar a la posición donde desea agregar elementos, en ese caso, la adición se convierte en una operación O (n). Por ejemplo, insertar o eliminar un elemento en medio de una lista enlazada.

En mi opinión, use ArrayList sobre LinkedList para la mayoría de los propósitos prácticos en Java.

Answer 12

El resumen ArrayList con ArrayDeque es preferible en muchos más casos de uso que LinkedList . Si no está seguro, simplemente comience con ArrayList .

LinkedList y ArrayList son dos implementaciones diferentes de la interfaz de lista. LinkedList implementa con una lista doblemente enlazada. ArrayList implementa con un arreglo de tamaño dinámico.

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

Para LinkedList<E>

• 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<E>
• remove(int index) es O (n) (con n / 4 pasos en promedio)
• Iterator.remove() es O (1) . <--- principal beneficio de LinkedList<E>
• ListIterator.add(E element) es O (1) Este es uno de los principales beneficios de LinkedList<E>

^{Nota: Muchas de las operaciones necesitan n / 4 pasos en promedio, un número constante de pasos en el mejor de los casos (por ejemplo, índice = 0) y n / 2 pasos en el peor de los casos (en la mitad de la lista)}

Para ArrayList<E>

• get(int index) is O (1) <--- beneficio principal de ArrayList<E>
• add(E element) se amortiza O (1) , pero O (n) en el peor de los casos, ya que la matriz se debe redimensionar y copiar
• 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, número 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<E> permite inserciones o eliminaciones de tiempo constante utilizando iteradores , pero solo acceso secuencial de elementos. En otras palabras, puede recorrer la lista hacia adelante o hacia atrás, pero encontrar una posición en la lista lleva un tiempo proporcional al tamaño de la lista. Javadoc dice que "las operaciones que indizan en la lista recorrerán la lista desde el principio o el final, lo que sea 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<E> , por otro lado, permite un acceso de lectura aleatorio rápido, para que pueda capturar cualquier elemento en tiempo constante. Pero agregar o eliminar desde cualquier lugar, pero el final requiere desplazar todos los últimos elementos, ya sea para hacer una apertura o para llenar el vacío. 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 Peor caso pero constante en promedio.

Por lo tanto, dependiendo de las operaciones que intente realizar, debe elegir las implementaciones en consecuencia. Iterar sobre cualquier tipo de Lista es prácticamente igual de barato. (Iterar sobre un ArrayList es técnicamente más rápido, pero a menos que esté haciendo algo realmente sensible al rendimiento, no debería preocuparse por esto, ambas son constantes).

Los principales beneficios de usar una lista LinkedList surgen cuando se reutilizan los iteradores existentes para insertar y eliminar elementos. Estas operaciones se pueden realizar en O (1) cambiando la lista solo localmente. En una lista de matrices, el resto de la matriz se debe mover (es decir, copiar). En el otro lado, buscar en una LinkedList vinculada significa seguir los enlaces en O (n) ( n / 2 pasos) para el peor de los casos, mientras que en una ArrayList puede calcularse matemáticamente la posición deseada y acceder a ella en O (1) .

Otro beneficio de usar una lista LinkedList surge cuando agrega o elimina 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 de la cabeza, 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 una lista LinkedList tiene más sobrecarga, ya que también se almacenan los punteros a los elementos siguiente y anterior. ArrayLists no tienen esta sobrecarga. Sin embargo, ArrayLists ocupa la mayor cantidad de memoria que se asigna para la capacidad, independientemente de si se han agregado elementos.

La capacidad inicial predeterminada de un ArrayList es bastante pequeña (10 de Java 1.4 - 1.8). Pero como la implementación subyacente es una matriz, se debe cambiar el tamaño de la matriz 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 mayor capacidad inicial.

Answer 13

TL; DR debido a la arquitectura moderna de la computadora, ArrayListserá significativamente más eficiente para casi cualquier posible caso de uso y, por LinkedListlo tanto, debe evitarse excepto en casos muy singulares y extremos.

En teoría, LinkedList tiene un O (1) para el add(E element)

También agregar un elemento a la mitad de una lista debería ser muy eficiente.

La práctica es muy diferente, ya que LinkedList es una estructura de datos hostiles de caché . Desde el punto de vista del rendimiento: hay muy pocos casos en los que LinkedListpodría ser mejor que el Cache-friendly ArrayList .

Aquí están los resultados de una prueba de referencia que inserta elementos en ubicaciones aleatorias. Como puede ver, la lista de matrices es mucho más eficiente, aunque en teoría cada inserción en el medio de la lista requerirá "mover" los n elementos posteriores de la matriz (los valores más bajos son mejores):

Trabajando en un hardware de última generación (cachés más grandes y más eficientes), los resultados son aún más concluyentes:

LinkedList toma mucho más tiempo para lograr el mismo trabajo. source Código Fuente

Existen dos motivos principales para esto:

1. Principalmente - que los nodos del LinkedListse dispersan aleatoriamente en la memoria. La RAM ("Memoria de acceso aleatorio") no es realmente aleatoria y los bloques de memoria se deben buscar en la memoria caché. Esta operación lleva tiempo, y cuando tales recuperaciones ocurren con frecuencia, las páginas de memoria en el caché deben reemplazarse todo el tiempo -> Fallos de caché -> El caché no es eficiente. ArrayListlos elementos se almacenan en la memoria continua, que es exactamente lo que la arquitectura moderna de la CPU está optimizando.

2. Se LinkedList requiere un secundario para retener los punteros de retroceso / avance, lo que significa 3 veces el consumo de memoria por valor almacenado en comparación con ArrayList.

DynamicIntArray , por cierto, es una implementación de ArrayList personalizada Int(tipo primitivo) y no Objetos; por lo tanto, todos los datos se almacenan de manera adyacente, por lo tanto, aún más eficientes.

Un elemento clave a recordar es que el costo de obtener el bloque de memoria es más significativo que el costo de acceder a una sola celda de memoria. Es por eso que el lector de 1 MB de memoria secuencial es hasta 400 veces más rápido que leer esta cantidad de datos de diferentes bloques de memoria:

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

Fuente: Números de latencia que todo programador debe saber

Solo para aclarar aún más el punto, verifique el punto de referencia de agregar elementos al principio de la lista. Este es un caso de uso en el que, en teoría, LinkedListdeberían brillar realmente, y ArrayListdeberían presentar resultados pobres o incluso peores:

Nota: este es un punto de referencia de C ++ Std lib, pero mi experiencia anterior muestra que los resultados de C ++ y Java son muy similares. Código fuente

Copia de una mayor secuencial de la memoria es una operación optimizada por la CPU moderna - el cambio de la teoría y la realidad lo que, de nuevo, ArrayList/ Vectormucho más eficiente

Créditos: Todos los puntos de referencia publicados aquí son creados por Kjell Hedström . Incluso más datos se pueden encontrar en su blog.

Answer 14

ArrayList y LinkedList tienen sus propias ventajas y desventajas.

ArrayList usa una dirección de memoria contigua en comparación con LinkedList, que usa punteros hacia el siguiente nodo. Entonces, cuando desea buscar un elemento en un ArrayList es más rápido que hacer n iteraciones con LinkedList.

Por otro lado, la inserción y eliminación en una lista enlazada son mucho más fáciles porque solo tiene que cambiar los punteros, mientras que una lista de arrays implica el uso de la operación de cambio para cualquier inserción o eliminación.

Si tiene operaciones frecuentes de recuperación en su aplicación, use un ArrayList. Si tiene una inserción y eliminación frecuentes, use una lista enlazada.

Answer 15

Comparemos los parámetros debajo de LinkedList y ArrayList:

1. Implementación

ArrayList es la implementación de matriz de tamaño variable de la interfaz de lista, mientras que

LinkedList es la implementación de la lista de enlaces dobles de la interfaz de la lista.

2. Rendimiento

• obtener (índice int) o la operación de búsqueda

  La operación ArrayList get (int index) se ejecuta en tiempo constante, es decir, O (1) mientras

  El tiempo de ejecución de la operación LinkedList get (int index) es O (n).

  La razón por la que ArrayList es más rápido que LinkedList es que ArrayList utiliza un sistema basado en índices para sus elementos, ya que internamente utiliza una estructura de datos de matriz, por otro lado,

  LinkedList no proporciona acceso basado en índices para sus elementos, ya que itera desde el principio o el final (el que esté más cerca) para recuperar el nodo en el índice de elementos especificado.

• Insertar () o añadir operación (objeto)

  Las inserciones en LinkedList son generalmente rápidas en comparación con ArrayList. En LinkedList, la adición o inserción es una operación O (1).

  Mientras que en ArrayList , si la matriz es la más completa, es decir, en el peor de los casos, hay un costo adicional de cambiar el tamaño de la matriz y copiar los elementos en la nueva matriz, lo que hace que el tiempo de ejecución de la operación de adición en ArrayList O (n), de lo contrario sea O (1) .

• quitar (int) operación

  La operación de eliminación en LinkedList es generalmente la misma que ArrayList, es decir, O (n).

  En LinkedList , hay dos métodos de eliminación sobrecargados. uno es remove () sin ningún parámetro que elimine el encabezado de la lista y se ejecute en tiempo constante O (1). El otro método de eliminación sobrecargado en LinkedList es remove (int) o remove (Object) que elimina el objeto o int pasado como parámetro. Este método atraviesa LinkedList hasta que encuentra el objeto y lo desvincula de la lista original. Por lo tanto, este método de tiempo de ejecución es O (n).

  Mientras que en ArrayList, el método remove (int) implica copiar elementos de la matriz antigua a la nueva matriz actualizada, por lo que su tiempo de ejecución es O (n).

3. Iterador inverso

LinkedList se puede iterar en dirección inversa usando descendingIterator () mientras

no hay un Iterator descendente () en ArrayList , por lo que necesitamos escribir nuestro propio código para iterar sobre la ArrayList en dirección inversa.

4. Capacidad inicial

Si el constructor no está sobrecargado, ArrayList crea una lista vacía de capacidad inicial 10, mientras que

LinkedList solo construye la lista vacía sin ninguna capacidad inicial.

5. Memoria de arriba

La sobrecarga de memoria en LinkedList es más en comparación con ArrayList, ya que un nodo en LinkedList necesita mantener las direcciones del nodo siguiente y anterior. Mientras

En ArrayList, cada índice solo contiene el objeto real (datos).

Source

Answer 16

Depende de qué operaciones harás más en la Lista.

ArrayListEs más rápido acceder a un valor indexado. Es mucho peor al insertar o eliminar objetos.

Para obtener más información, lea cualquier artículo que habla sobre la diferencia entre matrices y listas vinculadas.

Answer 17

He leído las respuestas, pero hay un escenario en el que siempre uso una lista enlazada sobre una lista de arreglos que quiero compartir para escuchar las opiniones:

Cada vez que tenía un método que devuelve una lista de datos obtenidos de una base de datos, siempre uso una lista enlazada.

Mi razonamiento fue que debido a que es imposible saber exactamente cuántos resultados estoy obteniendo, no se perderá la memoria (como en ArrayList la diferencia entre la capacidad y el número real de elementos), y no se perderá tiempo intentando duplicar la capacidad.

En cuanto a ArrayList, estoy de acuerdo en que al menos siempre debe usar el constructor con la capacidad inicial, para minimizar la duplicación de los arreglos lo más posible.

Answer 18

Joshua Bloch, el autor de LinkedList:

¿Alguien realmente usa LinkedList? Lo escribí, y nunca lo uso.

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

Lamento la respuesta por no ser tan informativo como las otras respuestas, pero pensé que sería la más interesante y autoexplicativa.

Answer 19

Además de los otros buenos argumentos anteriores, debe observar la interfaz de los ArrayListimplementos RandomAccess, mientras que los LinkedListimplementos Queue.

Entonces, de alguna manera, abordan problemas ligeramente diferentes, con diferencias de eficiencia y comportamiento (consulte su lista de métodos).

Answer 20

Aquí está la notación Big-O en ArrayListy LinkedListy también CopyOnWrite-ArrayList:

Lista de arreglo

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

Lista enlazada

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)

Basándote en estos tienes que decidir qué elegir. :)

Answer 21

ArrayList extiende AbstractList e implementa la interfaz de lista. ArrayList es una matriz dinámica.
Se puede decir que se creó básicamente para superar los inconvenientes de las matrices.

La clase LinkedList amplía AbstractSequentialList e implementa las interfaces de lista, deque y de cola.
Actuación
arraylist.get()es O (1) mientras linkedlist.get()que O (n)
arraylist.add()es O (1) y linkedlist.add()0 (1)
arraylist.contains()es O (n) y linkedlist.contains()O (n)
arraylist.next()es O (1) y linkedlist.next()O (1)
arraylist.remove()es O (n) mientras que linkedlist.remove()es O (1)
En arraylist
iterator.remove()es O (n)
mientras que En lista enlazada
iterator.remove()es O (1)

Answer 22

La operación get (i) en ArrayList es más rápida que LinkedList, porque:
ArrayList: Implementación de matriz de tamaño variable de la interfaz de lista
LinkedList: Implementación de lista de enlaces dobles de las interfaces de lista y Deque

Las operaciones que indizan en la lista recorrerán la lista desde el principio o el final, lo que esté más cerca del índice especificado.

Answer 23

Sé que este es un post antiguo, pero honestamente no puedo creer que nadie mencione los LinkedListimplementos Deque. Basta con mirar los métodos en Deque(y Queue); si quieres una comparación justa, intente ejecutar LinkedListen contra ArrayDequey hacer una comparación de características para la función.

Answer 24

Si su código tiene add(0)y remove(0), use a LinkedListy es más bonito addFirst()y removeFirst()métodos. De lo contrario, utilizar ArrayList.

Y, por supuesto, Guava ''s ImmutableList es su mejor amigo.

Answer 25

Tanto remove () como insert () tienen una eficiencia de tiempo de ejecución de O (n) tanto para ArrayLists como para LinkedLists. Sin embargo, la razón detrás del tiempo de procesamiento lineal proviene de dos razones muy diferentes:

En una ArrayList, se llega al elemento en O (1), pero al eliminar o insertar algo, se convierte en O (n) porque es necesario cambiar todos los elementos siguientes.

En una lista enlazada, se necesita O (n) para llegar al elemento deseado, ya que tenemos que comenzar desde el principio hasta que alcancemos el índice deseado. En realidad, la eliminación o inserción es constante, porque solo tenemos que cambiar 1 referencia para remove () y 2 referencias para insert ().

Cuál de los dos es más rápido para insertar y quitar depende de dónde suceda. Si estamos más cerca del comienzo, LinkedList será más rápido, porque tenemos que pasar por relativamente pocos elementos. Si estamos más cerca del final, un ArrayList será más rápido, porque llegaremos en un tiempo constante y solo tendremos que cambiar los pocos elementos restantes que lo siguen. Cuando se realiza precisamente en el medio, el LinkedList será más rápido porque recorrer n elementos es más rápido que mover n valores.

Bonificación: Si bien no hay forma de hacer estos dos métodos O (1) para una ArrayList, en realidad hay una forma de hacerlo en las listas enlazadas. Digamos que queremos recorrer toda la Lista eliminando e insertando elementos en nuestro camino. Por lo general, comenzaría desde el principio para cada elemento con LinkedList, también podríamos "guardar" el elemento actual en el que estamos trabajando con un iterador. Con la ayuda del iterador, obtenemos una eficiencia de O (1) para eliminar () e insertar () cuando se trabaja en una lista vinculada. Por lo que es el único beneficio de rendimiento que conozco donde un LinkedList siempre es mejor que un ArrayList.

Answer 26

Una característica importante de una lista vinculada (que no leí en otra respuesta) es la concatenación de dos listas. Con una matriz, esto es O (n) (+ sobrecarga de algunas reasignaciones) con una lista enlazada, esto es solo O (1) o O (2) ;-)

Importante : para Java LinkedListesto no es cierto! Consulte ¿Existe un método rápido de concat para la lista enlazada en Java?

Answer 27

Una de las pruebas que vi aquí solo lleva a cabo la prueba una vez. Pero lo que he notado es que necesita ejecutar estas pruebas muchas veces y, finalmente, sus tiempos convergerán. Básicamente la JVM necesita calentarse. Para mi caso de uso particular, necesitaba agregar / eliminar elementos a un último que crezca a aproximadamente 500 elementos. En mis pruebas, el resultado LinkedListfue más rápido, con enlaces que LinkedListllegan en aproximadamente 50,000 NS y ArrayListen torno a 90,000 NS ... más o menos. Vea el código a continuación.

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

Answer 28

Una lista de matrices es esencialmente una matriz con métodos para agregar elementos, etc. (y debería usar una lista genérica en su lugar). Es una colección de elementos a los que se puede acceder a través de un indexador (por ejemplo, [0]). Implica una progresión de un elemento a otro.

Una lista enlazada especifica una progresión de un elemento al siguiente (Elemento a -> elemento b). Puede obtener el mismo efecto con una lista de arreglos, pero una lista enlazada dice absolutamente qué elemento debe seguir al anterior.

Answer 29

Ver los tutoriales de Java - Listar implementaciones .

Answer 30

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: Big-Oh Notación

Las ArrayLists son buenas para escribir una vez, leer o agregar muchos, pero son malas para agregar / eliminar desde la parte frontal o central.