Implementando una lista doblemente ligada en Python.
Implementando una lista doblemente ligada en Python.
Introducción.
Durante este artículo te vamos a enseñar como implementar una lista doblemente ligada en Python.
Python es un lenguaje de programación interpretado cuya filosofía hace hincapié en la legibilidad de su código. Se trata de un lenguaje de programación multiparadigma, ya que soporta orientación a objetos, programación imperativa y, en menor medida, programación funcional. Es un lenguaje interpretado, dinámico y multiplataforma.
Una lista doblemente enlazada es una lista lineal en la que cada nodo tiene dos enlaces, uno al nodo siguiente, y otro al anterior.
Las listas doblemente enlazadas no necesitan un nodo especial para acceder a ellas, pueden recorrerse en ambos sentidos a partir de cualquier nodo, esto es porque a partir de cualquier nodo, siempre es posible alcanzar cualquier nodo de la lista, hasta que se llega a uno de los extremos.
A continuación, te vamos a explicar cómo hacerlo paso a paso. En este artículo encontraras una breve introducción a las funciones y dentro de las imágenes del código te explicamos paso a paso porque se toman todas las decisiones.
El Autor del código original de este artículo es de Usman Malik, el cual puedes encontrar en las referencias de este artículo, este es un artículo similar, pero en español y explicado a detalle que hace cada una de las partes del código. Además, para complementar agregamos algunas funciones y para la función de invertir añadimos un diagrama explicando cómo se vería visualmente la inversión de una lista doblemente ligada.
Pros y contras de una lista doblemente ligada en Python.
Pros
A diferencia de una lista ligada, la lista doblemente ligada se puede navegar y ser analizada en ambas direcciones. La referencia al siguiente nodo ayuda a que nos podamos mover hacia adelante y la referencia al nodo anterior nos ayuda a movernos en dirección contraria.
Las operaciones básicas como agregar elemento y eliminar son fáciles de implementar y el poder navegar en dos direcciones facilita este hecho.
Contras
Utilizan mas memoria que los arreglos debido al almacenamiento utilizado por sus apuntadores
Las dificultades surgen en las listas enlazadas cuando se trata de invertir el desplazamiento. Por ejemplo, las listas enlazadas individualmente son incómodas para navegar hacia atrás y mientras que las listas enlazadas doblemente son algo más fáciles de leer, la memoria se desperdicia en la asignación de espacio para un puntero hacia atrás.
Constructor del nodo.
Que es un nodo:
El nodo es un elemento de la lista el cual contiene: el elemento que queremos guardar, una referencia hacia el nodo anterior y una referencia al nodo siguiente.
Comenzaremos con construir un nodo utilizando una clase class Nodo: el constructor toma de valores a self y a elemento el cual será el elemento que se encuentre dentro del nodo, además, podemos ver que se encuentran otros dos atributos los cuales nos van a indicar las conexiones entre los nodos. Inicializamos siguiente y anterior a None ya al crear un Nodo queremos que no apunten a ningún otro nodo. Y por último tenemos al atributo elemento el cual será el dato que vamos a guardar en el nodo.
Constructor de la lista doblemente ligada.
A continuación, crearemos una clase para la lista doblemente ligada class doubleList: la cual contiene únicamente el nodo inicial o el root de la lista el cual le da un inicio a la lista. Inicializamos root hacia None ya que al crear una lista queremos que este vacía. Durante el artículo crearemos varios métodos para interactuar con la lista, asegúrate de agregar esos métodos a esta clase.
¿Como se ve una lista cuyo root apunta al nodo?
La lista doblemente ligada inicia siempre con un root el cual va a apuntar al primer nodo de la lista.
Funciones para insertar un elemento a la lista doblemente ligada.
Insertando un elemento a una lista doblemente ligada vacía.
Para esta función tomaremos como parámetro a self y dato. Dato será el valor que va a tomar el elemento del nodo que vamos a insertar. Nuestra primera función será la siguiente: la cual va a recibir como parámetro a self y a dato el cual será el elemento que queremos guardar en el nodo. Al insertar nuestro primer elemento a la lista primero queremos revisar que la lista este vacía, si esta vacía vamos a crear el primer nodo y pasaremos como parámetro el dato de la clase. En caso contrario vamos a desplegar un mensaje al usuario de que la lista no está vacía.
Insertando un elemento a una lista doblemente ligada al inicio.
Para esta función tomaremos como parámetro a self y dato. Dato será el valor que va a tomar el elemento del nodo que vamos a insertar. Al igual que nuestra primera función y en las siguientes funciones primero tenemos que revisar que la lista este vacía, si está vacía ahora podemos utilizar la función que creamos anteriormente para agregar el nodo que queremos. En caso contrario tenemos que hacer algunos ajustes a las referencias de los nodos los cuales explicamos a continuación paso a paso:
Insertando un elemento a una lista doblemente ligada al final.
Insertar un elemento a la lista al final es muy similar al de agregar al inicio, la diferencia es que ahora tenemos que encontrar el ultimo nodo de la lista para referenciarlo con nuestro nuevo nodo. Para esto utilizaremos un apuntador de apoyo para movernos a través de la lista sin modificarla. Te explicamos como hacerlo paso a paso a continuación:
Insertando un elemento a una lista doblemente ligada después de un elemento.
Nuestra función tomara como parámetros a self, x, dato. X representara el elemento que estamos buscando mientras que dato será el valor que tomara el elemento del nodo que vamos a insertar. En este caso vamos a tener que navegar la lista hasta encontrar el elemento que estamos buscando para después insertaremos el nodo después de este elemento, para esto utilizaremos otro apuntador de apoyo para movernos y encontrar el elemento el cual asignaremos después de encontrar el elemento buscado. A continuación, te explicamos paso a paso como implementar la función.
Insertando un elemento a una lista doblemente ligada antes de un elemento.
Nuestra función tomara como parámetros a self, x, dato. X representara el elemento que estamos buscando mientras que dato será el valor tomara el elemento del nodo que vamos a insertar. Para esta función es un proceso muy similar al anterior, el único cambio es que en lugar de asignar el apuntador al nodo que esta antes del elemento que buscamos lo referenciaremos al nodo anterior del elemento buscado.
Función para imprimir la lista doblemente ligada.
Para esta función, queremos visitar todos los nodos de la lista. Esto para poder revisar las pruebas finales que haremos en este artículo las cuales nos van a indicar que todas las funciones están funcionando adecuadamente.
Función para determinar si está vacía la lista doblemente ligada.
Para esta función utilizaremos la misma metodología que hemos estado implementando anteriormente para revisar si la lista esta vacía, con la excepción de que ahora regresaremos True o False dependiendo de la situación.
Función para contar el numero de elementos en la lista doblemente ligadas.
De manera similar a la función de navegar la lista vamos a recorrer toda la lista y sumaremos a la cuenta el numero de elementos que existen en la misma.
Eliminando elementos de una lista doblemente ligada.
Eliminando un elemento al inicio de una lista doblemente ligada.
Eliminar un elemento de la lista consiste en primordialmente ajustar las referencias para que el nodo deje de existir dentro de nuestra lista, en este caso eliminaremos el primero nodo el cual también es el root de la lista por lo cual tenemos que volver a asignar una vez eliminado el nodo. Tenemos que considerar el caso en el cual solo exista un solo nodo en la lista. A continuación, te explicamos como implementar esta función.
Eliminando un elemento al final de una lista doblemente ligada.
Similarmente al caso anterior, con la excepción de que ahora navegaremos la lista hasta el final y eliminaremos el ultimo nodo, para este caso tenemos que volver a considerar el caso de que solo tengamos un solo elemento de la lista.
Eliminando un elemento de una lista doblemente ligada buscando por valor.
Esta es una de las funciones mas complicadas ya que tenemos que ajustar las referencias del nodo anterior y posterior del cual queremos eliminar para conseguir eliminar ese nodo y mantener la lista con el orden original. A continuación, te explicamos en el código paso a paso como implementar esto y porque se toman las decisiones.
Invirtiendo una lista doblemente ligada.
Invertir una lista doblemente ligada es una de las partes más confusas de este tipo de estructura de datos. Por lo que aparte del código te daremos una serie de pasos y un diagrama con el cual esperamos explicar un poco más a fondo que esta ocurriendo con la lista.
1. Utilizaremos dos apuntadores de apoyo para movernos a través de la lista y lo que vamos a invertir no es el orden, si no las referencias de los nodos. Un apuntador p apuntara al primer nodo y un apuntador q apuntara al segundo nodo.
2. El primer paso es referenciar el apuntador siguiente del primer nodo a None ya que este se convertirá en el último nodo y el apuntador anterior al segundo nodo ya que este se convertirá en el penúltimo nodo.
3. Una vez estableciendo estas bases utilizaremos un ciclo while para invertir las referencias de q y para movernos un lugar a la derecha de la lista.
4. En este punto comenzamos a invertir las referencias del nodo q, el anterior de q ahora será el siguiente de q y el siguiente ahora será p el cual es el anterior.
5. Después de esto nos movemos a la derecha de la lista y repetimos el proceso.
6. Al terminar todas las referencias ahora referenciamos a root al ultimo nodo de la lista el cual será ahora el primer nodo.
Test de las diferentes funcionalidades.
A continuación, te vamos a guiar por una serie de pruebas para revisar que las funciones estén funcionando de manera adecuada. La manera en la que funciona es que vamos a probar todas las funciones, desde crear una lista hasta invertirla.
La manera en la que esto va a funcionar es que te daremos los resultados finales y los tienes que comparar con los tuyos para comprobar que esté funcionando.
Pruebas(inputs)
Resultados(outputs)
Comparación del código de algunas funciones con c++
En esta sección vamos a comparar algunas de las funciones mas interesantes de la misma estructura en dos lenguajes de programación. Esto con el fin de comparar la complejidad y legibilidad de ambos códigos.
Conclusión.
En conclusión, una lista doblemente ligada a pesar de utilizar mas memoria que otras estructuras, nos permite cierta libertad para alterar los componentes de esta. Una de las funciones mas notorias es el hecho de poder invertir la lista de manera eficiente, aun siendo un proceso complejo de entender, una vez comprendido es fácil de implementar.
En este artículo se revisaron las funciones principales y sus componentes, así como una serie de pruebas que permiten la revisión de estos.
Esperamos poder haber ayudado a alguien a crear su primera lista doblemente ligada y que les sea de utilidad para estructurar los datos de sus proyectos.
Referencias.
Malik, U. (2020). Doubly Linked List with Python Examples. Stack Abuse. https://stackabuse.com/doubly-linked-list-with-python-examples/
Colaboradores de Wikipedia. (2020, 19 noviembre). Python. Wikipedia, la enciclopedia libre. https://es.wikipedia.org/wiki/Python
Colaboradores de Wikipedia. (2020, 6 marzo). Lista doblemente enlazada. Wikipedia, la enciclopedia libre. https://es.wikipedia.org/wiki/Lista_doblemente_enlazada
Estructuras de datos — Listas doblemente enlazadas. (2017). C.onclase. http://c.conclase.net/edd/?cap=005#:%7E:text=Una%20lista%20doblemente%20enlazada%20es,siguiente%2C%20y%20otro%20al%20anterior.
