Tercera unidad

LISTAS

LISTAS DOBLEMENTE ENLAZADAS
Son listas que tienen un enlace con el elemento siguiente y con el anterior. Una ventaja que tienen es que pueden recorrerse en ambos sentidos, ya sea para efectuar una operación con cada elemento o para insertar/actualizar y borrar. La otra ventaja es que las búsquedas son algo más rápidas puesto que no hace falta hacer referencia al elemento anterior. Suinconveniente es que ocupan más memoria por nodo que una lista simple. Se realizará una implementación de lista ordenada con doble enlace que aproveche el uso de la cabecera y el centinela. A continuación se muestra un gráfico que muestra una lista doblemente enlazada con cabecera y centinela, para lo que se utiliza un único nodo que haga las veces de cabecera y centinela.

- Declaración:
structlistaDE
{
int clave;
struct listaDE *ant,
*sig;
};

- Procedimiento de creación:
void crearDE(struct listaDE **LDE)
{
*LDE = (struct listaDE *) malloc(sizeof(struct listaDE));
(*LDE)->sig = (*LDE)->ant = *LDE;
}

- Procedimiento de inserción:
void insertarDE(struct listaDE *LDE, int elem)
{
struct listaDE *actual, *nuevo;

/* busca */actual = LDE->sig;
LDE->clave = elem;
while (actual->clave < elem)
actual = actual->sig;

/* crea */
nuevo = (struct listaDE *) malloc(sizeof(struct listaDE));
nuevo->clave = elem;

/* enlaza */
actual->ant->sig = nuevo;
nuevo->ant = actual->ant;
nuevo->sig = actual;
actual->ant = nuevo;
}

- Procedimiento de borrado:
voidborrarDE(struct listaDE *LDE, int elem)
{
struct listaDE *actual;

/* busca */
actual = LDE->sig;
LDE->clave = elem;

while (actual->clave < elem)
actual = actual->sig;

/* borra */
if (actual != LDE && actual->clave == elem) {
actual->sig->ant = actual->ant;
actual->ant->sig = actual->sig;
free(actual);
}
}Para probarlo se pueden usar las siguientes instrucciones:
struct listaDE *LDE;
...
crearDE(&LDE);
insertarDE(LDE, 1);
borrarDE(LDE, 1);
 Una lista doblemente enlazada es una lista lineal en la que cada nodo tiene dos enlaces, uno al nodo siguiente, y otro al anterior. Las listas doblemente enlazadas no necesitan un nodo especial para acceder a ellas, pueden recorrerse en ambossentidos a partir de cualquier nodo, esto es porque a partir de cualquier nodo, siempre es posible alcanzar cualquier nodo de la lista, hasta que se llega a uno de los extremos. El nodo típico es el mismo que para construir las listas que hemos visto, salvo que tienen otro puntero al nodo anterior:
Struct nodo \{
Int dato;
Struct nodo *siguiente;Struct nodo *anterior;
};
Declaraciones de tipos para manejar listas doblemente enlazadas en C
Para C, y basándonos en la declaración de nodo que hemos visto más arriba, trabajaremos con los siguientes tipos:
Typedef struct _nodo \ {
Int dato;
Struct _nodo *siguiente;
Struct _nodo*anterior;
} Tipo Nodo;

Typedef tipo Nodo *pNodo;
Typedef tipo Nodo *Lista;
Tipo Nodo es el tipo para declarar nodos, evidentemente.
PNodo es el tipo para declarar punteros a un nodo.
Lista es el tipo para declarar listas abiertas doblemente enlazadas. También es posible, y potencialmente útil, crear listas doblemente enlazadasy circulares.
TIPOS DE LISTAS ENLAZADAS
Listas enlazadas lineales
* Listas simples enlazadas
La lista enlazada básica es la lista enlazada simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo en la lista, o al valor NULL o a la lista vacía, si es el último nodo.

Una lista enlazada simple contiene dos valores: el valor actual del nodo y un enlace al siguiente...