La información está a nuestro alrededor.

En el mundo del software, la forma en que elegimos organizar nuestra información es la mitad de la batalla. Sin embargo, aquí está la cosa: hay muchas formas de resolver un problema. Y cuando se trata de organizar nuestros datos, hay muchas herramientas que podrían funcionar para el trabajo. El truco es saber qué herramienta es la adecuada para usar.

Independientemente del lenguaje en el que comencemos a codificar, una de las primeras cosas que encontramos son las estructuras de datos , que son las diferentes formas en que podemos organizar nuestros datos; variables , matrices , hashes y objetos son todos tipos de estructuras de datos. Pero estos son solo la punta del iceberg cuando se trata de estructuras de datos; hay muchos más, algunos de los cuales comienzan a sonar súper complicados cuanto más escuchas sobre ellos.

Una de esas cosas complicadas para mí siempre han sido las listas enlazadas . Conozco las listas vinculadas desde hace algunos años, pero nunca puedo mantenerlas claras en mi cabeza. Realmente solo pienso en ellos cuando me estoy preparando (o, a veces, en medio de) una entrevista técnica y alguien me pregunta por ellos. Investigaré un poco y creo que entiendo de qué se tratan, pero después de unas semanas, las olvido nuevamente. Todo esto es bastante ineficiente, y todo se debe al hecho de que sé que existen, ¡pero no los entiendo fundamentalmente ! Entonces, es hora de cambiar eso y responder la pregunta: ¿qué diablos es una lista vinculada, de todos modos?

Estructuras de datos lineales

Si realmente queremos comprender los conceptos básicos de las listas vinculadas, es importante que hablemos sobre qué tipo de estructura de datos son.

Una característica de las listas enlazadas es que son estructuras de datos lineales , lo que significa que hay una secuencia y un orden en la forma en que se construyen y recorren. Podemos pensar en una estructura de datos lineal como un juego de rayuela : para llegar al final de la lista, tenemos que revisar todos los elementos de la lista en orden o secuencialmente . Las estructuras lineales, sin embargo, son lo opuesto a las estructuras no lineales. En estructuras de datos no lineales , los elementos no tienen que estar ordenados, lo que significa que podríamos atravesar la estructura de datos de forma no secuencial .

Puede que no siempre nos demos cuenta, ¡pero todos trabajamos con estructuras de datos lineales y no lineales todos los días! Cuando organizamos nuestros datos en hashes (a veces llamados diccionarios ), estamos implementando una estructura de datos no lineal. Los árboles y los gráficos también son estructuras de datos no lineales que atravesamos de diferentes maneras, pero hablaremos más sobre ellos con más profundidad más adelante en el año.

De manera similar, cuando usamos matrices en nuestro código, ¡estamos implementando una estructura de datos lineal! Puede ser útil pensar en matrices y listas enlazadas como similares en la forma en que secuenciamos los datos. En ambas estructuras, el orden importa . Pero, ¿qué hace que las matrices y las listas vinculadas sean diferentes?

Gestión de la memoria

El mayor diferenciador entre matrices y listas enlazadas es la forma en que utilizan la memoria en nuestras máquinas. Aquellos de nosotros que trabajamos con lenguajes tipados dinámicamente como Ruby, JavaScript o Python no tenemos que pensar en cuánta memoria usa una matriz cuando escribimos nuestro código en el día a día porque hay varias capas de abstracción que terminan con nosotros sin tener que preocuparnos por la asignación de memoria en absoluto.

¡Pero eso no significa que la asignación de memoria no esté sucediendo! La abstracción no es magia, es solo la simplicidad de esconder cosas que no necesitas ver o tratar todo el tiempo. Incluso si no tenemos que pensar en la asignación de memoria cuando escribimos el código, si queremos entender realmente lo que sucede en una lista enlazada y qué la hace poderosa, tenemos que llegar al nivel rudimentario.

