Lista Enlazada

Estructuras de Datos – Lista Enlazada

In Algoritmos, Tutoriales by Josué V. Herrera0 CommentsLast Updated: 04 Ago 2017

Hoy abordaremos un nuevo algoritmo, aprenderemos a implementar una Lista Enlazada, una estructura de datos bien importante y de las más usadas. Pudiéramos clasificarla como clásica ya que forma parte de esas estructuras de datos que todo programador debe conocer, de hecho, con estas podemos implementar otras estructuras de datos.

Según Wikipedia:

…Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias, enlaces o punteros al nodo anterior o posterior. El principal beneficio de las listas enlazadas respecto a los vectores convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento….

Pero no te abrumes con esta explicación, vamos a crear nuestra propia definición poco a poco y mediante ejemplos. Comencemos por decir que una Lista Enlazada es una secuencia de elementos donde, a cada uno de estos se les llama nodos. Al mismo tiempo también existen diferentes tipos de listas enlazadas: listas enlazadas simples o de un solo enlace, listas doblemente enlazadas, listas enlazadas circulares y listas enlazadas doblemente circulares, aunque las más importantes o más usadas son las listas simples y las doblemente enlazadas:

Listas simples: Son aquellas donde cada nodo solamente cuenta con una referencia o enlace hacia el nodo siguiente.

Lista Enlazada Simple

Listas doblemente enlazadas: Son aquellas donde cada nodo cuenta con una referencia o enlace hacia el nodo anterior y otra hacia el siguiente.

Lista Doblemente Enlazada

También tenemos que llevar un registro de donde comienza y termina la lista, esto se logra con punteros a los que se les nombra como head (cabeza) para señalizar el inicio y tail (cola de perro / de dragón) para el final.

Lista Doblemente Enlazada - Head y Tail

Como podemos constatar en la imagen en el primer nodo el puntero Head apunta a este mientras que el Tail se establece a nil y en el último nodo el Head se iguala a nil mientras que el Tail apunta hacia este nodo.

En este artículo abordaremos las listas doblemente enlazadas ya que al ser más complejas que las simples usualmente son las que más interés generan. Espero que esto no desanime a ningún lector, ya que luego de leer y comprender este artículo seremos capaces de crear una lista enlazada simple sin problema alguno.

Implementando una Lista Enlazada

Como una Lista Enlazada está conformada por nodos, comenzaremos por crear la clase Node:

Una estructura de datos necesita datos y los nodos de una lista representan esos datos así que añadimos ahora el valor que almacenará cada nodo:

Hemos creado una propiedad llamada value de tipo String. También declaramos un inicializador el cual es requerido en pos de inicializar todas las propiedades no opcionales de nuestra clase.

También necesitamos en cada nodo una referencia al nodo siguiente y al anterior:

La clase Node va tomando forma, en las líneas 5 y 7 añadimos dos propiedades de tipo Node ya que evidentemente estas referencian a otros nodos en nuestra lista. Notemos que ambas son opcionales ya que como explicamos anteriormente, tanto al inicio como al final una de estas adoptan el valor nil. Importante comentar que la propiedad previous la hemos marcado como weak para evitar ciclos de referencias fuerte y con esto asegurar que la memoria asignada a cada nodo sea liberada correctamente.

Si deseas aprender más sobre la palabra clave weak te recomiendo nuestro artículo sobre el manejo de memoria en el lenguaje de programación Swift.

Ahora prosigamos creando la clase que representará a nuestra Lista Enlazada:

Esta clase llevará el registro de donde comienza y termina la lista, al igual que otras funciones que nos ayudarán a conocer si está vacía o con cuantos elementos cuenta esta lista doblemente enlazada. Una funcionalidad que también vamos a necesitar será la de añadir un nuevo nodo a la lista:

…y para esto crearemos una función de nombre append en la clase LinkedList.

En esta función recibimos como parámetro el nuevo valor que procederemos a convertir en un nuevo nodo y recordemos que la razón de ser de los nodos es que podamos encadenar un valor en nuestra lista de elementos. En la línea 5 verificamos que tailNode no sea nil en cuyo caso la lista ya contendría otros elementos y tendríamos que hacer que el nuevo nodo apunte a la cola de la lista y a su elemento previo, tal y como hemos hecho en las líneas 7 y 9. Por último y en cualquiera de los casos establecemos que la cola de la lista sea el nuevo nodo y aumentamos en una unidad el contador de elementos en la lista.

Imprimiendo la Lista Enlazada

Creo conveniente añadir la posibilidad de imprimir la lista no con un enfoque pleno en esta característica ya que en una aplicación real la manera en la que se imprimen o se muestran los datos en pantalla pueden variar mucho, mi intención es plenamente con fines didácticos y depuración.

Para lograr lo antes comentado adoptaremos el protocolo CustomStringConvertible el cual ya hemos visto en otros artículos y que nos obliga a implementar una propiedad computada de tipo String y de nombre description:

