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

En este artículo, profundizaremos en cuál es la diferencia entre una ArrayList y una LinkedList en Java. Compararemos su código y rendimiento para resaltar la distinción.

Introducción

Las listas son algunas de las estructuras de datos más utilizadas. En Java, una pregunta común cuando se usa una implementación List es:

¿Qué implementación utilizo?

¿Debe elegir una ArrayList o una LinkedList? ¿Cuál es la diferencia entre estos dos?

En este artículo, repasaremos ambas implementaciones, observaremos su funcionamiento interno y analizaremos su rendimiento. Saber qué implementación de una ‘Lista’ usar en qué situación es una habilidad esencial.

Descripción general de las listas en Java

Las listas son estructuras de datos utilizadas para el almacenamiento de elementos secuenciales. 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 lo 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.

Las ’listas’ a menudo van de la mano con otros mecanismos, como Java Streams, que ofrecen formas simples pero efectivas para la iteración, el filtrado, el mapeo y otras operaciones útiles.

En Java, List es una interfaz bajo el paquete java.util. 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, LinkedList también implementa la interfaz Queue.

Funcionamiento interno de ArrayList y LinkedList

Una ArrayList es una matriz redimensionable que crece a medida que se agregan elementos adicionales. Una 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 añade 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 doble de elementos conectados entre sí. El primer elemento apunta a el segundo, el cual 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 elemento 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 un Nodo. Es una pequeña clase interna que sirve como envoltorio alrededor de 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 enlazada sea transitable. La estructura completa de la lista consiste, por lo tanto, en nodos conectados entre sí. Cada nodo contiene su elemento y dos punteros: un enlace al nodo anterior y el enlace al siguiente nodo. El primer nodo no tiene un nodo anterior y el último nodo no tiene un nodo siguiente.

Finalmente, en el caso de una lista enlazada, podemos suponer la existencia de dos punteros que monitorean continuamente el primero y el ú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 {#comparación de implementaciones de lista de conjuntos y lista enlazada}

Obtención de elementos con get() {#obtención de elementos con obtención}

ArrayList.get()

Si uno desea obtener un elemento de un ArrayList usando el método get(int index), la implementación podría simplemente delegar esta tarea a su matriz interna:

1
2
3
4
5
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 ni 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 se ubica precisamente después del primero, y la ranura para el n-ésimo elemento se ubica precisamente antes del n+1-ésimo. Basándose en esta estructura interna, cualquier elemento se puede recuperar fácilmente por índice.

ListaEnlazada.get()

Si uno desea obtener un elemento de una LinkedList, utilizando el método get(int index), puede hacerlo, pero es realmente ineficiente.

Anteriormente mencionamos cómo una lista enlazada no existe en un solo lugar en la memoria sino que contiene diferentes nodos conectados entre sí. Para obtener un elemento, la lista debe recorrerse desde el principio (o el final, lo que esté más cerca) y seguir cada una de las conexiones de los nodos hasta que se encuentre el elemento deseado.

La implementación del mismo método se ve así:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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 sea 0 o superior al tamaño de LinkedList. Luego, el método node() recorre la lista hasta que encuentra el que estamos buscando.

Esto se hace en tiempo O(N), en comparación con el tiempo O(1) de ArrayList.

Inserción de elementos con add()

Esencialmente, cualquier tipo de inserción puede generalizarse e implementarse utilizando un método común: insertar en un índice dado.

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 en el medio, el usuario debe proporcionar este índice.

ArrayList.add()

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

1
2
3
4
5
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:

1
2
3
4
5
6
7
8
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 es la parte copiada, más lenta es esta operación. Esto hace que la adición de elementos a una ArrayList sea una operación relativamente ineficiente. Sin embargo, llegar al punto donde se debe realizar la inserción es realmente eficiente.

LinkedList.add()

La implementación de LinkedList\ nos permite agregar elementos en cualquier índice dado, con bastante facilidad. Simplemente apunte los punteros head y tail de los elementos anterior y anterior al nuevo, respectivamente. Si está insertando al principio o al final de la lista, solo se necesita actualizar un puntero.

inserting node in the middle of a linked list

Echemos un vistazo a la implementación:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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, tanto linkLast() como linkBefore() son llamados:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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 una LinkedList sea una operación altamente eficiente. Sin embargo, alcanzar la posición en la que se debe insertar el elemento es ineficiente.

Búsqueda de elementos con indexOf()

Encontrar un elemento de una lista, ya sea una ArrayList o una 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 encontrar el elemento.

ArrayList.indexOf()

En la implementación de ArrayList, esto se hace con un simple bucle for que va de 0 a size-1 y verifica si el elemento en el índice actual coincide con el valor dado:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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 aleatoria (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: visitar cada elemento, uno por uno, hasta encontrar el que se busca:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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 una ArrayList para copiar una parte de sí misma y reinicializar la matriz sin un valor, desplazando la parte copiada hacia la izquierda:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
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 es la parte copiada, más lenta es esta operación. Nuevamente, esto hace que la eliminación de elementos de una ArrayList sea una operación ineficiente. Sin embargo, lo bueno de 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 una LinkedList funciona al desvincular los punteros anteriores y posteriores del elemento que nos gustaría eliminar. Después de eso, el elemento anterior se vincula con el siguiente en la línea. De esta forma, el elemento anterior queda "varado" y sin referencias a él, el GC se encarga de ello:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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 una LinkedList sea 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 {#comparación de rendimiento}

Hasta ahora, hemos discutido cómo ArrayList y LinkedList funcionan bajo el capó. Hemos diseccionado cada uno de ellos para comprender mejor sus similitudes y, lo que es más importante, sus diferencias.

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

texto alternativo

[Créditos: Miró Medio]{.small}

Comparando get()

Podemos ver que obtener elementos de una lista siempre es O(1) para ArrayList.

Para LinkedList, obtener el primer o el último elemento es O(1) porque siempre apunta a estos dos. No hay necesidad de lógica transversal adicional. Sin embargo, buscar cualquier otro elemento es O(N) porque no podemos simplemente acceder a ellos a través de un índice.

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

Comparando insertar()

Para 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 de la derecha de la matriz se debe copiar y desplazar.

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

La complejidad de LinkedList para insertar en el medio es O(N), la misma que para ArrayList. La operación de inserción es realmente eficiente, pero para llegar a ese punto, tiene que atravesar todos los elementos anteriores.

En general, la inserción de elementos se realiza de la misma manera entre una ArrayList y una LinkedList, a menos que esté trabajando principalmente con el primer y el último elemento.

Comparando remove()

Las complejidades de la extracción son prácticamente las mismas que las complejidades de la inserción. ArrayLists eliminará elementos en O(1) si están al final - O(N) en todos los demás casos.

LinkedLists tiene 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 suele ser la misma, a menos que trabaje principalmente con los elementos inicial y final.

Conclusión

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

La implementación que se debe usar depende de los casos de uso exactos. Si los elementos se van a recuperar con frecuencia, no tiene mucho sentido usar LinkedList ya que la obtención es más lenta en comparación con ArrayList. Por otro lado, si se necesitan inserciones de tiempo constante o si se desconoce el tamaño total de antemano, se prefiere LinkedList.

C `.

C

Licensed under CC BY-NC-SA 4.0