Estructuras de datos listas

-------------------------------------------------
I. Introducción

El objetivo de este artículo es la comprensión de las listas doblemente enlazadas. 
Las listas doblemente enlazadas pueden ser utilizadas cuando son necesarias varias operaciones de inserción o eliminación de elementos. 

-------------------------------------------------
II. Definición

Las listas doblementeenlazadas son estructuras de datos semejantes a las listas enlazadas simples. 
La asignación de memoria es hecha al momento de la ejecución. 

En cambio, en relación a la listas enlazada simple el enlace entre los elementos se hace gracias a dos punteros (uno que apunta hacia el elemento anterior y otro que apunta hacia el elemento siguiente). 

El puntero anterior del primer elemento debeapuntar hacia NULL (el inicio de la lista). 
El puntero siguiente del último elemento debe apuntar hacia NULL (el fin de la lista). 

Para acceder a un elemento, la lista puede ser recorrida en ambos sentidos:
* comenzando por el inicio, el puntero siguiente permite el desplazamiento hacia el próximo elemento.
* comenzando por el final, el puntero anterior permite el desplazamientohacia el elemento anterior.

Resumiendo, el desplazamiento se hace en ambas direcciones, del primer al ultimo elemento y/o del ultimo al primer elemento. 

-------------------------------------------------
III. La construcción del modelo de un elemento de la lista

Para definir un elemento de la lista será utilizado el tipo struct. 
El elemento de la lista contendrá: un campo dato, unpuntero anterior y un puntero siguiente. 

Los punteros anterior y siguiente deben ser del mismo tipo que el elemento, en caso contrario no podrán apuntar hacia un elemento de la lista. 
El puntero anterior permitirá el acceso hacia el elemento anterior mientras que el puntero siguientepermitirá el acceso hacia el próximo elemento. 

typedef struct dl_ElementoLista {char *dato;
struct dl_ElementoLista *anterior;
struct dl_ElementoLista *siguiente;
}dl_Elemento;

Para tener el control de la lista es preferible conservar algunos elementos: el primer elemento, el último elemento, el número de elementos. 

Para ello, será utilizada otra estructura (no es obligatorio, pueden serutilizadas variables). 

typedef struct dl_ListaIdentificacion {
dl_Elemento *inicio;
dl_Elemento *fin;
int tamaño;
}dl_Lista;

El puntero inicio contendrá la dirección del primer elemento de la lista. 
El puntero fin contendrá la dirección del último elemento de la lista. 
La variable tamaño contiene elnúmero de elementos. 

Cualquiera que sea la posición en la lista, los punteros inicio y fin apuntan siempre al primer y último elemento. 
El campo tamaño contendrá el numero de elementos de la lista cualquiera que sea la operación efectuada sobre la lista. 

-------------------------------------------------
IV. Operaciones sobre la lista doblemente enlazadas

Para la inserción y laeliminación, una solo función bastará si está bien concebida en función de las necesidades. 
Sin embargo, debo recordar que este artículo es puramente didáctico. 
Por esta razón he escrito una función para cada operación de inserción y eliminación. 

-------------------------------------------------
A. Inicialización

Modelo de la función: 

void inicialización (Lista*lista);

Esta operación debe ser hecha antes de cualquier otra operación sobre la lista. 
Esta inicializa el puntero inicio y el puntero fin con el puntero NULL, y el tamaño con el valor 0. 

La función 

void inicialización (Liste *liste){
lista->inicio = NULL;
lista->fin = NULL;
tamaño = 0;
}...