¿Cuándo usar LinkedList sobre ArrayList en Java?

3123

Siempre he sido uno para usar simplemente:

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

Utilizo la interfaz como el nombre del tipo para la portabilidad , de modo que cuando hago preguntas como estas, puedo modificar mi código.

¿Cuándo debe LinkedListusarse ArrayListy viceversa?

sdellysse
fuente
44
Ver también: Array versus lista enlazada
Hawkeye Parker
1
Solo vea la cita del autor de LinkedList stackoverflow.com/a/42529652/2032701 y obtendrá una idea práctica del problema.
Ruslan
Consulte la publicación Java LinkedList vs ArrayList , que describe las diferencias e incluye algunas pruebas de rendimiento.
Alonana

Respuestas:

3371

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


LinkedListy ArrayListson dos implementaciones diferentes de la interfaz List. LinkedListlo implementa con una lista doblemente vinculada. ArrayListlo implementa con una matriz de redimensionamiento dinámico.

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

por LinkedList<E>

  • get(int index)es O (n) (con n / 4 pasos en promedio), pero O (1) cuándo index = 0o index = list.size() - 1(en este caso, también puede usar getFirst()y getLast()). Uno de los principales beneficios de LinkedList<E>
  • add(int index, E element)es O (n) (con n / 4 pasos en promedio), pero O (1) cuando index = 0o index = list.size() - 1(en este caso, también puede usar addFirst()y addLast()/ add()). Uno de los principales beneficios de LinkedList<E>
  • remove(int index)es O (n) (con n / 4 pasos en promedio), pero O (1) cuándo index = 0o index = list.size() - 1(en este caso, también puede usar removeFirst()y removeLast()). Uno de los principales beneficios de LinkedList<E>
  • Iterator.remove()es O (1) . Uno de los principales beneficios de LinkedList<E>
  • ListIterator.add(E element)es O (1) . 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 el medio de la lista)

por ArrayList<E>

  • get(int index)es O (1) . Principal beneficio de ArrayList<E>
  • add(E element)es O (1) amortizado, pero O (n) en el peor de los casos ya que la matriz debe ser redimensionada y copiada
  • 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, un 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 caminar la lista hacia adelante o hacia atrás, pero encontrar una posición en la lista lleva tiempo proporcional al tamaño de la lista. Javadoc dice que "las operaciones que se 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<E>, por otro lado, permita un acceso de lectura aleatorio rápido, para que pueda tomar cualquier elemento en tiempo constante. Pero agregar o eliminar de cualquier lugar que no sea el final requiere cambiar todos los últimos elementos, ya sea para hacer una abertura o 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 en la nueva, por lo que agregar a an ArrayListes O (n) en el peor de los casos caso pero constante en promedio.

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

Los principales beneficios de usar un LinkedListsurgen cuando reutiliza iteradores existentes para insertar y eliminar elementos. Estas operaciones se pueden hacer en O (1) cambiando la lista solo localmente. En una lista de matriz, el resto de la matriz debe moverse (es decir, copiarse). Por otro lado, buscar en un LinkedListmedio siguiendo los enlaces en O (n) ( n / 2 pasos) para el peor de los casos, mientras que en una ArrayListposición deseada se puede calcular matemáticamente y acceder a ella en O (1) .

Otro beneficio de usar un LinkedListsurgir 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 ArrayDequepuede ser una buena alternativa LinkedListpara agregar y quitar de la cabeza, pero no es un List.

Además, si tiene listas grandes, tenga en cuenta que el uso de la memoria también es diferente. Cada elemento de a LinkedListtiene más sobrecarga ya que también se almacenan los punteros a los elementos siguientes y anteriores. ArrayListsNo tengo esta sobrecarga. Sin embargo, ArrayListstome tanta memoria como se asigne para la capacidad, independientemente de si los elementos se han agregado realmente.

La capacidad inicial predeterminada de un ArrayListes bastante pequeña (10 de Java 1.4 - 1.8). Pero dado que 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 de cambiar el tamaño cuando sabe que va a agregar muchos elementos, construya ArrayListcon una capacidad inicial más alta.

Jonathan Tran
fuente
183
Olvidé mencionar los costos de inserción. En una LinkedList, una vez que tiene la posición correcta, la inserción cuesta O (1), mientras que en una ArrayList sube a O (n): todos los elementos que pasen el punto de inserción deben moverse.
David Rodríguez - dribeas
26
Con respecto al uso de Vector: Realmente no hay necesidad de recurrir a Vector. La forma de hacerlo es con su implementación de Lista preferida y una llamada a synchronizedList para darle un contenedor sincronizado. Ver: java.sun.com/docs/books/tutorial/collections/implementations/…
Ryan Cox
69
No, para LinkedList, get sigue siendo O (n) incluso si conoce la posición, porque para llegar a esa posición, la implementación subyacente tiene que recorrer los "siguientes" punteros de la lista vinculada para llegar al valor de esa posición. No existe el acceso aleatorio. Para la posición 2, caminar los punteros puede ser barato, pero para la posición 1 millón, no es tan barato. El punto es que es proporcional a la posición, lo que significa que es O (n).
Jonathan Tran
53
@ Kevin Puede importar que la memoria esté "muy cerca". El hardware almacenará en caché bloques contiguos de memoria (RAM dinámica) en RAM estática más rápida en el caché L1 o L2. En teoría y la mayoría de las veces prácticamente, la memoria puede tratarse como acceso aleatorio. Pero en realidad, la lectura secuencial de la memoria será un poco más rápida que en orden aleatorio. Para un ciclo de rendimiento crítico, esto podría importar. Lo llaman "localidad espacial" o localidad de referencia .
Jonathan Tran
92
No hay tal cosa como O(n/2)o O(n/4). La notación O grande le dice cómo una operación escala con una n mayor . y una operación que necesita n/2pasos se escala exactamente como una operación que necesita npasos, razón por la cual se eliminan los sumandos o factores constantes. O(n/2)y O(n/4)son ambos justos O(n). LinkedListy ArrayListtener diferentes factores constantes de todos modos, por lo que no tendría sentido comparar O(n/2)uno de uno con otro O(n/4)del otro, ambos solo denotan operaciones de escala lineal.
Holger
630

Hasta el momento, nadie parece haber abordado la huella de memoria de cada una de estas listas, además del consenso general de que a LinkedListes "mucho más" que un, ArrayListasí que hice algunos cálculos numéricos para demostrar exactamente cuánto ocupan ambas listas para N referencias nulas.

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

Nota: Los tamaños que se muestran para las ArrayListlíneas son para listas recortadas : en la práctica, la capacidad de la matriz de respaldo en ArrayListgeneral es mayor que su recuento de elementos actual.

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


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


El resultado muestra claramente que LinkedListes mucho más que eso ArrayList, especialmente con un recuento de elementos muy alto. Si la memoria es un factor, manténgase alejado 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 el número de elementos. Tenga en cuenta que la razón de las modificaciones es porque todos los objetos en Java ocuparán un espacio múltiple de 8 bytes, independientemente de si se usa o no.

Lista de arreglo:

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)

Lista enlazada:

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)

Numeron
fuente
2
Es bastante interesante ver que LinkedList requiere tanta memoria como ArrayList para almacenar un solo elemento. ¡Qué poco intuitivo! ¿Qué sucede si ejecuta su ejemplo con -XX: + UseCompressedOops?
jontejj
215
El problema con tus matemáticas es que tu gráfica exagera mucho el impacto. Está modelando objetos que cada uno contiene solo un int, por lo que 4 u 8 bytes de datos. En la lista vinculada, hay esencialmente 4 "palabras" de sobrecarga. Por lo tanto, su gráfico da la impresión de que las listas vinculadas usan "cinco veces" el almacenamiento de listas de matrices. Esto está mal. La sobrecarga es de 16 o 32 bytes por objeto, como un ajuste aditivo, no un factor de escala.
Heath Hunnicutt
66
Ninguno de los objetos ArrayList / LinkedList / Node contiene solo un int, por lo que no entiendo lo que está diciendo allí. Reescribí 'objeto arriba' a 'encabezado de objeto' para aclararlo: hay un encabezado de 8 bytes para cada objeto, independientemente del sistema, y ​​sí, eso incluye todos los objetos de Nodo en LinkedList, que se cuentan correctamente todo lo que puedo contar. Por cierto, en mirarlo de nuevo, he encontrado un par de otros problemas con mis matemáticas en LinkedList que en realidad hace que la brecha y ArrayList peor . Estoy feliz de seguir actualizándolo, así que no dude en aclarar y elaborar más.
Numeron
66
Debe tenerse en cuenta que CompressedOopses por defecto ahora en todos los JDK recientes (7, 8 y actualizaciones de 6 durante unos años), de modo de 64 bits no hará una diferencia en ArrayListo LinkedListtamaños, a menos que haya desactivado de forma explícita Uy comprimido para alguna razón.
BeeOnRope
1
@jontejj el aumento de capacidad predeterminado es del 50%, por lo que cuando se llena un ArrayListsin especificar una capacidad inicial, seguirá utilizando una cantidad de memoria significativamente menor que a LinkedList.
Holger
244

ArrayListes lo que quieres LinkedListcasi siempre es un error (de rendimiento).