Lo primero que destaco del código es que hemos extendido la clase en pos de añadir la nueva funcionalidad. El motivo principal reside en que el modelo de datos de una aplicación real jamás imprimirá directamente en pantalla, por no mencionar que cada aplicación muestra los datos de maneras bien distintas. El enfoque correcto sería extender la clase y así añadimos nuestro propio formato, como acabamos de hacer. Hemos declarado una variable de nombre text la cual almacenará la cadena que nos disponemos a crear, en un inicio solamente almacena un corchete abierto ([) que es lo que da inicio a la cadena de texto. Luego de la línea 8 a la 20 iteramos sobre la lista agregando los valores de cada nodo a la cadena de texto y finalizamos en la línea 22 agregando el corchete cerrado (]).

Para probar que todo está funcionando correctamente agregaremos las siguientes líneas de código:

…la salida en pantalla:

Accediendo a los Nodos

Aún cuando una lista enlazada funciona más eficiente cuando nos movemos en orden a través de los nodos haciendo uso de previous y next, en algunas ocasiones es oportuno acceder a un elemento haciendo uso de un índice.

Para lograr esto declararemos la función nodeAt(index:) la cual retornará el nodo asociado al índice específico:

Esta función recibe un valor entero y lo primero que hacemos con este en la línea 3 es verificar que no sea negativo. En la siguiente línea creamos una variable que almacena el primer nodo en la lista y seguido a esto creamos otra variable que igualamos al valor pasado como parámetro a la función. De la línea 9 a la 21 tenemos un bucle de tipo while que toma como expresión de control node != nil, es decir mientras la variable node tenga asociado un valor el bucle continuará ejecutando el código que hemos definido dentro de él.  Lo primero que hacemos dentro del bucle es verificar si el índice solicitado es 0 ya que, de ser así, retornamos la variable node, recordemos que al definir var node = head estamos creando una referencia al primer elemento de la lista, el cual se encuentra en el indice 0, por lo que siendo este el caso ya tenemos el nodo correspondiente a ese índice y no tiene sentido continuar con el bucle. En la línea 17 restamos en uno a la variable i que funge de temporal para el valor del índice y esto lo hacemos con el objetivo de sincronizar este valor con el aumento del índice de la lista, ya que cuando se ejecuta la línea 19 la variable node ya no se encuentra apuntando al primer elemento de la lista y por ende el índice pasó de 0 a 1 y así van evolucionando ambos valores, mientras el índice de la lista aumenta, el valor de i disminuye  hasta llegar a 0, momento donde se retorna el nodo asociado o nil en caso de que se haya llegado al final de la lista.

En la siguiente tabla se puede visualizar mejor el proceso. Hemos asumido que el valor inicial de index es 3 y como node es igual a head pues su valor inicial es 0:

VariablesValores InicialesFin Primer CicloFin Segundo CicloFin Tercer CicloInicio Cuarto Ciclo
i3210i == 0
node0123return node

Llegado el inicio del cuarto ciclo y final, la variable i es igual a 0 y acto seguido se ejecuta la línea 13 donde retornamos el nodo asociado al índice 3.

Para comprobar que nuestra función trabaja de la manera que hemos previsto, modifiquemos el siguiente código:

…agregándole la última línea. La salida en pantalla será:

La primera línea tiene el formato que habíamos creado sin embargo la segunda no. La razón es evidente, cuando trabajamos el formato de salida lo hicimos sobre la clase LinkedList y en la línea 10 estamos imprimiendo una instancia de Node. La solución es la que seguramente ya han imaginado, tenemos que extender la clase Node para que también adopte el protocolo CustomStringConvertible:

Cuando se vuelve a ejecutar todo el código, la salida en pantalla ya se muestra con el formato correcto:

Si ahora deseamos que nos devuelva el nodo correspondiente al indice 1:

…la salida cambia a la siguiente:

¿Pero que sucedería si pasamos un índice negativo?

Pues obtendríamos el siguiente mensaje de error:

…básicamente debido a que no podemos desempaquetar al valor nil. Una solución elegante y rápida para nuestro ejemplo pudiera ser el uso del operador de coalescencia nula:

…y la salida en pantalla sería:

En el siguiente artículo puedes aprender más sobre: el operador de coalescencia nula y los valores opcionales.

Eliminando Todos los Nodos

Otra funcionalidad que debe tener una lista enlazada es la posibilidad de poder remover todos los elementos que la conforman, una especie de reset que vacíe la lista y la vuelva a su estado inicial. En el siguiente código implementamos la función removeAll():

Como pueden ver es bastante simple de lograr, basta con igualar a nil tanto la cabeza como la cola de la lista. Podemos probarlo haciendo:

…la salida sería:

Ya la lista la tenemos vacía pero vamos a darle un pequeño ajuste para obtener una mejor salida en momentos como estos:

…y ahora la salida es:

Eliminando Nodos Individuales

