Cuando el uso de LinkedList más de ArrayList en Java?

StackOverflow https://stackoverflow.com/questions/322715

Pregunta

Siempre he sido una persona simplemente usar:

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

Yo uso la interfaz como el nombre de tipo de la portabilidad, así que cuando me preguntas como estas puedo retrabajo de mi código.

Cuando debe LinkedList puede utilizarse a través de ArrayList y vice-versa?

¿Fue útil?

Solución

Resumen ArrayList con ArrayDeque son preferibles en muchos más casos de uso que LinkedList.Si no estás seguro — acaba de empezar con ArrayList.

LinkedList y ArrayList son dos implementaciones diferentes de la interfaz de Lista. LinkedList implementa con una lista doblemente vinculadas. ArrayList implementa con un dinámicamente cambiar el tamaño de la matriz.

Como con el estándar de una lista enlazada y operaciones de matriz, los diversos métodos tienen diferentes tiempos de ejecución de algoritmos.

Para LinkedList<E>

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

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

Para ArrayList<E>

  • get(int index) es O(1) <--- la principal ventaja de ArrayList<E>
  • add(E element) es O(1) se amortizan, sino que O(n) el peor de los caso, dado que la matriz debe ser cambiado de tamaño y copiado
  • 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 necesidad n/2 pasos en promedio, constante número de pasos en el mejor de los casos (al final de la lista), n pasos en el peor de los casos (inicio de la lista)

LinkedList<E> permite la constante de tiempo de inserciones o eliminaciones el uso de iteradores, pero sólo de acceso secuencial de los elementos.En otras palabras, puede recorrer la lista hacia delante o hacia atrás, pero encontrar una posición en la lista toma tiempo proporcional al tamaño de la lista.Javadoc dice "las operaciones de índice en la lista será el recorrido de la lista desde el principio o al final, lo que está más cerca", por lo que estos métodos son O(n) (n/4 pasos) en promedio, aunque O(1) para index = 0.

ArrayList<E>, por otro lado, permitir una rápida lectura aleatoria de acceso, por lo que se puede agarrar cualquier elemento en tiempo constante.Pero la adición o eliminación de cualquier lugar, pero el final requiere cambiar todos los últimos elementos más, ya sea para hacer una apertura o llenar el vacío.Además, si se agrega más elementos de los que la capacidad subyacente de la matriz, una nueva matriz (1,5 veces el tamaño) es asignado, y la antigua matriz se copian a la nueva, por lo que la adición de un ArrayList es O(n) en el peor de los casos, pero constante, en promedio.

Por lo que dependiendo de las operaciones que se pretende hacer, usted debe elegir las implementaciones en consecuencia.Iterando sobre cualquier tipo de Lista es prácticamente igual de barato.(Iterar sobre una ArrayList es técnicamente más rápido, pero a menos que usted está haciendo algo que realmente el rendimiento sensible, usted no debe preocuparse acerca de esto, son dos constantes.)

Los principales beneficios de la utilización de un LinkedList surgir cuando vuelva a utilizar los iteradores para insertar y eliminar elementos.Estas operaciones puede hacerse en O(1) por cambio de la lista solo de forma local.En una lista de matrices, el resto de la matriz debe ser movido (es decir,copiado).En el otro lado, buscando en un LinkedList significa seguir los enlaces en O(n) (n/2 pasos) para el peor de los casos, mientras que en un ArrayList la posición deseada puede ser calculada matemáticamente y se accede en O(1).

Otro de los beneficios de la utilización de un LinkedList surgir al agregar o quitar de la cabeza de la lista, ya que dichas operaciones se O(1), mientras están O(n) para ArrayList.Tenga en cuenta que ArrayDeque puede ser una buena alternativa para LinkedList para agregar y quitar de la cabeza, pero no es un List.

También, si usted tiene listas de gran tamaño, tenga en cuenta que el uso de memoria de también es diferente.Cada elemento de un LinkedList tiene más gastos ya que los punteros a la siguiente y anterior de los elementos son también almacenados. ArrayLists no tienen los gastos generales.Sin embargo, ArrayLists tomar la mayor cantidad de memoria asignada a la capacidad, independientemente de si los elementos han sido añadidos.