Por qué LinkedListapesta:

  • Utiliza muchos objetos pequeños de memoria 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 algoritmos O (n) más lentos que si ArrayListse usaran.
  • Conseguir un buen rendimiento es complicado.
  • Incluso cuando el rendimiento de Big-O es el mismo ArrayList, probablemente será significativamente más lento de todos modos.
  • Es discordante ver LinkedListen la fuente porque probablemente sea la elección incorrecta.
Tom Hawtin - tackline
fuente
237
Lo siento. te marcó LinkedList no apesta. Hay situaciones en las que LinkedList es la clase correcta para usar. Estoy de acuerdo en que no hay muchas situaciones en las que sea mejor que una lista de matrices, pero existen. ¡Educar a las personas que hacen cosas tontas!
David Turner
40
Lamento ver que hay muchos votos negativos para esto. De hecho, hay muy pocas razones para usar LinkedList de Java. Además del mal rendimiento, también utiliza mucha más memoria que las otras clases de listas concretas (cada nodo tiene dos punteros adicionales y cada nodo es un objeto contenedor separado con los bytes de sobrecarga adicionales que van con ellos).
Kevin Brock
42
Esta es una de las respuestas más útiles aquí. Es una pena que muchos programadores no entiendan (a) la diferencia entre los tipos de datos abstractos y las implementaciones concretas, y (b) la importancia del mundo real de los factores constantes y la sobrecarga de memoria en la determinación del rendimiento.
Porculus
50
-1: Esta es una vista más bien parpadeada. Sí, es cierto que ArrayList es una herramienta muy versátil. Sin embargo, tiene sus limitaciones. Hay casos en los que esto le causará problemas, y tendrá que usar LinkedList. Por supuesto, es una solución muy especializada y, como cualquier herramienta especializada, en la mayoría de los casos es superada por una versátil. Pero eso no significa que "apesta" o algo así, solo tienes que saber cuándo usarlo.
Malcolm
27
@DavidTurner: Existen, pero creo que el punto de Tom era que si tienes que preguntar, probablemente quieras ArrayList.
user541686
139

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 conducir a la compra de más hardware, el comportamiento de ArrayList bajo presión podría llevar a que las aplicaciones en un clúster expandan sus matrices casi sincrónicamente y para tamaños de matriz grandes podría provocar una falta de capacidad de respuesta en la aplicación y un corte de energía, bajo presión, que es un comportamiento catastrófico.

Del mismo modo, puede obtener un mejor rendimiento en una aplicación desde el recolector de basura con rendimiento predeterminado, pero una vez que obtiene aplicaciones Java con montones de 10 GB, puede terminar bloqueando la aplicación durante 25 segundos durante un GC completo que causa tiempos de espera y fallas en las aplicaciones SOA y sopla sus SLA si ocurre con demasiada frecuencia. Aunque el recopilador de CMS toma más recursos y no logra el mismo rendimiento bruto, es una opción mucho mejor porque tiene una latencia más predecible 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 peor latencia.

lamont
fuente
8
¿No sería otra solución administrar el tamaño de la lista mediante programación mediante el método de ArrayList allowCapacity ()? Mi pregunta es ¿por qué se almacenan tantas cosas en un montón de estructuras de datos frágiles cuando podrían almacenarse mejor en un mecanismo de almacenamiento en caché o db? El otro día tuve una entrevista en la que juraron de arriba abajo sobre los males de ArrayList, pero vine aquí y descubrí que el análisis de complejidad es mejor. GRAN PUNTO PARA DISCUSIÓN, AUNQUE. ¡GRACIAS!
ingyhere
22
una vez que llegue aplicaciones Java con 10 GB montones puede terminar encerrar a la aplicación durante 25 segundos durante un GC completas que hace que los tiempos de espera realidad con LinkedList asesinas a la recolector de basura durante los GC completo, tiene que iterar el excesivamente grande Lista enlazada con el fallo de caché de cada nodo
bestsss
55
Esa es ... una solución horrible. básicamente depende de que el GC lo limpie, lo cual es increíblemente costoso, cuando puede llamar a sureCapacity () en una lista de arrays ...
Philip Devine
55
@Andreas: A LinkedList siempre asigna cinco veces la memoria que un conjunto simple de referencias, por lo que un ArrayListrequerimiento temporal de 2.5 veces todavía consume mucha menos memoria, incluso cuando la memoria no se recupera. Dado que la asignación de matriz grande omite el espacio de Eden, no tienen ningún impacto en el comportamiento de GC, a menos que realmente no haya suficiente memoria, en cuyo caso, LinkedListexplotaron mucho antes ...
Holger
55
@Andreas El otro problema es cómo se asigna la memoria. LinkedListsolo necesita un pequeño trozo de memoria libre para asignar al siguiente elemento. ArrayListnecesitará un bloque de espacio libre grande y continuo para asignar la matriz redimensionada. Si el montón se fragmenta, GC podría terminar reordenando todo el montón solo para liberar un bloque de memoria adecuado.
Piotr Kusmierczyk
128
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