Ya hemos aprendido sobre binarios y cómo los datos se pueden dividir en bits y bytes. Así como los caracteres, números, palabras y oraciones requieren bytes de memoria para representarlos, también lo hacen las estructuras de datos.

Cuando se crea una matriz , necesita una cierta cantidad de memoria. Si tuviéramos 7 letras que necesitáramos almacenar en una matriz, necesitaríamos 7 bytes de memoria para representar esa matriz. Pero necesitaríamos toda esa memoria en un bloque contiguo . Es decir, nuestra computadora necesitaría ubicar 7 bytes de memoria que estaban libres, un byte al lado del otro, todos juntos, en un solo lugar.

Por otro lado, cuando nace una lista vinculada , no necesita 7 bytes de memoria en un solo lugar. Un byte podría vivir en algún lugar, mientras que el siguiente byte podría almacenarse en otro lugar de la memoria. Las listas enlazadas no necesitan ocupar un solo bloque de memoria; en cambio, la memoria que utilizan puede estar esparcida por todas partes .

La diferencia fundamental entre matrices y listas enlazadas es que las matrices son estructuras de datos estáticas , mientras que las listas enlazadas son estructuras de datos dinámicas . Una estructura de datos estática necesita que todos sus recursos se asignen cuando se crea la estructura; esto significa que incluso si la estructura creciera o se redujera de tamaño y se agregaran o quitaran elementos, siempre necesitaría un tamaño y una cantidad de memoria determinados. Si fuera necesario agregar más elementos a una estructura de datos estática y no tuviera suficiente memoria, necesitaría copiar los datos de esa matriz, por ejemplo, y volver a crearla con más memoria para poder agregar elementos a eso.

Por otro lado, una estructura de datos dinámica puede reducirse y crecer en la memoria. No necesita una cantidad determinada de memoria para ser asignada para existir, y su tamaño y forma pueden cambiar, y la cantidad de memoria que necesita también puede cambiar.

A estas alturas, ya podemos empezar a ver algunas diferencias importantes entre matrices y listas enlazadas. Pero esto plantea la pregunta: ¿qué permite que una lista enlazada tenga su memoria dispersa por todas partes? Para responder a esta pregunta, debemos observar la forma en que está estructurada una lista vinculada.

Partes de una lista vinculada

Una lista vinculada puede ser pequeña o enorme, pero no importa el tamaño, las partes que la componen son bastante simples. Una lista vinculada está formada por una serie de nodos , que son los elementos de la lista.

El punto de partida de la lista es una referencia al primer nodo, al que se hace referencia como cabeza . Casi todas las listas enlazadas deben tener un encabezado, porque este es efectivamente el único punto de entrada a la lista y todos sus elementos, y sin él, ¡no sabría por dónde empezar! El final de la lista no es un nodo, sino un nodo que apunta a un valor nulo o vacío.

Un solo nodo también es bastante simple. Tiene solo dos partes: los datos o la información que contiene el nodo y una referencia al siguiente nodo .

Si podemos entender esto, entonces estamos a mitad de camino. La forma en que funcionan los nodos es muy importante y muy poderosa, y podría resumirse así:

Un nodo solo sabe qué datos contiene y quién es su vecino.

Un solo nodo no sabe cuánto tiempo tiene la lista vinculada, y es posible que ni siquiera sepa dónde comienza o dónde termina. Lo único que le preocupa a un nodo son los datos que contiene y a qué nodo hace referencia su puntero: el siguiente nodo de la lista.

Y esta es la razón por la que una lista enlazada no necesita un bloque de memoria contiguo. Debido a que un solo nodo tiene la "dirección" o una referencia al siguiente nodo, no es necesario que vivan uno al lado del otro, de la forma en que los elementos deben vivir en una matriz. En cambio, podemos confiar en el hecho de que podemos recorrer nuestra lista apoyándonos en las referencias del puntero al siguiente nodo, lo que significa que nuestras máquinas no necesitan bloquear un solo trozo de memoria para representar nuestra lista.