El valor predeterminado inicial de la capacidad de un ArrayList es bastante pequeño (10 de Java 1.4 - 1.8).Pero desde la implementación subyacente es una matriz, la matriz debe cambiar de tamaño si se agrega una gran cantidad de elementos.Para evitar el alto costo de cambio de tamaño cuando usted sabe que usted va a añadir un montón de elementos, la construcción de la ArrayList con una mayor capacidad inicial.

Otros consejos

Hasta ahora, nadie parece estar dirigida a la huella de la memoria de cada una de estas listas, además de que el consenso general de que una LinkedList es "mucho más" que un ArrayList así que hice algunos cálculos para demostrar exactamente cuánto ambas listas aprovechar para N referencias nulas.

Ya que las referencias son de 32 o de 64 bits (incluso cuando nulo) en su relativa de los sistemas, he incluido 4 conjuntos de datos de 32 y 64 bits LinkedLists y ArrayLists.

Nota: Los tamaños de muestra para la ArrayList las líneas para tapizados en las listas de - En la práctica, la capacidad de la copia de la matriz en un ArrayList generalmente es más grande que su actual recuento de elementos.

Nota 2: (gracias BeeOnRope) Como CompressedOops predeterminado es de ahora, desde mediados de JDK6 y de seguridad, los siguientes valores para máquinas de 64 bits será, básicamente, coinciden con sus equivalentes de 32 bits, a menos que específicamente lo apague.

Graph of LinkedList and ArrayList No. of Elements x Bytes

El resultado muestra claramente que LinkedList es mucho más que ArrayList, sobre todo con una muy alta recuento de elementos.Si la memoria es un factor, alejarse de LinkedLists.

Las fórmulas que he usado seguir, quiero saber si he hecho algo mal y lo voy a arreglar.'b' sea 4 o 8 de 32 o de 64 bits de los sistemas, y 'n' es el número de elementos.Nota: la razón de los mods es porque todos los objetos en java tomará un múltiplo de 8 bytes de espacio, independientemente de si es utilizado o no.

ArrayList:

ArrayList object header + size integer + modCount integer + array reference + (array oject header + b * n) + MOD(array oject, 8) + MOD(ArrayList object, 8) == 8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8) + MOD(8 + 4 + 4 + b + (12 + b * n) + MOD(12 + b * n, 8), 8)

LinkedList:

LinkedList object header + size integer + modCount integer + reference to header + reference to footer + (node object overhead + reference to previous element + reference to next element + reference to element) * n) + MOD(node object, 8) * n + MOD(LinkedList object, 8) == 8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n + MOD(8 + 4 + 4 + 2 * b + (8 + 3 * b) * n + MOD(8 + 3 * b, 8) * n, 8)

ArrayList es lo que quieres. LinkedList casi siempre es un error (de rendimiento).

Por qué <=> apesta:

  • 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 se usara <=>.
  • Obtener un buen rendimiento es complicado.
  • Incluso cuando el rendimiento big-O es el mismo que <=>, probablemente será significativamente más lento de todos modos.
  • Es discordante ver <=> en la fuente porque probablemente sea la elección incorrecta.

Como alguien que ha estado haciendo ingeniería de rendimiento operativo en servicios web SOA a gran escala durante aproximadamente una década, preferiría el comportamiento de LinkedList sobre ArrayList. Si bien el rendimiento en estado estable de LinkedList es peor y, por lo tanto, podría llevar a comprar más hardware, el comportamiento de ArrayList bajo presión podría llevar a que las aplicaciones en un clúster expandan sus matrices en casi sincronía 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 tenencia de 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 aplicaciones SOA y vuela 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. Según mi experiencia en mi trabajo, no puedo ignorar la peor latencia del caso. 

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-lectura-muchas o anexos, pero malas para agregar / quitar desde el frente o en el medio.

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 esto Implementación de 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)

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

Array vs ArrayList vs LinkedList vs Vector profundiza más, al igual que Lista vinculada .

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

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

Array, respaldado por <=>, 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);
    }
}

ArrayList es esencialmente una matriz. LinkedList se implementa como una doble lista enlazada.

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

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

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