Las ArrayLists son buenas para escribir una vez, leer muchas o anexos, pero son malas para agregar / quitar desde el frente o en el medio.

Michael Munsey
fuente
42
No puede comparar los valores de O grande directamente sin pensar en factores constantes. Para listas pequeñas (y la mayoría de las listas son pequeñas), el O (N) de ArrayList es más rápido que el O (1) de LinkedList.
Porculus
44
No me importa el rendimiento de las listas pequeñas, y tampoco lo hace mi computadora a menos que se use de alguna manera en un bucle.
Maarten Bodewes
45
LinkedList no puede realmente insertarse en el medio O(1). Tiene que recorrer la mitad de la lista para encontrar el punto de inserción.
Thomas Ahle
8
LinkedList: insertar en el medio O (1) - ¡ES INCORRECTO! Descubrí que incluso la inserción en la décima posición del tamaño de LinkedList es más lenta que insertar un elemento en la posición 1/10 de una ArrayList. Y aún peor: el final de la colección. insertar en las últimas posiciones (no la última) de ArrayList es más rápido que en las últimas posiciones (no la última) de LinkedList
kachanov
14
@kachanov La inserción en a LinkedList es O(1) si tiene un iterador en la posición de inserción , ListIterator.addes decir, supuestamente es O(1)para a LinkedList.
HA SALIDO - Anony-Mousse
107

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

LinkedList es casi siempre la elección incorrecta, en cuanto al rendimiento. Hay algunos algoritmos muy específicos en los que se requiere LinkedList, pero 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 relativamente rápido, 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 debería considerar usar un ArrayBlockingQueue (si puede determinar un límite superior en el tamaño de la cola con anticipación 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 índices de rendimiento comparables a lo que se cita en el artículo en una JVM reciente)

Daniel Martin
fuente
39
Desde Java 6 puedes usar ArrayDeque. docs.oracle.com/javase/6/docs/api/java/util/ArrayDeque.html
Thomas Ahle
1
ArrayDequees más lento que a LinkedListmenos que todas las operaciones estén en el mismo extremo. Está bien cuando se usa como una pila, pero no hace una buena cola.
Jeremy List
2
Falso, al menos para la implementación de Oracle en jdk1.7.0_60 y en la siguiente prueba. Creé una prueba en la que realizo un ciclo de 10 millones de veces y tengo un Deque de 10 millones de enteros aleatorios. Dentro del ciclo, sondeo un elemento y ofrezco un elemento constante. En mi computadora, LinkedList es más de 10 veces más lenta que ArrayDeque y usa menos memoria). La razón es que, a diferencia de ArrayList, ArrayDeque mantiene un puntero al encabezado de la matriz para que no tenga que mover todos los elementos cuando se quita el encabezado.
Henno Vermeulen
66
ArrayDequees probable que sea más rápido que Stackcuando se usa como una pila, y más rápido que LinkedListcuando se usa como una cola.
akhil_mittal
3
Tenga en cuenta que el comentario de akhil_mittal es una cita de la ArrayDequedocumentación.
Stuart Marks
65

Es una pregunta de eficiencia. LinkedListes rápido para agregar y eliminar elementos, pero lento para acceder a un elemento específico. ArrayListes rápido para acceder a un elemento específico, pero puede ser lento para agregar a cualquiera de los extremos, 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 .

dgtized
fuente
54

Correcto o incorrecto: ejecute la prueba localmente y decida por usted mismo.

Editar / Eliminar es más rápido LinkedListque 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 unitaria 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);
    }
}
Ceniza
fuente
1
ArrayList no necesita duplicarse, para ser precisos. Por favor revise las fuentes primero.
Danubian Sailor
Cabe señalar que su ejemplo es defectuoso ... Está eliminando de una cadena de entre 18 + [2, 12] bytes ("true0false", "true500000false"), en promedio 25 bytes, que son los tamaños de los elementos en el medio. Se sabe que a medida que aumenta el tamaño del byte del elemento, la lista vinculada funciona mejor, a medida que aumenta el tamaño de la lista, una matriz contigua (lista) funcionará mejor. Lo más importante es que está haciendo .equals () en cadenas, lo cual no es una operación barata. Si en cambio usaste números enteros, creo que habría una diferencia.
Centril
2
"... es peor en aplicaciones de gran volumen ": este es un malentendido. LinkedListtiene mucha más sobrecarga de memoria porque para cada elemento hay un objeto de nodo con cinco campos. En muchos sistemas que genera 20 bytes de sobrecarga. La sobrecarga de memoria promedio por elemento ArrayListes de una palabra y media, que hace 6 bytes y 8 bytes en el peor de los casos.
Lii
1
He hecho una mejor versión de su punto de referencia aquí, con resultados : el rendimiento de agregado para el arraylist es artificialmente bajo para el suyo, porque addAll proporciona una matriz de almacenamiento de EXACTAMENTE tamaño inicial, por lo que el primer inserto siempre activa un arraycopy. Además, esto incluye ciclos de calentamiento para permitir la compilación JIT antes de que se recopilen los datos.
BobMcGee
44
@BillK desde Java 8, puede usar removeIf(element -> condition)donde encaja, que puede ser significativamente más rápido para un ArrayList, en comparación con el bucle y la eliminación a través del iterador, ya que no es necesario cambiar todo el resto para cada elemento individual. Si esto funciona mejor o peor de lo que LinkedListdepende del escenario particular, como a LinkedListes O (1) en teoría, pero eliminar solo un nodo requiere varios accesos a la memoria, que pueden exceder fácilmente el número necesario para ArrayListeliminar un número significativo de elementos .
Holger
50

