Las listas enlazadas son un tipo de estructura de datos que se utilizan mucho, sobre todo en desarrollo backend. En este artículo introductorio aprenderás acerca de las ventajas, desventajas y casos de uso de este tipo de estructura.

En este artículo aprenderás:

1. ¿Qué es una lista enlazada (Doubly)?
2. ¿Cómo construir una lista enlazada?
3. Ventajas de las listas enlazadas
4. Desventajas de las listas enlazadas

¿Qué es una lista enlazada (Doubly)?

*Existen dos tipos de listas enlazadas. Este artículo explicará el tipo 'Doubly' que es la implementación más compleja de las dos. Una lista enlazada 'Singly' es muy parecida, pero sin la propiedad 'previous'.

Una lista enlazada Doubly es una estructura de datos basada en nodos. Un nodo no es nada más que un contenedor (un objeto) que almacena parte de la información que contiene la lista. La razón del nombre 'lista enlazada' es porque los nodos están enlazados unos con otros. De manera más específica, cada nodo está enlazado con mínimo 1 y máximo 2 nodos más. La manera en la que estos nodos están enlazados es mediante las propiedades 'next' y 'previous' (puedes encontrar implementaciones con nombres diferentes (p. ej. 'next' y 'prev')). La propiedad 'next' hace referencia al nodo siguiente en la lista y 'previous' al nodo anterior. Cada nodo tiene también una propiedad 'value' que contiene el valor que se pretende almacenar (también puedes encontrarla con otros nombres (p. ej. 'data')).

Ejemplo simplificado *

En el ejemplo anterior podemos empezar a imaginar cómo podríamos recorrer una lista enlazada para buscar un valor. Si empezamos por el nodo1 y queremos llegar al nodo3, lo único que tenemos que hacer es acceder al nodo que está dos lugares por delante del nodo1. De esta manera, para acceder al valor del nodo3 comenzando por el nodo1 tendríamos que hacer lo siguiente: nodo1.next.next.value => 'Valor 3'

Para terminar con el concepto de una lista enlazada nos hacen falta 2 cosas:

1. ¿Cómo sabemos dónde empieza la lista?

   Existe un nodo en cada lista enlazada que hace referencia al inicio y se llama 'head'. Head tiene la misma estructura que cualquier otro nodo, pero siempre su 'previous' va a ser nulo.

2. ¿Y dónde acaba?
   Existe un nodo en cada lista enlazada que hace referencia al final y se llama 'tail'. Tail también tiene la misma estructura que cualquier otro nodo, pero siempre su 'next' va a ser nulo.

¿Cómo construir una lista enlazada?

Para facilitar la construcción de los nodos en nuestra lista enlazada, vamos a crear una clase 'Nodo' para instanciar cada uno de ellos y una clase 'ListaEnlazada' para instanciar la lista.

Una vez que tenemos las clases hechas podemos utilizaras para instanciar la lista y los nodos con valores.

Ahora para poder visualizar la lista enlazada que creamos, vamos a iterar sobre ella desde el nodo 'head' hasta que acabe la lista. La manera que tenemos para saber si la lista terminó es cuando el valor de la propiedad 'next' del nodo es nula, esto significa que estamos en el último nodo.

Ventajas de una lista enlazada

1. Es una estructura de datos dinámica: Esto significa que puede crecer y decrecer dinamicamente a medida que enlazamos y desenlazamos nodos.
2. Es muy rápido insertar y borrar nodos: A diferencia de un arreglo, insertar o borrar un nodo de una lista enlazada sucede en tiempo constante. Para insertar un elemento al inicio de un arreglo se tienen que desplazar todos los elementos un lugar para hacer espacio para el nuevo, y lo mismo para borrarlo. Con una lista enlazada únicamente debemos de hacer una nueva referencia al nodo que estamos insertando.
3. Uso eficiente de memoria: Debido a que cada nodo existe en su propio espacio en memoria, los elementos de una lista enlazada no necesariamente están almacenados uno junto al otro. Cada uno apunta al espacio en memoria en el que está el nodo al que hace referencia.

Desventajas de una lista enlazada

1. Buscar un elemento en una lista enlazada es lento: A diferencia de un arreglo, en una lista enlazada no puedes acceder a un nodo simplemente con su indice, tienes que iterar desde el principio (head) hasta llegar al nodo que necesitas. En un arreglo, buscar un elemento sucede en tiempo constante.
2. Ocupa más memoria que un arreglo: Debido a que es necesario almacenar la referencia (dirección en memoria) de los nodos adyacentes, una lista enlazada ocupa más memoria.