ArrayList y LinkedList implementan la interfaz de la Lista y sus métodos y resultados son casi idénticos. Sin embargo, hay pocas diferencias entre ellos que los hacen mejores que los otros dependiendo del requerimiento.
1) Búsqueda: La operación de búsqueda de ArrayList es bastante rápida comparada con la operación de búsqueda de LinkedList. get(int index) en ArrayList da el rendimiento de O(1) mientras que el rendimiento de LinkedList es O(n).
Razón: ArrayList mantiene un sistema basado en índices para sus elementos, ya que utiliza la estructura de datos de la matriz de forma implícita, lo que la hace más rápida para la búsqueda de un elemento en la lista. Por otro lado LinkedList implementa una lista doblemente enlazada que requiere el recorrido por todos los elementos para buscar un elemento.
2) Eliminación: La operación de eliminación de LinkedList proporciona un rendimiento O(1) mientras que ArrayList proporciona un rendimiento variable: O(n) en el peor de los casos (mientras se elimina el primer elemento) y O(1) en el mejor de los casos (mientras se elimina el último elemento).
Conclusión: La eliminación del elemento LinkedList es más rápida en comparación con ArrayList.
Razón: Cada elemento de LinkedList mantiene dos punteros (direcciones) que apuntan a los dos elementos vecinos de la lista. Por lo tanto, la eliminación sólo requiere un cambio en la ubicación del puntero en los dos nodos (elementos) vecinos del nodo que va a ser eliminado. Mientras que en ArrayList todos los elementos necesitan ser desplazados para llenar el espacio creado por el elemento eliminado.
3) Inserta el rendimiento: El método de adición de LinkedList da un rendimiento de O(1) mientras que ArrayList da O(n) en el peor de los casos. La razón es la misma que la explicada para eliminar.
4) Recargo de memoria: ArrayList mantiene los índices y los datos de los elementos mientras que LinkedList mantiene los datos de los elementos y dos punteros para los nodos vecinos, por lo que el consumo de memoria es alto en LinkedList comparativamente.
Hay pocas similitudes entre estas clases que son las siguientes:
- Tanto ArrayList como LinkedList son una implementación de la interfaz de List.
- Ambos mantienen el orden de inserción de los elementos, lo que significa que mientras se muestran los elementos de ArrayList y LinkedList el conjunto de resultados tendría el mismo orden en el que los elementos se insertaron en la Lista.
- Ambas clases no están sincronizadas y pueden sincronizarse explícitamente mediante el método Collections.synchronizedList.
- El iterador y el listIterator devueltos por estas clases son rápidos (si la lista se modifica estructuralmente en cualquier momento después de que se cree el iterador, de cualquier manera excepto a través de los métodos de quitar o añadir del propio iterador, el iterador lanzará una excepción de modificación concurrente).
¿Cuándo usar LinkedList y cuándo usar ArrayList?
1) Como se ha explicado anteriormente, las operaciones de inserción y extracción dan un buen rendimiento (O(1)) en LinkedList en comparación con ArrayList(O(n)). Por lo tanto, si hay un requisito de adición y eliminación frecuente en la aplicación, entonces LinkedList es la 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 adición y eliminación y se requieren más operaciones de búsqueda, ArrayList sería su mejor opción.