ArrayListEs esencialmente una matriz. LinkedListse implementa como una lista de doble enlace.

El getes bastante claro. O (1) para ArrayList, porque ArrayListpermite el acceso aleatorio usando el índice. O (n) para LinkedList, porque primero necesita encontrar el índice. Nota: hay diferentes versiones de addy remove.

LinkedListes más rápido en agregar y quitar, pero más lento en obtener. En resumen, LinkedListdebe preferirse si:

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

=== ArrayList ===

  • agregar (E e)
    • agregar al final de ArrayList
    • requieren memoria de cambio de tamaño de costo.
    • O (n) peor, O (1) amortizado
  • add (int int, elemento E)
    • agregar a una posición de índice específica
    • requieren cambios y posible costo de cambio de tamaño de memoria
    • En)
  • eliminar (int index)
    • eliminar un elemento especificado
    • requieren cambios 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 debe buscar el elemento, y luego cambiar el costo de cambio de tamaño de memoria posible
    • En)

=== LinkedList ===

  • agregar (E e)

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

    • insertar en la posición especificada
    • necesita encontrar la posición primero
    • En)
  • eliminar()
    • eliminar el primer elemento de la lista
    • O (1)
  • eliminar (int index)
    • 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 ( addy removeson el primer tipo, es decir, agregue un elemento al final de la lista y elimine el elemento en la posición especificada en la lista):

ingrese la descripción de la imagen aquí

Ryan
fuente
3
"LinkedList es más rápido que agregar / quitar". Incorrecto, verifique la respuesta anterior stackoverflow.com/a/7507740/638670
Nerrve
49

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 informativa como las otras respuestas, pero pensé que sería la más interesante y explicativa.

Ruslan
fuente
34

ArrayListes accesible al azar, mientras que LinkedListes realmente barato expandir y eliminar elementos. 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 tendrá que preocuparse por la diferencia.

Dustin
fuente
15
LinkedList no es barato para agregar elementos. Casi siempre es más rápido agregar un millón de elementos a una ArrayList que agregarlos a una LinkedList. Y la mayoría de las listas en el código del mundo real no tienen ni un millón de elementos.
Porculus
10
En cualquier momento, conoce el costo de agregar un artículo a su LinkedList. La ArrayList no lo hace (en general). Agregar un solo elemento a una ArrayList que contenga un millón de elementos podría llevar mucho tiempo: es una operación O (n) más el doble de almacenamiento a menos que haya asignado previamente espacio. Agregar un elemento a un LinkedList es O (1). Mi última declaración se mantiene.
Dustin
44
Agregar un solo elemento a una ArrayList es O (1) sin importar que sea 1 millón o 1 billón. Agregar un elemento a un LinkedList también es O (1). "Agregar" significa AGREGAR AL FINAL.
kachanov
Debes haber leído la implementación de manera diferente que yo. En mi experiencia, copiar una matriz de mil millones de elementos lleva más tiempo que copiar una matriz de un millón de elementos.
Dustin
66
@kachanov debes entender mal a Dustin. A menos que haya declarado una matriz de mil millones de elementos, eventualmente necesitará cambiar el tamaño de su matriz, en cuyo caso deberá copiar todos los elementos en una nueva matriz más grande, por lo que a veces obtendrá O (N); sin embargo, con una lista vinculada siempre obtener O (1)
Stan R.
29

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 algunos casos muy únicos y extremos.


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

También agregar un elemento en el medio 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 tener un mejor rendimiento que el compatible con caché ArrayList .

Estos son los resultados de una prueba de referencia que inserta elementos en ubicaciones aleatorias. Como puede ver, la lista de la matriz 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):

ingrese la descripción de la imagen aquí

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:

ingrese la descripción de la imagen aquí

LinkedList tarda mucho más tiempo en realizar el mismo trabajo. código fuente