=== ArrayList ===

  • añadir(E E)
    • añadir al final del ArrayList
    • requieren de la memoria de cambio de tamaño de costo.
    • O(n) en el peor, O(1) amortizado
  • add(int index, E elemento)
    • agregar a una determinada posición de índice
    • requieren de cambio y las posibles memoria de cambio de tamaño de costo
    • O(n)
  • remove(int index)
    • eliminar un elemento especificado
    • requieren de cambio y las posibles memoria de cambio de tamaño de costo
    • O(n)
  • remove(Object o)
    • quitar la primera ocurrencia del elemento especificado en esta lista
    • necesita buscar el primer elemento y, a continuación, cambiando & memoria de posible cambio de tamaño de costo
    • O(n)

=== LinkedList ===

  • añadir(E E)

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

  • add(int index, E elemento)

    • insertar en la posición especificada
    • necesita encontrar primero la posición
    • O(n)
  • remove()
    • quitar el primer elemento de la lista
    • O(1)
  • remove(int index)
    • quitar el elemento con el índice especificado
    • necesidad de encontrar el primer elemento
    • O(n)
  • remove(Object o)
    • quitar la primera ocurrencia del elemento especificado
    • necesidad de encontrar el primer elemento
    • O(n)

Aquí está una figura de programcreek.com (add y remove es el primer tipo, es decir, añadir un elemento al final de la lista y elimina el elemento en la posición especificada en la lista.):

enter image description here

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 se explica por sí misma.

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

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

Si el código tiene add(0) y remove(0), el uso de un LinkedList y es más bonita addFirst() y removeFirst() métodos.De lo contrario, utilice ArrayList.

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

Sé que este es un viejo post, pero honestamente, no puedo creer que nadie mencionó que LinkedList implementa Deque.Basta con mirar a los métodos de Deque (y Queue);si quieres una comparación justa, intente ejecutar LinkedList en contra de ArrayDeque y hacer una función para la función de comparación.

Aquí está el Big-O notación en ambos ArrayList y LinkedList y también CopyOnWrite-ArrayList:

ArrayList

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

LinkedList

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

CopyOnWrite-ArrayList

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

Basado en estos usted tiene que decidir qué elegir.:)

TL; DR debido a la arquitectura moderna de la computadora, ArrayList será significativamente más eficiente para casi cualquier caso de uso posible y, por lo tanto, se debe evitar LinkedList 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 Cache Hostile . Desde el punto de vista del rendimiento: hay muy pocos casos en los que Int podría tener un mejor rendimiento que el compatible con caché Vector.

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á & Quot; move & Quot; los n elementos posteriores de la matriz (los valores más bajos son mejores):

ingrese la descripción de la imagen aquí

Trabajar 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. fuente Código fuente

Hay dos razones principales para esto:

  1. Principalmente : que los nodos de <=> está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 el caché deben reemplazarse todo el tiempo - & Gt; La memoria caché falla - & Gt; La caché no es eficiente. <=> los elementos se almacenan en la memoria continua, que es exactamente para lo que está optimizando la arquitectura moderna de la CPU.

  2. Secundario <=> requerido para retener punteros hacia atrás / adelante, lo que significa 3 veces el consumo de memoria por valor almacenado en comparación con <=>.

DynamicIntArray , por cierto, es una implementación personalizada de ArrayList que contiene <=> (tipo primitivo) y no Objetos; por lo tanto, todos los datos se almacenan de forma adyacente, por lo tanto, aún más eficiente.

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, el <=> realmente debería brillar, y <=> deberí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, cambiando la teoría y haciendo, de nuevo, <=> / <=> mucho más eficiente

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

Comparemos LinkedList y ArrayList w.r.t. parámetros 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 la lista de enlaces dobles de la interfaz de la lista.