Cuando se nos presenta la necesidad de eliminar nodos individuales nos vemos ante tres casos:

1 – Remover el primer nodo, en este caso tenemos que actualizar las referencias head y previous sobre el nodo siguiente.

Lista Enlazada - Eliminando Primero

2 – Remover un nodo dentro de la lista, en este caso tenemos que actualizar las referencias previous del nodo siguiente y next del nodo anterior.

Lista Enlazada - Eliminando Intermedio

3 – Remover al último nodo, en este caso tenemos que actualizar las referencias next y tail sobre el nodo anterior.

Lista Enlazada - Eliminando Último

Teniendo en cuenta esto, prosigamos a crear una nueva función de nombre remove:

…en la cual contemplaremos cada uno de estos casos tal y como hemos marcado en el código mediante comentarios. Lo primero que hacemos es verificar que la lista no este vacía ya que no tiene sentido eliminar algo cuando no hay nada, lo segundo es asegurarnos de que el nodo pasado como parámetro es válido y en cualquiera de estos dos casos retornamos un mensaje de error correspondiente. El resto del código creo que se explica mejor con las imágenes asociadas a cada caso en la lista de arriba no obstante si tiene alguna duda en los comentarios la pueden dejar y con gusto la respondo. Por último en las líneas 44 y 45 las referencias que atan a nuestro nodo con la lista se liberan igualándolas a nil, luego al no haber más referencias a esta posición de memoria pues ARC toma el control y la libera.

En el siguiente tutorial podrás profundizar más sobre: ARC (Automatic Reference Counting) y la gestión de memoria.

Genéricos

Hasta ahora hemos implementado una lista con soporte solamente para valores de tipo String y esto nos limita grandemente por razones más que evidentes. La solución reside en el uso de código genérico, veamos:

Como ya sabemos la clase Node se encarga de almacenar los valores de nuestra lista, fungiendo como los eslabones de una cadena y al mismo tiempo como las cabinas de un teleférico que solamente permite montar solamente a mujeres, siendo estas últimas el tipo String al que hemos dado soporte hasta ahora. En la nueva versión de Node ya podemos manejar todo tipo de valores, es decir las cabinas ya permiten montar junto a las mujeres todo tipo de personas y animales: hombres, niños, perritos, gaticos… etc.

Lo siguiente es modificar la clase LinkedList ya que al trabajar internamente con la clase Node no se abstrae del tipo de datos que estamos almacenando:

En este punto ya nuestro código compila nuevamente y podemos tratar varios tipos de datos. Veamos un ejemplo:

La salida en pantalla de este código sería:

Si te preguntas por las extensiones pues no he hablado de ellas en este segmento debido a que no necesitamos modificarlas, el código que habíamos implementado es compatible con los cambios implementados.

No he explicado en detalles los últimos cambios de esta sección ya que es un tema que se ha abordado en otro artículos, si deseas aprender más te exhorto a que visites nuestro tutorial sobre el aprendizaje de genéricos en el lenguaje de programación Swift.

Resumen

Como muchas veces ocurre en el desarrollo de software, no existe un único método correcto para resolver un problema. Una estructura de lista enlazada puede trabajar bien en un caso pero causar problemas en otros. En general, el beneficio de las listas enlazadas se incrementa cuando trabajamos con una colección dinámica en la cual añadimos y eliminamos nodos de manera frecuente y donde la localización de los nuevos elementos introducidos, importa.

Como ya hemos comentado esta estructura de datos es de las clásicas, una más de las tantas que como programadores necesitamos saber implementar o mejor aún, entender la tesis detrás de su puesta en práctica, comprendiendo la teoría, seremos capaces de implementarla, no solamente en Swift, sino en cualquier otro lenguaje. En KodigoSwift hemos abordado varias estructuras de datos, igual de importantes, que te invitamos a conocer en la sección de algoritmos de programación en Swift.

Espero que todo cuanto se ha dicho aquí, de una forma u otra le haya servido de aprendizaje, de referencia, que haya valido su preciado tiempo.

Este artículo, al igual que el resto, será revisado con cierta frecuencia en pos de mantener un contenido de calidad y actualizado.

Cualquier sugerencia, ya sea errores a corregir, información o ejemplos a añadir será, más que bienvenida, necesaria!

Acerca de Josué V. Herrera

Ciudadano del mundo. Me gustan mucho los animales y la naturaleza, la literatura, la música y el cine, aficionado a la aviación y a todo lo que es tecnología y ciencia. Desde el 2005 me dedico de manera profesional a la informática, trabajando principalmente como administrador de redes y sistemas aunque también he fungido como programador, especializándome en Linux y en C++ / Qt. Soy Experto en Administración y Seguridad de Redes por la Universidad Tecnológica Nacional FRVM de Argentina. Desde el 2014 me dedico al estudio de Swift y el entorno que lo rodea, ya sea desde el lado de Apple como del Open Source.

Ver Todos