Existen dos motivos principales para esto:

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

  2. Se LinkedList requiere secundaria para mantener apuntadores hacia atrás / adelante, 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 que contiene Int(tipo primitivo) y no Objetos, por lo tanto, todos los datos se almacenan de forma adyacente, por lo tanto, son aún más eficientes.

Un elemento clave para recordar es que el costo de recuperar 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 x400 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 el punto, verifique el punto de referencia de agregar elementos al comienzo de la lista. Este es un caso de uso donde, en teoría, LinkedListdebería brillar realmente, y ArrayListdebería presentar resultados pobres o incluso peores:

ingrese la descripción de la imagen aquí

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

Copiar una gran cantidad de memoria secuencial es una operación optimizada por las CPU modernas, que cambia la teoría y hace que, de nuevo, ArrayList/ sea Vectormucho más eficiente


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

Lior Bar-On
fuente
¡No llamaría a una cola única o extrema! Una cola quince es mucho más fácil de implementar en una LinkedList en lugar de una ArrayList. En realidad, es una pesadilla en una ArrayList, ya que tiene que rastrear su propio inicio, detener y hacer su propia reasignación, también podría usar una matriz, pero una Lista Vinculada ES un quince. No estoy seguro de la implementación de Java, pero un LinkedList puede hacer O (1) para las operaciones de cola y de cola (requiere un puntero especial al elemento de cola para la eliminación, que supongo que Java tiene pero no he verificado dos veces .)
Bill K
24

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

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

Jesse Wilson
fuente
3
Para listas pequeñas, ArrayList.add (0) siempre será más rápido que LinkedList.addFirst ().
Porculus
1
@Porculus constantemente escucho este argumento de que para listas pequeñas ArrayList.add (0) será más rápido, ¿qué tan pequeño es este tamaño? 10 elementos, 10 millones?
garg10may
1
@ garg10may pequeño es menos de 10.
Jesse Wilson
@Porculus pequeño significa menos que la capacidad máxima de la matriz interna subyacente a la ArrayList.
Janac Meena
21

Sé que esta es una publicación antigua, pero sinceramente, no puedo creer que nadie haya mencionado que LinkedListimplemente Deque. Solo mire 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.

Ajax
fuente
18

Aquí está la notación Big-O en ambos 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)

En función de estos, debe decidir qué elegir. :)

Rajith Delantha
fuente
99
>>>> ArrayList add -> O (1) <- no tru. En algunos casos, ArrayList tendrá que crecer para agregar un elemento más
kachanov
1
LinkedList remove no es O (1), sería necesario para buscar el elemento a ser eliminado, por lo tanto peor caso O (n) y O media (n / 2)
garg10may
Tampoco lo es LinkedList.add(), aunque la mayoría de las respuestas aquí lo dicen.
Marqués de Lorne
18

Comparemos los parámetros debajo de LinkedList y ArrayList wrt a continuación:

1. Implementación

ArrayList es la implementación de matriz redimensionable de la interfaz de lista, mientras que

LinkedList es la implementación de lista doblemente vinculada de la interfaz de lista.


2. Rendimiento

  • get (int index) u operación de búsqueda

    La operación get (int index) de ArrayList 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 usa un sistema basado en índices para sus elementos, ya que internamente usa 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 (lo que esté más cerca) para recuperar el nodo en el índice del elemento especificado.

  • operación insert () o add (Object)

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

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

  • operación remove (int)

    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 Object o int pasado como parámetro. Este método atraviesa LinkedList hasta que encuentra el Object 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 anterior a la nueva matriz actualizada, por lo tanto, su tiempo de ejecución es O (n).


3. Iterador inverso

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

no hay descendingIterator () en ArrayList , por lo que debemos escribir nuestro propio código para iterar sobre 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).


Fuente

Abhijeet Ashok Muneshwar
fuente
18

Por lo general, uso uno sobre el otro según las complejidades de tiempo de las operaciones que realizaría en esa Lista en particular.

|---------------------|---------------------|--------------------|------------|
|      Operation      |     ArrayList       |     LinkedList     |   Winner   |
|---------------------|---------------------|--------------------|------------|
|     get(index)      |       O(1)          |         O(n)       | ArrayList  |
|                     |                     |  n/4 steps in avg  |            |
|---------------------|---------------------|--------------------|------------|
|      add(E)         |       O(1)          |         O(1)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     | O(n) in worst case  |                    |            |
|---------------------|---------------------|--------------------|------------|
|    add(index, E)    |       O(n)          |         O(n)       | LinkedList |
|                     |     n/2 steps       |      n/4 steps     |            |
|                     |---------------------|--------------------|            |
|                     |                     |  O(1) if index = 0 |            |
|---------------------|---------------------|--------------------|------------|
|  remove(index, E)   |       O(n)          |         O(n)       | LinkedList |
|                     |---------------------|--------------------|            |
|                     |     n/2 steps       |      n/4 steps     |            |
|---------------------|---------------------|--------------------|------------|
|  Iterator.remove()  |       O(n)          |         O(1)       | LinkedList |
|  ListIterator.add() |                     |                    |            |
|---------------------|---------------------|--------------------|------------|


