Diferencia entre ArrayList y LinkedList en Java: c贸digo y rendimiento

    Introducci贸n

    Las listas son algunas de las estructuras de datos m谩s utilizadas. En Java, una pregunta com煤n al usar un List la implementaci贸n es:

    驴Qu茅 implementaci贸n utilizo?

    驴Deber铆a elegir un ArrayList o un LinkedList? 驴Cu谩l es la diferencia entre estos dos?

    En este art铆culo, revisaremos estas dos implementaciones, observaremos su funcionamiento interno y discutiremos su desempe帽o. Saber qu茅 implementaci贸n de un List usar en qu茅 situaci贸n es una habilidad esencial.

    Descripci贸n general de listas en Java

    Las listas son estructuras de datos que se utilizan para el almacenamiento secuencial de elementos. Esto significa que cada elemento de la lista tiene un predecesor y un sucesor (excepto el primero y el 煤ltimo, por supuesto, solo tienen uno de cada uno).

    Por tanto, las listas son colecciones ordenadas (a diferencia de los conjuntos) que tambi茅n permiten duplicados. Son convenientes porque permiten una f谩cil manipulaci贸n de elementos (como inserci贸n o recuperaci贸n) y una iteraci贸n simple de toda la colecci贸n.

    Lists a menudo van de la mano con otros mecanismos, como Java Streams, que ofrecen formas simples pero efectivas de iteraci贸n, filtrado, mapeo y otras operaciones 煤tiles.

    En Java, List es una interfaz bajo el java.util paquete. Dado que es una interfaz, simplemente proporciona una lista de m茅todos que deben anularse en la clase de implementaci贸n real.

    ArrayList y LinkedList son dos implementaciones diferentes de estos m茅todos. sin embargo, el LinkedList tambi茅n implementa el Queue interfaz.

    Funcionamiento interno de ArrayList y LinkedList

    Un ArrayList es una matriz de tama帽o variable que crece a medida que se agregan elementos adicionales. UN LinkedList es una implementaci贸n de lista / cola doblemente enlazada.

    Esto significa que ArrayList Contiene internamente una matriz de valores y una variable de contador para conocer el tama帽o actual en cualquier punto. Si se agrega un elemento, se aumenta el tama帽o. Si se elimina un elemento, se reduce el tama帽o.

    LinkedList no tiene una matriz, sino una cola de dos extremos de elementos conectados entre s铆. El primer elemento apunta al segundo, que apunta al tercero, y as铆 sucesivamente. Dado que esta es una lista doblemente enlazada, cada elemento tambi茅n apunta a su predecesor. El quinto elemento, por ejemplo, apunta tanto al cuarto como al sexto elemento.

    ArrayList contiene una 煤nica matriz para el almacenamiento de datos. LinkedList necesita una estructura de datos personalizada. Esta estructura de datos personalizada es una Node. Es una peque帽a clase interna que sirve como envoltorio para cada elemento.

    Para almacenar el elemento B, no es suficiente almacenar su valor como lo har铆a con un ArrayList.

    Tambi茅n se necesita un puntero al elemento anterior y al siguiente para que la lista vinculada sea transitable. Por tanto, toda la estructura de la lista consta de nodes conectados entre s铆. Cada node contiene su elemento y dos punteros: un enlace al node anterior y el enlace al siguiente node. El primer node no tiene un node anterior y el 煤ltimo node no tiene un node siguiente.

    Finalmente, en el caso de una lista enlazada, podemos asumir la existencia de dos punteros que monitorean continuamente el primer y 煤ltimo elemento de la lista. El primer puntero, head, apunta al primer elemento y se actualiza cada vez que se inserta un nuevo elemento al principio. El segundo puntero, tail, apunta al 煤ltimo elemento y tambi茅n se actualiza cada vez que se agrega un nuevo elemento al final.

    Comparaci贸n de implementaciones de ArrayList y LinkedList

    Obteniendo elementos con get ()

    ArrayList.get ()

    Si uno desea obtener un elemento de un ArrayList utilizando el get(int index) m茅todo, la implementaci贸n podr铆a simplemente delegar esta tarea a su matriz interna:

    public E get(int index) {
        rangeCheck(index);
    
        return elementData(index);
    }
    

    Por supuesto, se realiza una verificaci贸n adicional en el 铆ndice dado (asegur谩ndose de que no sea menor que cero o mayor que el tama帽o de la matriz).

    Podemos ver que esta operaci贸n se realiza en tiempo constante, o O (1). Esto significa que no importa el tama帽o de la matriz, cualquier elemento solicitado se devolver谩 instant谩neamente, sin necesidad de recorrer la lista. Esto se debe a que toda la matriz se almacena en un lugar 煤nico en la memoria.

    La ranura para el segundo elemento est谩 ubicada precisamente despu茅s del primero, y la ranura para el n-茅simo elemento est谩 ubicada precisamente antes del n + 1-茅simo. Bas谩ndose en esta estructura interna, cualquier elemento se puede recuperar f谩cilmente por 铆ndice.

    LinkedList.get ()

    Si uno desea obtener un elemento de un LinkedList, utilizando el get(int index) m茅todo – puedes, pero es realmente ineficiente.

    Anteriormente mencionamos que una lista vinculada no existe en un solo lugar en la memoria, sino que contiene diferentes nodes conectados entre s铆. Para obtener un elemento, es necesario recorrer la lista desde el principio (o el final, lo que est茅 m谩s cerca) y seguir las conexiones de cada uno de los nodes hasta encontrar el elemento deseado.

    La implementaci贸n del mismo m茅todo se ve as铆:

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
    
    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    
    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }
    
    Node<E> node(int index) {
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
    

    Primero, se realiza una verificaci贸n para asegurarse de que el 铆ndice no 0 o por encima del tama帽o del LinkedList. Entonces la node() El m茅todo atraviesa la lista hasta que encuentra el que estamos buscando.

    Esto se hace en tiempo O (N), comparado con ArrayListtiempo de O (1).

    Insertar elementos con add ()

    Esencialmente, cualquier tipo de inserci贸n se puede generalizar e implementar utilizando un m茅todo com煤n: insertar en un 铆ndice determinado.

    Si es necesario insertar un elemento al principio, se puede llamar al m茅todo con un 铆ndice de 0. Si es necesario insertar un elemento al final, el 铆ndice corresponder谩 al tama帽o actual de la lista. Si es necesario insertar un elemento en alg煤n lugar intermedio, el usuario debe proporcionar este 铆ndice.

    ArrayList.add ()

    Insertar un elemento al final es bastante simple, especialmente para una estructura como un ArrayList. Simplemente extienda la longitud en uno e inserte el elemento al final:

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }
    

    Sin embargo, insertar en una posici贸n determinada es un poco m谩s complicado. Debe dividir la matriz en el lugar que desea insertar: copie todo despu茅s de ese punto y mu茅valo hacia la derecha, agregando el nuevo elemento en el 铆ndice:

    public void add(int index, E element) {
        rangeCheckForAdd(index);
    
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = element;
        size++;
    }
    

    Cuanto m谩s grande sea la parte copiada, m谩s lenta ser谩 esta operaci贸n. Esto hace que la adici贸n de elementos a un ArrayList una operaci贸n relativamente ineficiente. Sin embargo, llegar al punto en el que debe realizarse la inserci贸n es realmente eficaz.

    LinkedList.add ()

    LinkedListLa implementaci贸n de nos permite agregar elementos en cualquier 铆ndice dado, con bastante facilidad. Solo apunta el head y tail punteros de los elementos anteriores y posteriores al nuevo, respectivamente. Si est谩 insertando al principio o al final de la lista, solo es necesario actualizar un puntero.

    Echemos un vistazo a la implementaci贸n:

    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
    

    Alternativamente, si especificamos un 铆ndice, ambos linkLast() y linkBefore() ser llamado:

    public void add(int index, E element) {
        checkPositionIndex(index);
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
    
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }
    

    No importa cu谩n grande sea la lista, solo es necesario cambiar dos punteros. Esto hace que la adici贸n de elementos a un LinkedList una operaci贸n altamente eficiente. Sin embargo, llegar a la posici贸n en la que se debe insertar el elemento es ineficaz.

    Encontrar elementos con indexOf ()

    Encontrar un elemento de una lista, ya sea un ArrayList o un LinkedList deber铆a ser bastante similar. Esto se debe a que no hay forma de saber a priori d贸nde se almacena un elemento en particular, a menos que la matriz est茅 ordenada y distribuida uniformemente.

    Una lista simplemente realiza un seguimiento de sus elementos y ofrece formas de manipularlos. Para saber exactamente d贸nde est谩 cada uno de estos elementos, ambas implementaciones deben pasar por alg煤n tipo de proceso iterativo hasta que se encuentra el elemento.

    ArrayList.indexOf ()

    En el ArrayList implementaci贸n, esto se hace con un simple for bucle que va desde 0 a size-1 y verificar si el elemento en el 铆ndice actual coincide con el valor dado:

    public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }
    

    Esta es literalmente una b煤squeda lineal, que no es muy eficiente, pero en realidad es la 煤nica forma de buscar un elemento en una colecci贸n barajada (si ignoramos los algoritmos metaheur铆sticos y las aproximaciones).

    LinkedList.indexOf ()

    LinkedList hace esto un poco diferente. En lugar de iterar a trav茅s de una matriz, tiene que recorrer la lista saltando de un elemento al siguiente con el uso de punteros. En 煤ltima instancia, el resultado es el mismo: visitando cada elemento, uno por uno, hasta encontrar el buscado:

    public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }
    

    Eliminar elementos con remove ()

    ArrayList.remove ()

    Muy similar a agregar elementos en un 铆ndice dado, eliminarlos requiere un ArrayList para copiar una parte de s铆 mismo y reinicializar la matriz sin un valor, desplazando la parte copiada hacia la izquierda:

    public E remove(int index) {
        rangeCheck(index);
    
        modCount++;
        E oldValue = elementData(index);
    
        int numMoved = size - index - 1;
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
            elementData[--size] = null; // clear to let GC do its work
    
        return oldValue;
    }
    

    Cuanto m谩s grande sea la parte copiada, m谩s lenta ser谩 esta operaci贸n. Nuevamente, esto hace que la eliminaci贸n de elementos de un ArrayList una operaci贸n ineficiente. Aunque, algo bueno sobre ArrayLists es que puedes llegar a ese elemento muy f谩cilmente. elementData(index) devuelve el elemento que desea eliminar en O (1) tiempo.

    LinkedList.remove ()

    Eliminar un elemento de un LinkedList funciona desvinculando los punteros anteriores y posteriores del elemento que nos gustar铆a eliminar. Despu茅s de eso, el elemento anterior est谩 vinculado al siguiente en la l铆nea. De esta forma, el elemento antiguo queda “varado” y sin referencias a 茅l, el GC se encarga de ello:

    public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
    

    Esto hace que la operaci贸n de eliminar elementos de un LinkedList eficiente, ya que de nuevo, solo es necesario cambiar algunos puntos. Sin embargo, cuanto m谩s larga sea la lista, m谩s tardar谩 en llegar al elemento que debe eliminarse, ya que no podemos acceder a los elementos a trav茅s de su 铆ndice.

    Comparaci贸n de rendimiento

    Hasta ahora, hemos discutido c贸mo ArrayList y LinkedList trabajar bajo el cap贸. Hemos analizado cada uno de ellos para comprender mejor sus similitudes y, lo que es m谩s importante, las diferencias.

    En esta secci贸n, compararemos brevemente las dos implementaciones desde la perspectiva del rendimiento:

    Cr茅ditos: Miro Medio

    Comparando get ()

    Podemos ver que la obtenci贸n de elementos de una lista es siempre O (1) para ArrayList.

    por LinkedList, buscar el primer o el 煤ltimo elemento es O (1) porque siempre tiene punteros a estos dos. No hay necesidad de l贸gica transversal adicional. Sin embargo, buscar cualquier otro elemento es O (N) porque no podemos acceder a ellos a trav茅s de un 铆ndice.

    Por lo tanto, en general, si recupera muchos elementos de la lista, una ArrayList se prefiere.

    Comparando insert ()

    por ArrayList, la inserci贸n es O (1) solo si se agrega al final. En todos los dem谩s casos (agregando al principio o en el medio), la complejidad es O (N), porque la parte derecha de la matriz debe copiarse y desplazarse.

    La complejidad de un LinkedList ser谩 O (1) tanto para la inserci贸n al principio como al final. Una vez m谩s, esto se debe a la head y tail punteros que se pueden utilizar para insertar un elemento en cualquiera de estas dos posiciones instant谩neamente.

    LinkedListLa complejidad de insertar en el medio es O (N), lo mismo que para ArrayList. La operaci贸n de inserci贸n es realmente eficiente, pero para llegar a ese punto hay que atravesar todos los elementos anteriores.

    Por lo general, la inserci贸n de elementos se realiza por igual entre ArrayList y un LinkedList, a menos que est茅 trabajando principalmente con el primer y 煤ltimo elemento.

    Comparando remove ()

    Las complejidades de la eliminaci贸n son pr谩cticamente las mismas que las de la inserci贸n. ArrayLists eliminar谩 elementos en O (1) si est谩n al final – O (N) en todos los dem谩s casos.

    LinkedLists tienen complejidad O (1) para eliminar desde el principio o el final, y O (N) en otros casos.

    Por lo tanto, la eliminaci贸n de elementos es generalmente la misma, a menos que trabaje principalmente con los elementos iniciales y 煤ltimos.

    Conclusi贸n

    ArrayList y LinkedList son dos implementaciones diferentes del List interfaz. Tienen sus diferencias que es importante comprender para utilizarlas correctamente.

    La implementaci贸n que se debe utilizar depende de los casos de uso exactos. Si los elementos se van a buscar con frecuencia, tiene poco sentido usar LinkedList ya que la recuperaci贸n es m谩s lenta en comparaci贸n con ArrayList. Por otro lado, si se necesitan inserciones de tiempo constante o si el tama帽o total se desconoce de antemano, entonces LinkedList se prefiere.

     

     

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *