Pregunta ¿Cuándo usar LinkedList sobre ArrayList?


Siempre he sido de los que simplemente uso:

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

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

Cuando debe LinkedList ser usado sobre ArrayList ¿y viceversa?


2565
2017-11-27 01:36


origen


Respuestas:


Resumen  ArrayList con ArrayDeque son preferibles en mucho más casos de uso que LinkedList. No estoy seguro - solo comience con ArrayList.


LinkedList y ArrayList son dos implementaciones diferentes de la interfaz de lista. LinkedList lo implementa con una lista doblemente vinculada. ArrayList lo implementa con una matriz de redimensionamiento dinámico.

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

por LinkedList<E>

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

Nota: muchas de las operaciones necesitan n / 4 pasos en promedio, 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)

por ArrayList<E>

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

Nota: muchas de las operaciones necesitan n / 2 pasos en promedio, constante número de pasos en el mejor de los casos (final de la lista), norte pasos en el peor de los casos (comienzo de la lista)

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

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

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

Los principales beneficios de usar un LinkedList surgen cuando reutiliza iteradores existentes para insertar y eliminar elementos. Estas operaciones se pueden hacer en O (1) cambiando la lista localmente solamente. En una lista de matriz, el resto de la matriz debe ser movido (es decir, copiado). Por otro lado, buscando en una LinkedList significa seguir los enlaces en En) (n / 2 pasos) para el peor de los casos, mientras que en un ArrayList la posición deseada puede calcularse matemáticamente y acceder a ella en O (1).

Otro beneficio de usar un LinkedList surgen cuando agrega o quita del encabezado de la lista, ya que esas operaciones son O (1)mientras ellos son En) para ArrayList. Tenga en cuenta que ArrayDeque puede ser una buena alternativa para LinkedList para agregar y quitar de la cabeza, pero no es List.

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

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


2845
2017-10-06 06:46



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

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

Nota: Los tamaños mostrados para el ArrayList las líneas son para listas recortadas - En la práctica, la capacidad del conjunto de respaldo en un ArrayList es generalmente más grande que su conteo actual de elementos.

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


Graph of LinkedList and ArrayList No. of Elements x Bytes


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

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

ArrayList:

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

LinkedList:

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

534
2017-11-27 14:20



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

Por qué LinkedList sucks:

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

190
2018-01-01 20:23



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

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

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


125
2018-04-08 20:33



Algorithm           ArrayList   LinkedList
seek front            O(1)         O(1)
seek back             O(1)         O(1)
seek to index         O(1)         O(N)
insert at front       O(N)         O(1)
insert at back        O(1)         O(1)
insert after an item  O(N)         O(1)

Algoritmos: notación Big-Oh

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


111
2018-05-19 11:21



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

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

Hay un caso de uso común en el que LinkedList supera a ArrayList: el de una cola. Sin embargo, si su 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 su cola antes de tiempo, y puede permitirse asignar toda la memoria por adelantado), o esto Implementación CircularArrayList. (Sí, es del 2001, por lo que deberá generarlo, pero obtuve índices de rendimiento comparables a lo que se cita en el artículo recientemente en una JVM reciente)


92
2017-11-27 01:39



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

Array vs ArrayList vs LinkedList vs Vectorva más en profundidad, al igual que Lista enlazada.


50
2017-09-21 22:59



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

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

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

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


Operation                       ArrayList                      LinkedList  

AddAll   (Insert)               101,16719                      2623,29291 

Add      (Insert-Sequentially)  152,46840                      966,62216

Add      (insert-randomly)      36527                          29193

remove   (Delete)               20,56,9095                     20,45,4904

contains (Search)               186,15,704                     189,64,981

Aquí está el código:

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

public class ArrayListVsLinkedList {
    private static final int MAX = 500000;
    String[] strings = maxArray();

    ////////////// ADD ALL ////////////////////////////////////////
    @Test
    public void arrayListAddAll() {
        Watch watch = new Watch();
        List<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);
    }
}

49
2018-04-21 00:03



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

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

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

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

=== Lista de arreglo ===

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

=== Lista enlazada ===

  • agregar (E e)

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

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

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

enter image description here


38
2017-11-27 01:41