|--------------------------------------|-----------------------------------|
|              ArrayList               |            LinkedList             |
|--------------------------------------|-----------------------------------|
|     Allows fast read access          |   Retrieving element takes O(n)   |
|--------------------------------------|-----------------------------------|
|   Adding an element require shifting | o(1) [but traversing takes time]  |
|       all the later elements         |                                   |
|--------------------------------------|-----------------------------------|
|   To add more elements than capacity |
|    new array need to be allocated    |
|--------------------------------------|
Gayan Weerakutti
fuente
ArrayDeque equilibra las cosas un poco más hacia las matrices, ya que insertar / eliminar delante / detrás son todas O (1), lo único que la Lista enlazada aún gana es agregar / eliminar mientras se atraviesa (las operaciones Iterator).
Bill K
14

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

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

PhiLho
fuente
10

Depende de qué operaciones realizará 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 hable sobre la diferencia entre las matrices y las listas vinculadas.

Matthew Schinckel
fuente
2
Para obtener más información, no lea, solo escriba el código. y descubrirá que la implementación de ArrayList es más rápida que LinkedList en inserción y eliminación.
kachanov
8

Una lista de matriz 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 al siguiente.

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

kemiller2002
fuente
7

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) (+ gastos generales de algunas reasignaciones) con una lista vinculada, esto es solo O (1) u O (2) ;-)

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

Karussell
fuente
2
¿Como es eso? Esto puede ser cierto con las estructuras de datos de la lista vinculada, pero no con un objeto Java LinkList. No puede simplemente apuntar un nextdesde una lista al primer nodo en la segunda lista. La única forma es usar el addAll()que agrega elementos secuencialmente, aunque es mejor que recorrer y llamar add()a cada elemento. Para hacer esto rápidamente en O (1) necesitaría una clase de composición (como org.apache.commons.collections.collection.CompositeCollection) pero luego esto funcionaría para cualquier tipo de Lista / Colección.
Kevin Brock
si verdad. Edité la respuesta en consecuencia. pero vea esta respuesta para 'cómo' hacerlo con LinkedList: stackoverflow.com/questions/2494031/…
Karussell el
7

ArrayList y LinkedList tienen sus propios pros y contras.

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 una ArrayList es más rápido que hacer n iteraciones con LinkedList.

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

Si tiene operaciones de recuperación frecuentes en su aplicación, use una ArrayList. Si tiene una inserción y eliminación frecuente, use LinkedList.

Nesan Mano
fuente
6

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

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

Mi justificación fue que, debido a que es imposible saber exactamente cuántos resultados estoy obteniendo, no habrá pérdida de memoria (como en ArrayList con la diferencia entre la capacidad y el número real de elementos), y no habría pérdida de tiempo tratando de 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 las matrices tanto como sea posible.

gaijinco
fuente
5

ArrayListy LinkedListambos implementos List interface y sus métodos y resultados son casi idénticos. Sin embargo, existen pocas diferencias entre ellos que hacen que uno sea mejor que otro según el 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 un sistema basado en índices para sus elementos, ya que utiliza la estructura de datos de matriz implícitamente, lo que lo hace más rápido para buscar un elemento en la lista. Por otro lado, LinkedListimplementa una lista doblemente vinculada que requiere el recorrido a través de todos los elementos para buscar un elemento.

2) la Deletion: LinkedListoperación de eliminación proporciona O(1)rendimiento mientras ArrayListproporciona 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 elemento 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 va a eliminar. Mientras que en ArrayList, todos los elementos deben desplazarse para completar el espacio creado por el elemento eliminado.

3) el Inserts Performance: LinkedListmétodo add proporciona O(1)rendimiento mientras ArrayListque O(n)en el peor de los casos. La razón es la misma que la explicada 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 algunas similitudes entre estas clases que son las siguientes:

  • Tanto ArrayList como LinkedList son implementaciones de la interfaz List.
  • 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á el mismo orden en que los elementos se insertaron en la Lista.
  • Ambas clases no están sincronizadas y pueden sincronizarse explícitamente mediante el método Collections.synchronizedList.
  • El iteratory listIteratordevuelto 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 manera, excepto a través de los iterator’spropios métodos remove o add, 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 proporcionan un buen rendimiento (O(1))en LinkedListcomparación con ArrayList(O(n)).

    Por lo tanto, si existe 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 quitar y más requisitos de operaciones de búsqueda, ArrayList sería su mejor opción.

