Listas doblemente vinculadas y cómo implementarlas en Python 3

Las listas enlazadas son una forma lineal de almacenar datos. Se compone de nodos que contienen datos, así como punteros con cómo llegar a la siguiente pieza de datos. Piense en los nodos como miembros de una cadena. Cada cadena depende la una de la otra para mantener un vínculo fuerte. Si, por ejemplo, al enlace del medio le falta todo, después de eso falla. ¡Ya no es una cadena completa! ¿Cómo se traduce esto en listas vinculadas? Si falta uno de los punteros o es incorrecto, el resto de los datos ya no podrán leerse.

¡No es una cadena válida! ¡Esto rompería una lista vinculada!

Sin embargo, el tema de este artículo es sobre una versión más versátil de las listas vinculadas: la lista doblemente vinculada. En comparación con una lista vinculada normal (o individualmente), una lista doblemente vinculada incluye otro puntero llamado anterior. Como puede suponer, esto le permite al nodo saber dónde está el nodo anterior. En comparación, una lista vinculada individualmente tendría que atravesar la lista completa nuevamente hasta el punto anterior para llegar al mismo punto.

Para obtener información sobre listas enlazadas individualmente, visite el artículo de mi compañero de clase:

Como se mencionó anteriormente, los nodos apuntan a otras ubicaciones en la memoria. Qué significa eso? Bueno, a diferencia de las matrices que se almacenan en ubicaciones contiguas, las listas vinculadas simplemente tienen punteros. En el diagrama debajo de cada bloque de memoria (rojo) tiene dos punteros que apuntan a él. Accede a esa información mirando el siguiente puntero (negro). Si quiere encontrar el bloque anterior, verá el puntero anterior (blanco).

Entonces, ¿cómo se implementa una lista doblemente vinculada? "Así es como en Python 3

Simplemente agregue un .prev a su clase Node. ¡Ahora estás listo para comenzar a implementar!

Ventajas - ¡Con código Python 3!

¿Cuáles son algunas de las ventajas de una lista doblemente vinculada sobre una lista individualmente vinculada? Bueno, con una lista doblemente enlazada, puede moverse hacia adelante y hacia atrás entre sus nodos. Esto hace que cosas como la inserción sean realmente fáciles. Con listas doblemente vinculadas, simplemente recorre su lista vinculada al nodo que desea y luego llama al nodo anterior.

Desventajas

Si bien hay grandes cosas acerca de las listas vinculadas, no es una solución completa. Al igual que con muchas estructuras de datos y algoritmos, esta debería ser una herramienta en su arsenal. Una de las desventajas sobre una lista vinculada individualmente es que hay más consumo de memoria ya que cada enlace en una lista doblemente vinculada necesita hacer un seguimiento de ese puntero anterior. Además, es difícil hacer un seguimiento de dicho puntero.

De hecho, todavía estoy en el proceso de practicar su implementación. Esta habrá sido mi segunda implementación exitosa a partir de la redacción de este artículo (abril de 2019). Cada vez se vuelve un poco más fácil, pero aún necesito dibujar diagramas de cómo interactúa el puntero anterior con todas mis otras funciones.

¿Pero para qué se usaría esto?

Te escucho preguntar. Piensa en cualquier momento que hayas visto un anterior y el siguiente. Hay algunas formas obvias y sutiles de implementarlas.

Fuente: https://pbs.twimg.com/media/DxzXvUKXgAAvmxx.jpg

¿Qué pasa en un caso como un reproductor de música? Tiene un botón siguiente y anterior muy explícito. Se podría usar una lista doblemente vinculada para alternar entre esas dos canciones.

¿O qué tal un navegador? Estos también tienen formas explícitas de retroceder y avanzar entre las páginas web que visitó.

Ahora piense en su software de procesamiento de texto o editor de fotos de su elección. Cada vez que comete un error, puede presionar CTRL (CMD para Mac) + Z para deshacer esa última acción. Del mismo modo, puede rehacer lo que ha deshecho con CTRL (CMD para Mac) + Y. Ahora, ¿por qué le suena familiar? ¡También podría implementarse con una lista doblemente vinculada! El puntero anterior apunta a acciones que se realizaron mientras que también puede rehacer las acciones si deshace demasiado.

Fuente: https://gfycat.com/brilliantbeautifuldassieFuente: https://www.solitairecardgames.com/how-to-play-solitaire

Una implementación menos obvia en la que pensé fue en el juego Solitario. Al lado hay una imagen de terminologías de Solitario para ayudar a ilustrar mi punto.

El juego es un ejemplo brillante en el que constantemente necesitas poder ver las cartas anteriores y siguientes, ya sea en el cuadro o en la pila de desechos. A medida que juegas una carta desde la pila de residuos hasta el cuadro, la pila de residuos se actualiza con la carta anterior.

Para una discusión más animada de los usos en listas doblemente vinculadas, recomiendo echar un vistazo a esta discusión en stackoverflow:

Entonces, la próxima vez que implemente una lista vinculada, ¿por qué no prueba una lista doblemente vinculada? ¡No es mucho más código en la parte superior de una lista vinculada y hay grandes beneficios!

Recursos adicionales

Puede encontrar un enlace completo a mi implementación de Python 3 de una lista doblemente vinculada en mi repositorio de Github.

Si desea una cadena imprimible en 3D de listas doblemente enlazadas, la he subido a Thingiverse.

https://www.geeksforgeeks.org/doubly-linked-list/

https://www.tutorialspoint.com/data_structures_algorithms/doubly_linked_list_algorithm.htm

https://www.youtube.com/watch?v=JdQeNxWCguQ