Consejos para usar las colecciones

1. Lista de colecciones

Como podrás recordar, Java tiene colecciones - una herramienta útil para almacenar objetos del mismo tipo.

Recordemos las principales interfaces relacionadas con las colecciones:

List, Set, Map y Queue.

Como de costumbre, las herramientas no son necesariamente buenas o malas, lo que importa es si las estamos utilizando para su propósito previsto. Y para hacer eso, debemos comprender a fondo sus características específicas para saber qué colección usar y cuándo.

1. List

Comencemos con la colección más utilizada.

List es lo más cercano posible a un simple array.

Esta colección nos permite almacenar convenientemente una lista de objetos del mismo tipo sin preocuparnos por el tamaño de la colección en sí, como tendríamos que hacer si estuviéramos usando un array. Los elementos de la colección se acceden por índice. Si sabemos exactamente dónde está un objeto y necesitamos acceder a él con frecuencia sin tener que agregar o eliminar elementos con frecuencia, una List es ideal.

2. Set

Set tiene una estructura completamente diferente.

Set es más adecuado cuando necesitamos almacenar objetos únicos. Por ejemplo, un conjunto de autores en una biblioteca donde cada autor es único. Pero no podemos simplemente tomar cualquier autor específico de ella. Set nos permite verificar rápidamente si un autor particular está presente en nuestra biblioteca, es decir, podemos verificar si un objeto único está presente en un Set. También podemos iterar sobre toda la colección, accediendo a cada elemento, pero hacerlo no es óptimo.

En otras palabras, para nuestra biblioteca, un Set puede representar la colección de todos los autores únicos para verificar rápidamente si algún autor en particular está presente.

3. Map

Mapa es más como una archivo, donde cada archivo está firmado y puede almacenar objetos individuales o estructuras enteras. Mapa se debe utilizar en casos en los que necesitamos mantener una asignación de un valor a otro.

Para Mapa, estas relaciones se llaman pares clave-valor.

Podríamos utilizar esta estructura en nuestra biblioteca usando objetos de autor como las claves y listas (objetos Lista) de libros como los valores. Por lo tanto, después de verificar un Conjunto para ver si un objeto de autor existe en la biblioteca, podemos usar el mismo objeto de autor para obtener una Lista de sus libros de un Mapa.

4. Cola

Cola es una colección que, sorpresa, implementa el comportamiento de una cola. Y la cola puede ser tanto LIFO (último en entrar, primero en salir) o FIFO (primero en entrar, primero en salir). Además, la cola puede ser bidireccional, o "de doble final".

Esta estructura es útil cuando los objetos agregados a la clase necesitan ser utilizados en el orden en que se reciben. Por ejemplo, tomemos nuestra biblioteca.

Podemos agregar a los visitantes recién llegados a una Cola y atenderlos en orden, emitiendo los libros que vienen a buscar.

Como podemos ver, cada una de estas estructuras es buena si se usa para su propósito previsto. Y encontramos buenos usos para los cuatro tipos de colecciones en un solo ejemplo de biblioteca.

2. Complejidad

Como se señaló anteriormente, las colecciones que consideramos anteriormente son interfaces, lo que significa que deben tener implementaciones para que podamos usarlas.

Al igual que martillar clavos con un microscopio no es la mejor idea, no todas las implementaciones de una colección son adecuadas para cada situación.

Cuando se elige la herramienta adecuada para un trabajo, típicamente se observan dos características:

• ¿Qué tan bien se adapta la herramienta al trabajo?
• ¿Qué tan rápido se realizará el trabajo?

Hemos pasado algún tiempo descubriendo cómo elegir una herramienta adecuada para un trabajo, pero su velocidad es algo nuevo.

En informática, la velocidad de una herramienta se expresa a menudo en términos de complejidad temporal y se denota con una letra mayúscula O.

¿Qué es la complejidad temporal?

En términos simples, la complejidad temporal indica el tiempo requerido para que un algoritmo en la colección realice una acción particular (añadir/eliminar un elemento, buscar un elemento).

ArrayList vs LinkedList

Veamos esto usando dos implementaciones de la interfaz List — ArrayList y LinkedList.

A simple vista, trabajar con estas colecciones es similar:

List<String> arrayList = new ArrayList<>();
arrayList.add(String);
arrayList.get(index);
arrayList.remove(index);
arrayList.remove(String);
 
List<String> linkedList = new LinkedList<>();
 
linkedList.add(String);
 