Esta es también la explicación de por qué las listas vinculadas pueden crecer y reducirse dinámicamente durante la ejecución de un programa. Agregar o eliminar un nodo con una lista vinculada se vuelve tan simple como reorganizar algunos punteros, en lugar de copiar los elementos de una matriz. Sin embargo, también hay algunos inconvenientes en las listas vinculadas que no les mencionaré todavía, pero más sobre los de la próxima semana.

Por ahora, ¡simplemente disfrutaremos de la gloria de lo geniales que son las listas enlazadas!

Listas para todas las formas y tamaños

Aunque las partes de una lista vinculada no cambian, la forma en que estructuramos nuestras listas vinculadas puede ser bastante diferente. Como la mayoría de las cosas en el software, dependiendo del problema que intentemos resolver, un tipo de listas vinculadas puede ser una mejor herramienta para el trabajo que otro.

Las listas enlazadas individualmente son el tipo más simple de lista enlazada, basándose únicamente en el hecho de que solo van en una dirección. Hay una sola pista en la que podemos recorrer la lista; empezamos por el cabezal de nodo, y atravesar desde la raíz hasta que el último nodo, que pondrá fin a un vacío nulo valor.

Pero así como un nodo puede hacer referencia a su nodo vecino subsiguiente, ¡también puede tener un puntero de referencia a su nodo anterior! Esto es lo que llamamos una lista doblemente enlazada , porque hay dos referencias contenidas dentro de cada nodo: una referencia al siguiente nodo, así como al nodo anterior . Esto puede ser útil si quisiéramos poder atravesar nuestra estructura de datos no solo en una sola pista o dirección, sino también hacia atrás.

Por ejemplo, si quisiéramos poder saltar entre un nodo y el nodo anterior sin tener que volver al principio de la lista , una lista doblemente enlazada sería una mejor estructura de datos que una lista enlazada individualmente. Sin embargo, todo requiere espacio y memoria, por lo que si nuestro nodo tuviera que almacenar dos punteros de referencia en lugar de solo uno, eso sería otra cosa a considerar.

Una lista enlazada circular es un poco extraña porque no termina con un nodo que apunta a un valor nulo. En cambio, tiene un nodo que actúa como la cola de la lista (en lugar del nodo principal convencional) y el nodo después del nodo de cola es el comienzo de la lista. Esta estructura de organización hace que sea realmente fácil agregar algo al final de la lista, porque puede comenzar a atravesarlo en el nodo de cola , ya que el primer elemento y el último elemento se apuntan entre sí. Las listas enlazadas circulares pueden empezar a volverse realmente locas porque podemos convertir tanto una lista enlazada individualmente como una lista enlazada doble en una lista enlazada circular.

Pero no importa cuán complicada sea una lista vinculada, si podemos recordar los fundamentos de un nodo y cómo funciona y cómo están estructuradas las diferentes referencias de puntero en nuestra lista, ¡no hay lista vinculada que no podamos abordar!

La semana que viene, en la parte 2 de esta serie, profundizaremos en la complejidad del espacio-tiempo de las listas enlazadas y cómo se comparan con su prima, la matriz. ¡Prometo que en realidad es mucho más divertido de lo que parece!

Recursos

Si cree que las listas vinculadas son geniales, consulte estos recursos útiles.

1. Diferencias entre matrices y listas enlazadas , Damien Wintour
2. Estructuras de datos: matrices frente a listas enlazadas , mycodeschool
3. Listas vinculadas: conceptos básicos , Dr. Edward Gehringer
4. Introducción a las listas vinculadas , Dr. Victor Adamchik
5. Estructuras de datos e implementaciones , Dra. Jennifer Welch
6. Estructuras de datos estáticas frente a estructuras de datos dinámicas , Ayoma Gayan Wijethunga