Real73
fuente
5

La operación get (i) en ArrayList es más rápida que LinkedList, porque:
ArrayList: implementación de matriz redimensionable de la interfaz List
LinkedList: implementación de lista doblemente enlazada de las interfaces List y Deque

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

Amitābha
fuente
5

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 List, LinkedList también implementa la interfaz Deque, que proporciona las operaciones de primero en entrar, primero en salir para add () y poll () y varias otras funciones de Deque. 3) Agregar elementos en ArrayList Agregar elemento en ArrayList es una operación O (1) si no activa el redimensionamiento 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 navegación.

4) Eliminar un elemento de una posición

Para eliminar un elemento de un índice particular, por ejemplo, llamando a remove (index), ArrayList realiza una operación de copia que lo acerca a O (n), mientras que LinkedList necesita atravesar ese punto que también lo convierte en O (n / 2) , ya que puede atravesar desde cualquier dirección según 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 elemento de una posición

La operación get (index) es O (1) en ArrayList mientras que su O (n / 2) en LinkedList, ya que necesita recorrer hasta esa entrada. Sin embargo, en la notación Big O, O (n / 2) es solo O (n) porque ignoramos las constantes allí.

7) memoria

LinkedList utiliza un objeto contenedor, Entry, que es una clase anidada estática para almacenar datos y dos nodos, el siguiente y el anterior, mientras que ArrayList solo almacena datos en Array.

Por lo tanto, el requisito de memoria parece menor en el caso de ArrayList que 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 la matriz es lo suficientemente grande, puede tomar 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 vs 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 desde el inicio o el final porque la lista vinculada internamente mantiene referencias de esas posiciones y son accesibles en tiempo O (1).

En otras palabras, no es necesario recorrer la lista vinculada para llegar a la posición donde desea agregar elementos, en ese caso, la suma se convierte en la operación O (n). Por ejemplo, insertar o eliminar un elemento en el medio de una lista vinculada.

En mi opinión, use ArrayList sobre LinkedList para la mayoría del propósito práctico en Java.

Anjali Suman
fuente
1
Creo que esta es la mejor respuesta de todo el grupo aquí. Es preciso e informativo. Sugeriría cambiar la última línea: al final agregue "aparte de las colas", que son estructuras muy importantes que realmente no tienen sentido para una lista vinculada.
Bill K
3

Una de las pruebas que vi aquí solo realiza la prueba una vez. Pero lo que he notado es que necesita ejecutar estas pruebas muchas veces y eventualmente sus tiempos convergerán. Básicamente, la JVM necesita calentarse. Para mi caso de uso particular, necesitaba agregar / eliminar elementos a una lista que crezca a unos 500 elementos. En mis pruebas LinkedListsalió más rápido, con LinkedListalrededor de 50,000 NS y ArrayListllegando a alrededor de 90,000 NS ... más o menos. Ver 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;
}
Jose Martinez
fuente
2

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

En una ArrayList, llega al elemento en O (1), pero en realidad eliminar o insertar algo lo convierte en O (n) porque todos los siguientes elementos deben cambiarse.

En un LinkedList, se necesita O (n) para llegar realmente al elemento deseado, porque tenemos que comenzar desde el principio hasta llegar al índice deseado. En realidad, eliminar o insertar es constante, ya que solo tenemos que cambiar 1 referencia para eliminar () y 2 referencias para insertar ().

Cuál de los dos es más rápido para insertar y quitar depende de dónde ocurra. 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, una ArrayList será más rápida, porque llegaremos allí en tiempo constante y solo tendremos que cambiar los pocos elementos restantes que la siguen. Cuando se hace precisamente en el medio, LinkedList será más rápido porque pasar por 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 manera de hacerlo en LinkedLists. Digamos que queremos revisar la Lista completa eliminando e insertando elementos en nuestro camino. Por lo general, comenzaría desde el principio para cada elemento utilizando LinkedList, también podríamos "guardar" el elemento actual en el que estamos trabajando con un iterador. Con la ayuda de Iterator, obtenemos una eficiencia O (1) para remove () e insert () cuando trabajamos en LinkedList. Lo que lo convierte en el único beneficio de rendimiento. Sé que una LinkedList siempre es mejor que una ArrayList.

pietz
fuente
1

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

La clase LinkedList extiende AbstractSequentialList e implementa la interfaz List, Deque y Queue.
El rendimiento
arraylist.get()es O (1) mientras que linkedlist.get()es O (n)
arraylist.add()es O (1) y linkedlist.add()es 0 (1)
arraylist.contains()es O (n) y linkedlist.contains()es O (n)
arraylist.next()es O (1) y linkedlist.next()es 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)

Randhawa
fuente