linkedList.get(index);
linkedList.remove(index);
linkedList.remove(String);
    

Como puede ver, para ambos tipos de colecciones, agregar, obtener y eliminar elementos parece lo mismo. Esto se debe a que son implementaciones en la misma interfaz. Pero ahí es donde terminan las similitudes.

Debido a sus diferentes implementaciones de la interfaz List, estas dos estructuras realizan diferentes acciones de manera más eficiente que otras.

Considere la eliminación y adición de un elemento.

Si necesitamos eliminar un elemento del medio de un ArrayList, tenemos que sobrescribir cualquier parte de la lista que siga al elemento que eliminamos.

Supongamos que tenemos una lista de 5 elementos y queremos eliminar el tercero.

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
list.remove(2);
    

En este caso, la eliminación libera una celda, por lo que debemos escribir el cuarto elemento donde estaba el tercero y el quinto donde estaba el cuarto.

Esto es altamente ineficiente.

Lo mismo ocurre cuando se agrega un elemento en medio de la lista.

LinkedList tiene una estructura diferente. Agregar o eliminar elementos es rápido, ya que solo necesitamos cambiar las referencias en los elementos anteriores y siguientes, excluyendo así el objeto que estamos eliminando de la cadena de elementos.

Al volver al ejemplo de la misma lista de 5 elementos, después de eliminar el tercer elemento, todo lo que necesitamos hacer es simplemente cambiar la referencia del segundo elemento al siguiente elemento y la referencia del cuarto elemento al anterior.

Cuando se agrega un elemento a la lista, ocurre el mismo proceso, pero al revés.

Observe cuánto menos trabajo necesitamos hacer en un LinkedList en comparación con un ArrayList. Y eso es solo con 5 elementos. Si nuestra lista tuviera 100 o más elementos, la superioridad de LinkedList se volvería aún más notable.

Pero, ¿cómo cambia la situación si accedemos a un elemento por índice?

Todo es exactamente lo opuesto aquí.

Dado que ArrayList está estructurado como un arreglo ordinario, obtener cualquier elemento por su índice es muy fácil para nosotros. Simplemente movemos el puntero a un lugar determinado y obtenemos el elemento de la celda correspondiente.

Pero una LinkedList simplemente no funciona de esa manera. Tenemos que recorrer todos los elementos de la lista para encontrar el elemento con un índice determinado.

¿Intentamos expresar todo esto en términos de big O?

Comencemos accediendo a un elemento por índice.

En un ArrayList, esto ocurre en un solo paso, independientemente de dónde se encuentre el elemento en la lista, ya sea al final o al principio.

En este caso, la complejidad de tiempo será O(1).

En una LinkedList, tenemos que iterar sobre un número de elementos igual al valor del índice que necesitamos.

La complejidad de tiempo para tal acción es O(n), donde n es el índice del elemento que necesitamos.

Aquí se puede ver que el número que ponemos entre paréntesis en el big-O corresponde al número de acciones realizadas.

¿Regresamos a eliminar y agregar elementos?

Comencemos con LinkedList.

Como no necesitamos realizar una gran cantidad de acciones para agregar o eliminar un elemento, y la velocidad de esta operación no depende de ninguna manera de dónde se encuentra el elemento, su complejidad se expresa como O(1) y se dice que es constante.

La complejidad de tiempo de esta operación para ArrayList también es O(n), lo que llamamos complejidad lineal.

En algoritmos con complejidad lineal, el tiempo de ejecución depende directamente del número de elementos que se van a procesar. También puede depender de la posición del elemento, ya sea al principio de la lista o hacia el final.

La complejidad de tiempo también puede ser logarítmica. Esto se expresa como O(log n).

Como ejemplo, consideremos un TreeSet ordenado que consta de 10 números. Queremos encontrar el número 2.

Dado que la lista está ordenada y no contiene duplicados, podemos dividirla por la mitad y verificar en qué mitad estaría el número deseado, descartar la parte irrelevante y luego repetir este proceso hasta que lleguemos al elemento deseado. En última instancia, encontraremos (o no encontraremos) el número después de procesar log(n) elementos.

Aquí hay una tabla que resume la complejidad de tiempo del resto de las colecciones.

Ahora que tenemos una tabla que muestra la complejidad temporal de las colecciones populares, podemos responder la pregunta de por qué, de tantas colecciones, usamos más a menudo ArrayList, HashSet y HashMap.

Simplemente, son las más eficientes para la mayoría de las tareas :)