Listas doblemente enlazadas



LISTAS DOBLEMENTE ENLAZADA

En las listas doblemente enlazadas, cada elemento contiene dos punteros aparte del valor almacenado en el elemento. Un puntero apunta al siguiente elemento de la listay el otro puntero apunta al elemento anterior. La figura 18.6. muestra una lista doblemente enlazada y un nodo de dicha lista.



Existe una operación de insertar y eliminar (borrar) en cadadirección. La figura 18.7. muestra el problema de insertar un nodo p a la derecha del nodo actual. Deben asignarse cuatro nuevos enlaces




En el caso de eliminar (borrar) un nodo de una lista doblementeenlazada es preciso cambiar dos punteros.


Declaración de una lista doblemente enlazada
Una lista doblemente enlazada con valores de tipo int necesita dos punteros y el valor del campo datos. En unaestructura se agrupan estos datos del modo siguiente:
typedef int Item;
struct unnodo
{
Item dato;
struct unnodo *adelante;
struct unnodo *atras;
};
typedef struct unnodo Nodo;
Insertar un elementoen una lista doblemente enlazada
El algoritmo empleado para añadir o insertar un elemento en una lista doble varía dependiendo de la posición en que se desea insertar el elemento. La posición deinserción puede ser:
En la cabeza (elemento primero) de la lista.
En el final de la lista (elemento último).
Antes de un elemento especificado.
Después de un elemento especificado.

Insertar un nuevoelemento en la cabeza de una lista doble
El proceso de inserción se puede resumir en este algoritmo:
Asignar un nuevo nodo apuntado por nuevo que es una variable puntero que apunta al nuevo nodo que se vaa insertar en la lista doble.
Situar el nuevo elemento en el campo dato del nuevo nodo.
Hacer que el campo enlace adelante del nuevo nodo apunte a la cabeza (primer nodo) de la lista original, y queel campo enlace atras del nodo cabeza apunte al nuevo nodo.
Hacer que cabeza (puntero cabeza) apunte al nuevo nodo que se ha creado.


CODIGO C

En este momento, la función de insertar un elemento...