ASIGNACIÓN DINÁMICA: LISTAS DOBLEMENTE ENLAZADAS






Concepto de lista doblemente enlazada.
Si disponemos de nodos dotados de dos campos de enlace, podemos emplearlos para construir lo que se denomina una lista doblemente enlazada. Estas listas se caracterizan porque cada nodo contiene la dirección del nodo siguiente dentro de la lista, y la dirección del nodo anterior dentro de la misma.

El primer nodo de la lista tiene el valor NULL en el campo que señalaría el nodo anterior; de este modo, es posible reconocerlo.

Resulta cómodo disponer de un puntero que señale a este nodo. Téngase en cuenta la necesidad de actualizarlo cuando se realicen acciones que exigan cambiar su valor para mantener la integridad de la lista.
El último nodo de la lista contiene el valor NULL en el campo que señalaría el nodo siguiente. Esto permite reconocerlo, aunque también es frecuente emplear un puntero de nodo final con esta intención.

Resulta cómodo disponer de un puntero que señale a este nodo. Téngase en cuenta la necesidad de actualizarlo cuando se realicen acciones que exigan cambiar su valor para mantener la integridad de la lista.
El resultado final es una lista doblemente enlazada, que presenta un aspecto similar al que puede verse en la figura.La característica más sobresaliente de este tipo de estructura no lineal es que cada nodo contiene la información necesaria para acceder tanto al elemento anterior como al elemento siguiente. El mayor coste de memoria se ve compensado ampliamente por la gran facilidad que ofrecen estas estructuras a la hora de añadir y eliminar nodos, al contrario de lo que sucede en las listas simplemente enlazadas. Inserción y eliminación de nodos.
Este proceso es completamente análogo al estudiado en la sección anterior, relativa a listas simplemente enlazadas. De hecho, el manejo de listas doblemente enlazadas resulta más sencillo, puesto que basta localizar un nodo para poder eliminarlo, o añadir un nodo delante o detrás de él, al contar en todo momento con la dirección del nodo anterior.
Proceso de inserción
Las imágenes siguientes describen la situación de una lista doblemente enlazada al realizar distintas operaciones.

Inserción de un nodo al principio de la lista

Como puede observarse, el puntero de nodo siguiente del nuevo nodo pasa a tomar el valor de ppio; el puntero de nodo anterior del nodo señalado por ppio deja de ser NULL y pasa a apuntar al nuevo nodo; finalmente, ppio pasa a apuntar al nuevo nodo.

Inserción de un nodo al final de la lista

En este caso, es preciso hacer que el puntero de nodo siguiente del nodo señalado por fin apunte al nuevo nodo. A continuación, se hace que el puntero de nodo anterior del nodo nuevo apunte al nodo señalado por fin. Por último, se hace que fin apunte al nuevo nodo.

Inserción de un nodo en posición intermedia .


La inserción en posición intermedia se hace a partir del puntero del nodo tras el cual se quiere insertar. El manejo de punteros es como sigue:
  1. El nodo nuevo debe apuntar al nodo siguiente.
  2. El nodo siguiente debe apuntar al nodo nuevo.
  3. El nodo anterior debe apuntar al nodo nuevo.
  4. El nodo nuevo debe apuntar al nodo anterior.
Se observará la mayor comodidad al disponer del puntero de nodo anterior y de nodo siguiente.

Proceso de eliminación
De nuevo se trata de un proceso análogo al empleado para eliminar nodos en una lista simplemente enlazada. El proceso se ve complicado ligeramente por la presencia de un mayor número de punteros, pero se trata de un mayor número de operaciones, no de una tarea más difícil. Comenzaremos por la

Eliminación de un nodo en posición inicial


Si hay un solo nodo, la tarea se reduce a eliminar el nodo y hacer que ppio y fin tomen el valor NULL . Si hay más de un nodo, se hace que fin tome el valor fin->sig y después se hace que fin->sig->ant tome el valor NULL , para mantener la integridad de la lista.

Eliminación de un nodo en posición final


Este procedimiento es sencillo al contar con el puntero del penúltimo nodo, o con el del último. En todo caso, se hace que fin apunte al penúltimo nodo y después se libera la memoria del último nodo. Por último, se da el valor NULL al puntero sig del nodo señalado por fin . De este modo se mantiene la integridad de la lista.

Eliminación de un nodo en posición intermedia


En este caso contamos con el puntero eliminado , que señala el nodo que se quiere suprimir. Basta con hacer que eliminado->sig->ant = eliminado->and , y eliminado->ant->sig = eliminado->sig . Luego se puede liberar eliminado .

Ejercicios propuestos



En los ejercicios de esta sección se van a emplear las declaraciones siguientes: 

struct Nodo {
 int dato;
 struct Nodo * ant;
 struct Nodo * sig;
};

struct Lista {
	struct Nodo * ppio;
	struct Nodo * fin;
};


  1. Ejercicio 1104r01.- Construir una función que admita como argumentos un puntero de Lista y otro de Nodo . Supuesta vacía la lista, la función debe insertar en ella el nodo proporcionado.

  2. Ejercicio 1104r02.- Construir una función que admita como argumentos un puntero de Lista y otro de Nodo . Suponiendo que la lista no esté vacía, construir una función adecuada para insertar el nodo proporcionado como primer elemento de la misma.

  3. Ejercicio 1104r03.- Construir una función que admita como argumentos un puntero de Lista y otro de Nodo . Suponiendo que la lista no esté vacía, construir una función adecuada para insertar el nodo proporcionado como último elemento de la lista.

  4. Ejercicio 1104r04.- Construir una función que admita como argumentos un puntero de Lista y otro de Nodo . Suponiendo que la lista tenga dos o más elementos, construir una función adecuada para insertar el nodo en la lista, supuesta ordenada.

  5. Ejercicio 1104r05.- Construir una función que elimine el primer nodo de una lista doblemente enlazada.

  6. Ejercicio 1104r06.- Construir una función que elimine el último nodo de lista doblemente enlazada.

  7. Ejercicio 1104r07.- Construir una función que elimine un nodo dado (en posición intermedia) de una lista doblemente enlazada.

  8. Ejercicio 1104r08.- Construir un programa adecuado para manejar listas doblemente enlazadas, basado en las funciones anteriores.

  9. Ejercicio 1104r09.- Se dispone de un archivo binario formado por registros de estructura conocida. Se pide construir un programa que maneje la base de datos, empleando para ello una lista doblemente enlazada.