2. Rendimiento

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

      La operación

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

         

    LinkedList el tiempo de ejecución de la operación 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 (el 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 está en ArrayList , si la matriz está llena, es decir, en 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 O ( n), de lo contrario es O (1).

  • operación de eliminación (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, entonces ArrayList crea una lista vacía de capacidad inicial 10, mientras que

     

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

5. Sobrecarga de memoria

  

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

Además de los otros buenos argumentos anteriores, debe notar que ArrayList implementa la interfaz RandomAccess, mientras que LinkedList implementa Queue.

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

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.

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

ArrayList es más rápido para 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.

Usualmente uso uno sobre el otro en función de 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    |
|--------------------------------------|

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 su LinkedList ¡esto no es cierto! Consulte ¿Existe un método rápido de concat para la lista vinculada en Java?

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 tiempo desperdiciado 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 los arrays tanto como sea posible.

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.

ArrayList y LinkedList ambos implementos List interface y de sus métodos y los resultados son casi idénticos.Sin embargo, hay pocas diferencias entre ellos que hacen que uno más que otro, dependiendo del requerimiento.

ArrayList Vs LinkedList

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

Reason: ArrayList mantiene un índice basado en el sistema de sus elementos, ya que utiliza la matriz de estructura de datos implícitamente que hace que sea más rápido para buscar un elemento en la lista.En el otro lado LinkedList implementa lista doblemente vinculada que requiere el recorrido a través de todos los elementos para la búsqueda de un elemento.

2) Deletion: LinkedList operación de quitar da O(1) rendimiento, mientras que la ArrayList da un rendimiento variable: O(n) en el peor de los casos (mientras se quita el primer elemento) y O(1) en el mejor de los casos (Mientras retira el último elemento).

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

Razón:LinkedList de cada elemento mantiene dos punteros (direcciones) que señala al tanto de vecino elementos en la lista.Por lo tanto la eliminación de sólo requiere de un cambio en la ubicación del puntero en los dos vecino de nodos (elementos) del nodo que se va a quitar.Mientras que En el ArrayList todos los elementos que necesita ser cambiado para llenar el espacio creado por quitado elemento.

3) Inserts Performance: LinkedList método add da O(1) rendimiento, mientras que la ArrayList da O(n) en el peor de los casos.La razón es la misma que la explicada para quitar.

4) Memory Overhead: ArrayList mantiene los índices y datos del elemento, mientras que LinkedList mantiene el elemento de datos y dos punteros para los nodos vecinos

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

Hay algunas similitudes entre estas clases, que son como sigue:

  • Ambos ArrayList y LinkedList son la implementación de la interfaz de Lista.
  • Ambos se mantienen los elementos de la inserción de la orden que significa que mientras se muestra ArrayList y LinkedList elementos del conjunto de resultados sería tener el mismo orden en que los elementos se insertó en la Lista.
  • Estas dos clases no son sincronizados y puede ser sincronizado de forma explícita mediante el uso de las Colecciones.synchronizedList método.
  • El iterator y listIterator devueltos por estas clases de son fail-fast (si la lista está estructuralmente modificados en cualquier momento después de que el iterador se crea, en cualquier forma, excepto a través de la iterator’s propio quitar o agregar métodos, el iterador se throw un ConcurrentModificationException).

Cuando el uso de LinkedList y cuándo usar ArrayList?

  • Como se explicó anteriormente la inserción y extracción de las operaciones de dar un buen rendimiento (O(1)) en LinkedList en comparación con ArrayList(O(n)).

    Por lo tanto, si hay un requisito de la frecuente la adición y la eliminación en aplicación, a continuación, LinkedList es una mejor opción.

  • Búsqueda (get method las operaciones son rápidas en Arraylist (O(1)) pero no en LinkedList (O(n))

    así que Si hay menos de agregar y quitar operaciones y en las operaciones de búsqueda requisito, ArrayList sería su mejor apuesta.

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 indexan en la lista atravesarán la lista desde el principio o el final, lo que esté más cerca del índice especificado.

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 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, p. Al llamar 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 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) Recuperando elemento de una posición

La operación get (index) es O (1) en ArrayList mientras que 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 usa 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 de inicio o fin porque la lista vinculada internamente mantiene referencias de esas posiciones y son accesibles en tiempo O (1).

En otras palabras, no necesita desplazarse por 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.

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 una 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, 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 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 usando LinkedList, también podríamos & Quot; save & Quot; El elemento actual en el que estamos trabajando con un iterador. Con la ayuda del Iterator, obtenemos una eficiencia O (1) para remove () e insert () cuando trabajamos en LinkedList. Convirtiéndolo en el único beneficio de rendimiento, sé que una LinkedList siempre es mejor que una ArrayList.

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 extiende AbstractSequentialList e implementa la interfaz List, Deque y Queue.
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 la lista de arrays
iterator.remove() es O (n)
mientras que en la lista enlazada
<=> es O (1)

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, 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 unos 500 elementos. En mis pruebas, LinkedList salió más rápido, con ArrayList vinculados llegando a alrededor de 50,000 NS y <=> llegando a alrededor de 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;
}
Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top