ArrayList y LinkedList implementan la interfaz List y sus métodos y resultados son casi idénticos. Sin embargo, existen pocas diferencias entre ellos que hacen que uno sea mejor que el otro según el requisito.
ArrayList Vs LinkedList
1) InvestigarNota: La operación de búsqueda ArrayList es bastante rápida en comparación con la operación de búsqueda LinkedList. get(int index)
en ArrayList proporciona el rendimiento de O(1)
mientras que el rendimiento de LinkedList es O(n)
.
Motivo: ArrayList mantiene un sistema basado en índices para sus elementos, ya que utiliza implícitamente la estructura de datos de la matriz, lo que agiliza la búsqueda de un elemento en la lista. Por otro lado, LinkedList implementa lista doblemente enlazada que requiere atravesar todos los elementos para buscar un elemento.
2) Cancelación: La operación de eliminación de LinkedList da O(1)
rendimiento mientras que ArrayList proporciona rendimiento variable: O(n)
en el peor de los casos (eliminando el primer elemento) e O(1)
en el mejor de los casos (al quitar el último elemento).
Conclusión: eliminar el elemento LinkedList es más rápido que ArrayList.
Razón: Cada elemento LinkedList mantiene dos punteros (direcciones) que apuntan a ambos elementos vecinos en la lista. Entonces, la eliminación solo requiere cambiar la posición del puntero en los dos nodos vecinos (elementos) del nodo que se eliminará. Mientras esté en ArrayList, todos los elementos deben moverse para llenar el espacio creado por el elemento eliminado.
3) Rendimiento de las inserciones: El método de agregar LinkedList da O(1)
rendimiento mientras ArrayList ofrece O(n)
lo peor. El motivo es el mismo que se explicó para la eliminación.
4) Sobrecarga de memoria: ArrayList mantiene índices y datos de elementos mientras que LinkedList mantiene datos de elementos y dos punteros para nodos vecinos, por lo que el consumo de memoria es alto en LinkedList en comparación.
Hay unos pocos similitudes entre estas clases que son las siguientes:
- Tanto ArrayList como LinkedList son implementaciones de la interfaz List.
- Ambos mantienen el orden en el que se insertaron los elementos, lo que significa que al visualizar los elementos ArrayList y LinkedList el conjunto de resultados tendría el mismo orden en el que se insertaron los elementos en la lista.
- Ambas clases no están sincronizadas y se pueden sincronizar explícitamente usando explícitamente
Collections.synchronizedList
método. - El iterador y la lista de iteradores devueltos por estas clases son rápidos (si la lista se modifica estructuralmente en cualquier momento después de que se crea el iterador, de cualquier manera, excepto a través de los métodos de eliminar o agregar iterador, el iterador arrojará un ConcurrentModificationException).
¿Cuándo usar LinkedList y cuándo usar ArrayList?
1) Como se explicó anteriormente, las operaciones de inserción y extracción dan un buen rendimiento (O(1)
) en LinkedList versus ArrayList (O(n)
). Por lo tanto, si necesita agregar y eliminar frecuentes en su aplicación, LinkedList es su mejor opción.
2) Las operaciones de búsqueda (método de obtención) son rápidas en Arraylist (O(1)
) pero no en LinkedList (O(n)
) por lo que si hay menos operaciones de agregar y quitar y se requieren más operaciones de búsqueda, ArrayList sería su mejor opción.