Publicado: 29/06/24
Estructura fundamental para implementar otras estructuras
Una linked list es una secuencia de datos conectados a través de enlaces. Cada elemento recibe el nombre de NODO y posee dos partes:
El primer enlace recibe el nombre de head (cabeza) y el último enlace, que apunta a un valor nulo, es llamado tail (cola).
Un NODO solamente sabe acerca de los datos que contiene y quién es su vecino próximo.
Una lista enlazada puede ser utilizada para implementar otras estructuras de datos, como por ejemplo:
Una aplicación común de las listas enlazadas es el acceso a información de adelante hacia atrás y viceversa, lo que se conoce como backward and forward navigation. Este tipo de navegación es el que se emplea en navegadores web o en un reproductor de música.
Una característica importante de las listas enlazadas es que son estructuras de tipo lineal. Esto significa que hay una secuencia u orden que determina cómo son construidas y recorridas. Es útil pensar en que las listas enlazadas son similares a las listas clásicas en la forma en que los datos son secuenciados. En ambas estructuras, el orden importa.
Las listas enlazadas son, además, de tipo dinámico, lo que significa que pueden “crecer” y “encogerse” en memoria. No es necesario especificar un tamaño de memoria a asignar antes de crear la estructura, y su tamaño, forma y la cantidad de memoria necesaria pueden modificarse en tiempo de ejecución.
La principal diferencia entre listas (arrays) y las listas enlazadas es cómo utilizan la memoria de la computadora. Cuando se crea una lista, necesita una cierta cantidad de memoria. Si tuvieramos un array con 7 letras, necesitaríamos 7 bytes de memoria para representar ese array. Pero necesitaríamos toda esa memoria en un bloque contiguo. Nuestra computadora necesitaría disponer esos 7 bytes de memoria juntos, un byte junto al otro, todos en un mismo lugar.
Por otro lado, cuando se crea una lista enlazada, no necesita los 7 bytes de memoria en un solo lugar. Un byte puede “vivir” en alguna parte, mientras que el próximo byte puede este en otro lugar totalmente distinto. Las listas enlazadas no necesitan un bloque de memoria contiguo, sino que los espacio de memoria que usan pueden estar dispersados.
El tipo de lista enlazada más simple, basada en el hecho de que sólo puede ser recorrida en una única dirección. Hay una sola pista a recorrer, comenzando por la cabeza hasta el último nodo que apunta a un valor nulo.
En este tipo de lista enlazada, un nodo puede contener dos referencias:
Esto permite recorrer la estructura no solo hacia adelante, sino que también hacia atrás. Es importante tener en cuenta que cada nodo, al contener dos referencias, hace que este tipo de lista enlazada requiera más espacio y memoria.
La teoría de cómo funciona internamente una lista enlazada no es tan difícil de comprender. El verdadero desafío es implementarla (y te hablo por experiencia propia).
Es por eso que te dejo dos ejercicios. Uno para implementar una lista enlazada simple y el otro donde te enfrentarás a una lista enlazada doble. Ambos ejercicios son en Python, el lenguaje que estoy utilizando actualmente para aprender sobre estructuras de datos. Estoy seguro de que Exercism, la plataforma donde están estos ejercicios, tiene los mismos pero aplicados a otros lenguajes. Te dejo a vos la búsqueda de tales ejercicios.
Ahora bien, sé que a lo mejor necesites algo más de teoría que lo que ofrece este post. Es por ello que te dejo más artículos para reforzar los conceptos de esta estractura de datos. Parte de este post está basado en estos artículos, así que aprovecho esta sección para citar mis fuentes, matando dos pájaros de un tiro.
¡Felicitaciones por haber aprendido sobre listas enlazadas! Tal como viste, esta estructura es utilizada para implementar otras estructuras de datos, por lo que es fundamental conocerla y practicarla con frecuencia para interiorizar sus conceptos.
Espero que este breve resúmen haya aportado a tu conocimiento. Si encontraste este artículo en Google o te lo compartieron, te invito a pasarte por el "artículo central" sobre Estructuras de datos, ya que allí también encontrarás enlaces a futuros artículos que iré publicando al respecto.
Python / ETL dev | Data Engineer en progreso | Musico | Nerd de yerbas varias