1. Información general
Cuando se trata de colecciones, la biblioteca estándar de Java ofrece muchas opciones para elegir. Entre esas opciones son dos famosos Lista implementaciones conocidas como ArrayList y LinkedList, cada uno con sus propias propiedades y casos de uso.
En este tutorial, veremos cómo se implementan realmente estos dos. Luego, evaluaremos diferentes aplicaciones para cada una.
2. ArrayList
Internamente, ArrayList está usando una matriz para implementar la interfaz List . Como las matrices tienen un tamaño fijo en Java, ArrayList crea una matriz con cierta capacidad inicial. En el camino, si necesitamos almacenar más elementos que la capacidad predeterminada, reemplazará esa matriz por una nueva y más espaciosa.
Para comprender mejor sus propiedades, evaluemos esta estructura de datos con respecto a sus tres operaciones principales: agregar elementos, obtener uno por índice y eliminar por índice.
2.1. Añadir
Cuando creamos una ArrayList vacía , inicializa su matriz de respaldo con una capacidad predeterminada (actualmente 10):
Agregar un nuevo elemento mientras la matriz aún no está llena es tan simple como asignar ese elemento a un índice de matriz específico. Este índice de matriz está determinado por el tamaño de la matriz actual, ya que prácticamente estamos agregando a la lista:
backingArray[size] = newItem; size++;Entonces, en los mejores casos y en los casos promedio, la complejidad de tiempo para la operación de adición es O (1) , que es bastante rápida. Sin embargo, a medida que la matriz de respaldo se llena, la implementación de adición se vuelve menos eficiente:
Para agregar un nuevo elemento, primero debemos inicializar una nueva matriz con más capacidad y copiar todos los elementos existentes en la nueva matriz. Solo después de copiar los elementos actuales podemos agregar el nuevo elemento. Por tanto, la complejidad del tiempo es O (n) en el peor de los casos, ya que primero tenemos que copiar n elementos.
En teoría, la adición de un nuevo elemento se ejecuta en un tiempo constante amortizado. Es decir, agregar n elementos requiere O (n) tiempo. Sin embargo, algunas adiciones individuales pueden funcionar mal debido a la sobrecarga de copia.
2.2. Acceso por índice
Acceder a los elementos por sus índices es donde realmente brilla ArrayList . Para recuperar un elemento en el índice i, solo tenemos que devolver el elemento que reside en el índice i de la matriz de respaldo. En consecuencia, la complejidad de tiempo para el acceso por operación de índice es siempre O (1).
2.3. Eliminar por índice
Supongamos que vamos a eliminar el índice 6 de nuestra ArrayList, que corresponde al elemento 15 en nuestra matriz de respaldo:
Después de marcar el elemento deseado como eliminado, debemos mover todos los elementos después de él en un índice. Obviamente, cuanto más cerca esté el elemento del inicio de la matriz, más elementos debemos mover. Por tanto, la complejidad temporal es O (1) en el mejor de los casos y O (n) en el promedio y en el peor de los casos.
2.4. Aplicaciones y limitaciones
Por lo general, ArrayList es la opción predeterminada para muchos desarrolladores cuando necesitan una implementación de List . De hecho, es una opción sensata cuando el número de lecturas es mucho mayor que el de escrituras .
A veces necesitamos lecturas y escrituras igualmente frecuentes. Si tenemos una estimación del número máximo de elementos posibles, entonces todavía tiene sentido usar ArrayList . Si ese es el caso, podemos inicializar ArrayList con una capacidad inicial:
int possibleUpperBound = 10_000; List items = new ArrayList(possibleUpperBound);Esta estimación puede evitar muchas copias innecesarias y asignaciones de matrices.
Además, las matrices están indexadas por valores int en Java. Por lo tanto, no es posible almacenar más de 232 elementos en una matriz Java y, en consecuencia, en ArrayList .
3. LinkedList
LinkedList , como su nombre indica, utiliza una colección de nodos vinculados para almacenar y recuperar elementos . Por ejemplo, así es como se ve la implementación de Java después de agregar cuatro elementos:
Cada nodo mantiene dos punteros: uno que apunta al siguiente elemento y otro que hace referencia al anterior. Ampliando esto, la lista doblemente enlazada tiene dos punteros que apuntan al primer y último elemento.
Nuevamente, evaluemos esta implementación con respecto a las mismas operaciones fundamentales.
3.1. Añadir
Para agregar un nuevo nodo, primero, debemos vincular el último nodo actual al nuevo nodo:
Y luego actualice el último puntero:
Como ambas operaciones son triviales, la complejidad de tiempo para la operación de suma es siempre O (1) .
3.2. Acceso por índice
LinkedList, a diferencia de ArrayList, no admite el acceso aleatorio rápido. Entonces, para encontrar un elemento por índice, debemos recorrer una parte de la lista manualmente .
En el mejor de los casos, cuando el elemento solicitado está cerca del inicio o el final de la lista, la complejidad temporal sería tan rápida como O (1). Sin embargo, en los escenarios promedio y en el peor de los casos, podemos terminar con un tiempo de acceso O (n) ya que tenemos que examinar muchos nodos uno tras otro.
3.3. Eliminar por índice
Para eliminar un elemento, primero debemos encontrar el elemento solicitado y luego desvincularlo de la lista . En consecuencia, el tiempo de acceso determina la complejidad del tiempo, es decir, O (1) en el mejor de los casos y O (n) en promedio y en el peor de los casos.
3.4. Aplicaciones
Las LinkedLists son más adecuadas cuando la tasa de adición es mucho mayor que la tasa de lectura .
Además, se puede utilizar en escenarios de mucha lectura cuando la mayoría de las veces queremos el primer o el último elemento. Vale la pena mencionar que LinkedList también implementa la interfaz Deque , lo que permite un acceso eficiente a ambos extremos de la colección.
En general, si conocemos sus diferencias de implementación, podríamos elegir fácilmente una para un caso de uso particular.
Por ejemplo, digamos que vamos a almacenar muchos eventos de series de tiempo en una estructura de datos similar a una lista. Sabemos que recibiríamos ráfagas de eventos cada segundo.
Además, debemos examinar todos los eventos uno tras otro periódicamente y proporcionar algunas estadísticas. Para este caso de uso, LinkedList es una mejor opción porque la tasa de adición es mucho mayor que la tasa de lectura.
Además, leeríamos todos los elementos, por lo que no podemos superar el límite superior O (n) .
4. Conclusión
En este tutorial, primero, analizamos cómo se implementan ArrayList y LinkLists en Java.
También evaluamos diferentes casos de uso para cada uno de estos.