java - diferencia - ArrayList Vs LinkedList

linkedlist vs list

Question

Estaba siguiendo una publicación anterior sobre esto que dice:

Para LinkedList

• obtener es O (n)
• agregar es O (1)
• quitar es O (n)
• Iterator.remove es O (1)

Para ArrayList

• obtener es O (1)
• add es O (1) amortizado, pero O (n) el peor de los casos, ya que la matriz debe redimensionarse y copiarse
• quitar es O (n)

Así que al ver esto, llegué a la conclusión de que si tengo que hacer una inserción secuencial en mi colección para, por ejemplo, 5000000 elementos, LinkedList superará a ArrayList .

Y si solo tengo que buscar los elementos de la colección al iterar, es decir, no agarrar el elemento en el medio, aún LinkedList sobrepasará a `ArrayList.

Ahora, para verificar mis dos declaraciones anteriores, escribí debajo del programa de muestra ... Pero me sorprende que mis declaraciones anteriores hayan demostrado ser erróneas.

ArrayList superó a Linkedlist en ambos casos. Tomó menos tiempo que LinkedList para agregarlo y recuperarlo de Collection. ¿Hay algo que estoy haciendo mal, o las declaraciones iniciales sobre LinkedList y ArrayList no son ciertas para las colecciones de tamaño 5000000?

Mencioné el tamaño, porque si reduzco la cantidad de elementos a 50000, LinkedList funciona mejor y las declaraciones iniciales son verdaderas.

long nano1 = System.nanoTime();

List<Integer> arr = new ArrayList();
for(int i = 0; i < 5000000; ++i) {
    arr.add(i);
}
System.out.println( (System.nanoTime() - nano1) );

for(int j : arr) {
    ;
}
System.out.println( (System.nanoTime() - nano1) );

long nano2 = System.nanoTime();

List<Integer> arrL = new LinkedList();
for(int i = 0; i < 5000000; ++i) {
    arrL.add(i);
}
System.out.println( (System.nanoTime() - nano2) );

for(int j : arrL) {
    ;
}
System.out.println( (System.nanoTime() - nano2) );

Answer 1

Comprender por qué los resultados que obtuvo no contradicen la caracterización de "O grande". Necesitamos volver a los primeros principios; es decir, la definición .

Deje f (x) yg (x) ser dos funciones definidas en algún subconjunto de los números reales. Uno escribe

f(x) = O(g(x)) as x -> infinity

si y solo si, para valores lo suficientemente grandes de x, f (x) es como máximo una constante multiplicada por g (x) en valor absoluto. Es decir, f (x) = O (g (x)) si y solo si existe un número real positivo M y un número real x0 tal que

|f(x)| <= M |g(x)| for all x > x_0.

En muchos contextos, la suposición de que estamos interesados ​​en la tasa de crecimiento como la variable x va al infinito no se expresa, y uno escribe más simplemente que f (x) = O (g (x)).

Entonces, el enunciado add1 is O(1) , significa que el costo de tiempo de una operación add1 en una lista de tamaño N tiende hacia una constante C _add1 ya que N tiende a infinito.

Y el enunciado add2 is O(1) amortized over N operations , lo que significa que el costo promedio de tiempo de una de una secuencia de operaciones N add2 tiende hacia una constante C _add2 ya que N tiende a infinito.

Lo que no dice es qué son esas constantes C _add1 y C _add2 . De hecho, la razón por la que LinkedList es más lenta que ArrayList en su punto de referencia es que C _add1 es más grande que C _add2 .

La lección es que la notación O grande no predice un rendimiento absoluto o incluso relativo. Todo lo que predice es la forma de la función de rendimiento a medida que la variable de control se hace muy grande. Esto es útil para saber, pero no te dice todo lo que necesitas saber.

Answer 2

El análisis de notación O proporciona información importante, pero tiene sus limitaciones. Por definición, el análisis de notación O considera que cada operación lleva aproximadamente el mismo tiempo para ejecutarse, lo que no es cierto. Como señaló @seand, las listas enlazadas internamente usan lógica más compleja para insertar y buscar elementos (eche un vistazo al código fuente, puede presionar + clic en su IDE). ArrayList internamente solo necesita insertar elementos en una matriz y aumentar su tamaño de vez en cuando (que incluso siendo una operación o (n), en la práctica se puede lograr bastante rápido).

Aclamaciones

Answer 3

Es difícil encontrar un buen caso de uso para LinkedList. Si solo necesita hacer uso de la interfaz Dequeu, probablemente debería usar ArrayDeque. Si realmente necesita utilizar la interfaz de la Lista, a menudo escuchará la sugerencia de usar siempre ArrayList porque LinkedList se comporta muy mal al acceder a un elemento aleatorio.

Desafortunadamente, también ArrayList tiene problemas de rendimiento si los elementos al principio o en el medio de la lista deben eliminarse o insertarse.

Sin embargo, hay una nueva implementación de lista llamada GapList que combina las fortalezas de ArrayList y LinkedList. Ha sido diseñado como un reemplazo directo tanto para ArrayList como para LinkedList y, por lo tanto, implementa las interfaces List y Deque. También se implementan todos los métodos públicos proporcionados por ArrayList (ensureCapacty, trimToSize).

La implementación de GapList garantiza un acceso aleatorio eficiente a los elementos por índice (como lo hace ArrayList) y, al mismo tiempo, agrega y elimina elementos de manera eficiente a la cabeza y la cola de la lista (como lo hace LinkedList).

Puede encontrar más información sobre GapList en http://java.dzone.com/articles/gaplist-%E2%80%93-lightning-fast-list .

Answer 4

Esta es una mala IMO de referencia.

• necesidad de repetir en el bucle varias veces para calentar jvm
• necesita HACER algo en su bucle iterativo o puede ser una matriz optimizada
• ArrayList cambia el tamaño, lo cual es costoso. Si hubiera construido ArrayList como new ArrayList(500000) lo construiría de una sola vez, y todas las asignaciones serían bastante baratas (una matriz respaldada prealcaldeada)
• No especifica su JVM de memoria: debe ejecutarse con -xMs == -Xmx (todo preasignado) y lo suficientemente alto como para que no se active el GC.
• Este punto de referencia no cubre el aspecto más desagradable de LinkedList: acceso aleatorio. (un iterador no es necesariamente la misma cosa). Si alimenta dice el 10% del tamaño de una gran colección como una selección aleatoria de list.get , encontrará que las listas de enlaces son terribles para capturar algo que no sea el primero o el último elemento.

Para un arraylist: el jdk get es lo que esperas:

public E get(int index) {
    RangeCheck(index);

    return elementData[index];
}

(básicamente solo devuelve el elemento de matriz indexado.,

Para una lista de enlaces:

public E get(int index) {
    return entry(index).element;
}

¿Se ve similar? No exactamente. la entrada es un método, no una matriz primitiva, y mira lo que tiene que hacer:

private Entry<E> entry(int index) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+
                                            ", Size: "+size);
    Entry<E> e = header;
    if (index < (size >> 1)) {
        for (int i = 0; i <= index; i++)
            e = e.next;
    } else {
        for (int i = size; i > index; i--)
            e = e.previous;
    }
    return e;
}

Así es, si pides decir, por ejemplo, list.get(250000) , debe comenzar en la parte list.get(250000) e iterar repetidamente a través del siguiente elemento. 250000 accesos más o menos (hay una optimización en el código donde comienza al principio o al final dependiendo de cuáles serían menos accesos).

Answer 5

La gran notación O no se trata de sincronizaciones absolutas, sino de tiempos relativos, y no se pueden comparar los números de un algoritmo con otro.

Solo obtiene información de cómo el mismo algoritmo reacciona al aumento o disminución del número de tuplas.

Un algoritmo puede tomar una hora para una operación, y 2 horas para dos operaciones, y es O (n), y otra es O (n) también, y toma un milisegundo para una operación y dos milisegundos para dos operaciones.

Otro problema si se mide con JVM es la optimización del compilador de hotspot. El compilador JIT podría eliminar un bucle de no hacer nada.

Una tercera cosa a considerar es el SO y JVM, usando cachés y ejecutando la recolección de basura mientras tanto.

Answer 6

Puede separar agregar o eliminar como una operación de dos pasos.

LinkedList : si agrega un elemento al índice n, puede mover el puntero de 0 a n-1, luego puede realizar su llamada operación O (1) add. La operación de eliminación es la misma.

ArraryList : ArrayList implementa la interfaz RandomAccess, lo que significa que puede acceder a un elemento en O (1).
Si agrega un elemento en el índice n, puede ir al índice n-1 en O (1), mover los elementos después de n-1, agregar establecer el elemento en el n slot.
La operación de movimiento se realiza mediante un método nativo llamado System.arraycopy , es bastante rápido.

public static void main(String[] args) {

    List<Integer> arrayList = new ArrayList<Integer>();
    for (int i = 0; i < 100000; i++) {
        arrayList.add(i);
    }

    List<Integer> linkList = new LinkedList<Integer>();

    long start = 0;
    long end = 0;
    Random random = new Random();

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        linkList.add(random.nextInt(100000), 7);
    }
    end = System.currentTimeMillis();
    System.out.println("LinkedList add ,random index" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        arrayList.add(random.nextInt(100000), 7);
    }
    end = System.currentTimeMillis();
    System.out.println("ArrayList add ,random index" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        linkList.add(0, 7);
    }
    end = System.currentTimeMillis();
    System.out.println("LinkedList add ,index == 0" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        arrayList.add(0, 7);
    }
    end = System.currentTimeMillis();
    System.out.println("ArrayList add ,index == 0" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        linkList.add(i);
    }
    end = System.currentTimeMillis();
    System.out.println("LinkedList add ,index == size-1" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        arrayList.add(i);
    }
    end = System.currentTimeMillis();
    System.out.println("ArrayList add ,index == size-1" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        linkList.remove(Integer.valueOf(random.nextInt(100000)));
    }
    end = System.currentTimeMillis();
    System.out.println("LinkedList remove ,random index" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        arrayList.remove(Integer.valueOf(random.nextInt(100000)));
    }
    end = System.currentTimeMillis();
    System.out.println("ArrayList remove ,random index" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        linkList.remove(0);
    }
    end = System.currentTimeMillis();
    System.out.println("LinkedList remove ,index == 0" + (end - start));

    start = System.currentTimeMillis();
    for (int i = 0; i < 10000; i++) {
        arrayList.remove(0);
    }
    end = System.currentTimeMillis();
    System.out.println("ArrayList remove ,index == 0" + (end - start));

}

Answer 7

Recuerde que la complejidad de la gran O describe el comportamiento asintótico y puede no reflejar la velocidad de implementación real. Describe cómo crece el costo de cada operación con el tamaño de la lista, no la velocidad de cada operación. Por ejemplo, la siguiente implementación de add es O (1) pero no es rápida:

public class MyList extends LinkedList {
    public void add(Object o) {
        Thread.sleep(10000);
        super.add(o);
    }
}

Sospecho que en su caso, ArrayList está funcionando bien porque aumenta su tamaño interno de memoria intermedia bastante agresivamente, por lo que no habrá una gran cantidad de reasignaciones. Cuando no es necesario cambiar el tamaño del búfer, ArrayList tendrá add s más rápidos.

También debe tener mucho cuidado cuando realice este tipo de perfiles. Te sugiero que cambies tu código de perfil para hacer una fase de calentamiento (para que el JIT tenga la oportunidad de hacer algo de optimización sin afectar tus resultados) y promediar los resultados en varias ejecuciones.

private final static int WARMUP = 1000;
private final static int TEST = 1000;
private final static int SIZE = 500000;

public void perfTest() {
    // Warmup
    for (int i = 0; i < WARMUP; ++i) {
        buildArrayList();
    }
    // Test
    long sum = 0;
    for (int i = 0; i < TEST; ++i) {
        sum += buildArrayList();
    }
    System.out.println("Average time to build array list: " + (sum / TEST));
}

public long buildArrayList() {
    long start = System.nanoTime();
    ArrayList a = new ArrayList();
    for (int i = 0; i < SIZE; ++i) {
        a.add(i);
    }
    long end = System.nanoTime();
    return end - start;
}

... same for buildLinkedList

(Tenga en cuenta que la sum puede desbordarse y que sería mejor utilizar System.currentTimeMillis() ).

También es posible que el compilador esté optimizando sus bucles de get vacíos. Asegúrese de que el bucle realmente hace algo para asegurarse de que se está llamando al código correcto.

Answer 8

Una ArrayList es una estructura de datos más simple que LinkedList. Un ArrayList tiene una única matriz de punteros en ubicaciones de memoria contigua. Solo tiene que recrearse si la matriz se expande más allá de su tamaño asignado.

Una LinkedList consiste en una cadena de nodos; cada nodo está separado asignado y tiene punteros frontal y posterior a otros nodos.

Entonces, ¿qué significa esto? A menos que necesite insertar en el medio, empalmar, eliminar en el medio, etc. una ArrayList generalmente será más rápida. Necesita menos asignaciones de memoria, tiene una localidad de referencia mucho mejor (lo cual es importante para el almacenamiento en caché del procesador), etc.

Answer 9

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 mayores diferencias en el rendimiento.

2) LinkedList implementa Deque Otra diferencia entre ArrayList y LinkedList es que, aparte de la interfaz de lista, LinkedList también implementa la interfaz Deque, que proporciona las operaciones first in first out para add () y poll () y varias otras funciones de Deque. 3) Agregar elementos en ArrayList Agregar elemento en ArrayList es O (1) operación si no desencadena el cambio de tamaño de la matriz, en cuyo caso se convierte en O (log (n)), por otro lado se agrega un elemento en LinkedList es O (1) operación, ya que no requiere ninguna navegación.

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

5) Iteraciones sobre ArrayList o LinkedList Iteration es la operación O (n) para LinkedList y ArrayList donde n es una cantidad 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 de Big O, O (n / 2) es solo O (n) porque ignoramos las constantes allí.

7) Memory LinkedList utiliza un objeto envoltorio, Entry, que es una clase anidada estática para almacenar datos y dos nodos al mismo tiempo y anteriores, mientras que ArrayList solo almacena datos en Array.

Así que el requisito de memoria parece menos 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 una matriz a otra.

Si Array es lo suficientemente grande, puede llevar 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 se realiza una operación add () frecuente que eliminar () 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 están accesibles en O (1) hora.

En otras palabras, no es necesario que recorra la lista vinculada para llegar a la posición donde desea agregar elementos, en ese caso, la adición se convierte en 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 parte del propósito práctico en Java.