que - ¿Cuándo usar LinkedList sobre ArrayList en Java?
linkedlist vs arraylist (30)
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.
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?
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.
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);
}
}
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 .
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)
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).
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:
- No hay gran cantidad de acceso aleatorio de elemento.
- 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):
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.
ArrayList
es aleatoriamente accesible, mientras que LinkedList
es realmente barato expandir y eliminar elementos de. Para la mayoría de los casos, ArrayList
está bien.
A menos que haya creado listas grandes y haya medido un cuello de botella, probablemente nunca deba preocuparse por la diferencia.
ArrayList
y LinkedList
ambos implementos List interface
y 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:
ArrayList
operación de búsqueda es bastante rápida en comparación con la LinkedList
operación de búsqueda. get(int index)
En ArrayList
da el rendimiento de O(1)
mientras que el LinkedList
rendimiento es O(n)
.
Reason:
ArrayList
mantiene 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 LinkedList
implementa una lista doblemente enlazada que requiere el recorrido a través de todos los elementos para buscar un elemento.
2) la Deletion:
LinkedList
operación de eliminación da O(1)
rendimiento mientras que ArrayList
proporciona 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:
LinkedList
Añadir método da O(1)
rendimiento mientras que ArrayList
da O(n)
en el peor de los casos. La razón es la misma que se explica para eliminar.
4) Memory Overhead:
ArrayList
mantiene índices y datos de elementos mientras LinkedList
mantiene 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
iterator
ylistIterator
devueltas por estas clases sonfail-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 lositerator''s
métodos propios de eliminación o adición, el iteradorthrow
aConcurrentModificationException
).
¿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))
enLinkedList
comparación conArrayList(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 method
operaciones de búsqueda ( ) son rápidasArraylist (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.
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.
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) cuandoindex = 0
<--- beneficio principal deLinkedList<E>
-
remove(int index)
es O (n) (con n / 4 pasos en promedio) -
Iterator.remove()
es O (1) . <--- principal beneficio deLinkedList<E>
-
ListIterator.add(E element)
es O (1) Este es uno de los principales beneficios deLinkedList<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 deArrayList<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.
TL; DR debido a la arquitectura moderna de la computadora, ArrayList
será significativamente más eficiente para casi cualquier posible caso de uso y, por LinkedList
lo 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 LinkedList
podrí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:
Principalmente - que los nodos del
LinkedList
se 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.ArrayList
los elementos se almacenan en la memoria continua, que es exactamente lo que la arquitectura moderna de la CPU está optimizando.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 conArrayList
.
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, LinkedList
deberían brillar realmente, y ArrayList
deberí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
/ Vector
mucho 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.
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.
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).
Depende de qué operaciones harás más en la Lista.
ArrayList
Es 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.
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.
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.
Además de los otros buenos argumentos anteriores, debe observar la interfaz de los ArrayList
implementos RandomAccess
, mientras que los LinkedList
implementos Queue
.
Entonces, de alguna manera, abordan problemas ligeramente diferentes, con diferencias de eficiencia y comportamiento (consulte su lista de métodos).
Aquí está la notación Big-O en ArrayList
y LinkedList
y 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. :)
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)
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.
Sé que este es un post antiguo, pero honestamente no puedo creer que nadie mencione los LinkedList
implementos Deque
. Basta con mirar los métodos en Deque
(y Queue
); si quieres una comparación justa, intente ejecutar LinkedList
en contra ArrayDeque
y hacer una comparación de características para la función.
Si su código tiene add(0)
y remove(0)
, use a LinkedList
y es más bonito addFirst()
y removeFirst()
métodos. De lo contrario, utilizar ArrayList
.
Y, por supuesto, Guava ''s ImmutableList es su mejor amigo.
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.
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 LinkedList
esto no es cierto! Consulte ¿Existe un método rápido de concat para la lista enlazada en Java?
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 LinkedList
fue más rápido, con enlaces que LinkedList
llegan en aproximadamente 50,000 NS y ArrayList
en 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;
}
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.
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)
Las ArrayLists son buenas para escribir una vez, leer o agregar muchos, pero son malas para agregar / eliminar desde la parte frontal o central.