Listas Doblemente Enlazadas: Una Guía Completa

Listas Doblemente Enlazadas

Todas las listas que hemos estudiado hasta ahora son unidireccionales, lo que significa que es posible moverse fácilmente de un nodo a su sucesor. Sin embargo, en muchas aplicaciones, algunas operaciones requieren desplazarse de un nodo a su predecesor.

Las listas bidireccionales pueden construirse fácilmente con nodos que contengan, además de una parte de datos, dos enlaces: un enlace siguiente que apunte al sucesor del nodo y un enlace previo que apunte a su predecesor:

Predecesor
9
Sucesor
17
22
26
34
?
9
?
dato

Una lista enlazada construida a partir de tales nodos se llama normalmente lista doblemente enlazada (o enlazada simétricamente). Para facilitar el recorrido tanto hacia delante como hacia atrás, un puntero (primero) ofrece acceso al primer nodo y otro puntero (último) ofrece acceso al último nodo. Por ejemplo, una lista doblemente enlazada con los enteros 9, 17, 22, 26, 34 podría dibujarse como sigue:

Como en el caso de las listas enlazadas simples, utilizar nodos de cabeza para listas doblemente enlazadas elimina algunos casos especiales (por ejemplo, la lista vacía y el primer nodo) y hacer que las listas sean circulares facilita recorrerlas de manera circular.

Los algoritmos para las operaciones básicas sobre listas son parecidos a los de las listas enlazadas simples, con la diferencia de que es necesario establecer algunos enlaces adicionales. Por ejemplo, insertar un nuevo nodo en una lista doblemente enlazada requiere establecer sus enlaces siguiente y previo para que apunten respectivamente a su sucesor y a su predecesor:

puntpred
puntnuevo -> previo = puntpred;
puntnuevo -> siguiente = puntpred -> siguiente;


y a continuación, reenlazar el enlace siguiente de su predecesor y el enlace previo de su sucesor para que apunten a este nuevo nodo:

puntpred
puntpred -> siguiente -> previo = puntnuevo;
puntpred -> siguiente = puntnuevo
puntnuevo

Es importante que los cambios en los enlaces se hagan en el orden correcto.

Se puede borrar un nodo simplemente reenlazando el enlace que apunta hacia delante de su predecesor y el que apunta hacia atrás de su sucesor para saltar sobre el nodo.

Los recorridos se realizan de la misma manera que para las listas enlazadas simples. Los recorridos hacia delante siguen los enlaces siguiente y los recorridos hacia atrás siguen los enlaces previo. Los constructores, destructores, constructores de copia, asignaciones y otras operaciones son también modificaciones inmediatas de aquellos para las listas enlazadas simples.

Caso de Estudio: Aritmética de Grandes Números