LISTAS DOBLEMENTE ENLAZADAS

1. INTRODUCCIÓN.

En algunas aplicaciones podemos desear recorrer la lista hacia adelante y hacia atrás, o dado un elemento, podemos desear conocer rápidamente los elementos anterior y siguiente. En tales situaciones podríamos desear darle a cada celda sobre una lista un puntero a las celdas siguiente y anterior en la lista tal y como se muestra en la figura.

Otra ventaja de las listas doblemente enlazadas es que podemos usar un puntero a la celda que contiene el i-ésimo elemento de una lista para representar la posición i, mejor que usar el puntero a la celda anterior aunque lógicamente, también es posible la implementación similar a la expuesta en las listas simples haciendo uso de la cabecera. El único precio que pagamos por estas características es la presencia de un puntero adicional en cada celda y consecuentemente procedimientos algo más largos para algunas de las operaciones básicas de listas. Si usamos punteros (mejor que cursores) podemos declarar celdas que consisten en un elemento y dos punteros a través de:

typedef struct celda{
	tipoelemento elemento;
   	struct celda *siguiente,*anterior;
}tipocelda;

typedef tipocelda *posicion;

Un procedimiento para borrar un elemento en la posición p en una lista doblemente enlazada es:

void borrar (posicion p)
{
   if (p->anterior != NULL)
	p->anterior->siguiente = p->siguiente;
   if (p->siguiente != NULL)
	p->siguiente->anterior = p->anterior;
   free(p);
}

El procedimiento anterior se expresa de forma gráfica en como muestra la figura:

Donde los trazos contínuos denotan la situación inicial y los punteados la final. El ejemplo visto se ajusta a la supresión de un elemento o celda de una lista situada en medio de la misma. Para obviar los problemas derivados de los elementos extremos (primero y último) es práctica común hacer que la cabecera de la lista doblemente enlazada sea una celda que efectivamente complete el círculo, es decir, el anterior a la celda de cabecera sea la última celda de la lista y la siguiente la primera. De esta manera no necesitamos chequear para NULL en el anterior procedimiento borrar.

Por consiguiente, podemos realizar una implementación de listas doblemente enlazadas con cabecera tal que tenga una estructura circular en el sentido de que dado un nodo y por medio de los punteros siguiente podemos volver hasta él como se puede observar en la figura (de forma analoga para anterior).

Es importante notar que aunque la estructura física de la lista puede hacer pensar que mediante la operación siguiente podemos alcanzar de nuevo un nodo de la lista, la estructura lógica es la de una lista y por lo tanto habrá una posición primero y una posición fin de forma que al aplicar una operación anterior o siguiente respectivamente sobre estas posiciones el resultado será un error.

Respecto a la forma en que trabajarán las funciones de la implementación que proponemos hay que hacer constar los siguientes puntos:

• La función de creación debe alojar memoria para la cabecera y hacer que los punteros siguiente y anterior apunten a ella, devolviendo un puntero a dicha cabecera.
  
  
• La función primero(l) devolverá un puntero al nodo siguiente a la cabecera.
  
  
• La función fin(l) devolvera un puntero al nodo cabecera.
  
  
• Trabajar con varias posiciones simultáneamente tendrá un comportamiento idéntico al de las listas enlazadas excepto respecto al problema referente al borrado cuando se utilizan posiciones consecutivas. Es posible implementar la función de borrado de tal forma que borrar un elemento de una posición p invalida el valor de dicha posición p y no afecta a ninguna otra posición. Nosotros en nuestra implementación final optaremos por pasar un puntero a la posición para el borrado de forma que la posición usada quede apuntando al elemento siguente que se va a borrar al igual que ocurría en el caso de las listas simples. Otra posible solución puede ser que la función devuelva la posición del elemento siguiente a ser borrado.
  
  
• La inserción se debe hacer a la izquierda del nodo apuntado por la posición ofrecida a la función insertar. Esto implica que al contrario que en las listas simples, al insertar un nodo, el puntero utilizado sigue apuntando al mismo elemento al que apuntaba y no al nuevo elemento insertado. Si se desea, es posible modificar la función de forma que se pase un puntero a la posición de inserción para poder modificarla y hacer que apunte al nuevo elemento insertado. En cualquier caso, el comportamiento final de la función deberá quedar reflejado en el conjunto de especificaciones del TDA.

2. OPERACIONES PRIMITIVAS DE LISTAS DOBLES.

Dentro del tipo abstracto de listas doblemente enlazadas podemos proponer las siguientes primitivas:

• tLista crear ()
• void destruir (tLista l)
• tPosicion primero (tLista l)
• tPosicion fin (tLista l)
• void insertar (tElemento x, tPosicion p, tLista l)
• void borrar (tPosicion *p, tLista l)
• tElemento elemento(tPosicion p, tLista l)
• tPosicion siguiente (tPosicion p, tLista l)
• tPosicion anterior (tPosicion p, tLista l)
• tPosicion posicion (tElemento x, tLista l)

ESPECIFICACIÓN SEMANTICA Y SINTACTICA.

• tLista crear ()
  Argumentos: Ninguno.
  Efecto: (Constructor primitivo). Crea un objeto del tipo tLista.
  
  
• void destruir (tLista l)
  Argumentos: Una lista.
  Efecto: Destruye el objeto l liberando los recursos que empleaba. Para volver a usarlo habrá que crearlo de nuevo.
  
  
• tPosicion primero (tLista l)
  Argumentos: Una lista.
  Efecto: Devuelve la posición del primer elemento de la lista.
  
  
• tPosicion fin (tLista l)
  Argumentos: Una lista.
  Efecto: Devuelve la posición posterior al último elemento de la lista.
  
  
• void insertar (tElemento x, tPosicion p, tLista l)
  Argumentos:

  l: Es modificada.
  p: Es una posición válida para la lista l.
  x: Dirección válida de un elemento del tipo T con que se instancia la lista, distinta de NULL.

  Efecto: Inserta elemento x en la posición p de la lista l desplazando todos los demás elementos en una posición.
  
  
• void borrar (tPosicion *p, tLista l)
  Argumentos:

  l: Es modificada.
  p: Es una posición válida para la lista l.

  Efecto: Elimina el elemento de la posición p de la lista l desplazando todos los demás elementos un una posición.
  
  
• tElemento elemento(tPosicion p, tLista l)
  Argumentos:

  l: Una lista.
  p: Es una posción válida de la lista l.

  Efecto: Devuelve el elemento que se encuentra en la posición p de la lista l.
  
  
• tPosicion siguiente (tPosicion p, tLista l)
  Argumentos:

  l: Una lista.
  p: Es una posición válida para la lista l, distinta de fin(l).

  Efecto: Devuelve la posición siguiente a p en l.
  
  
• tPosicion anterior (tPosicion p, tLista l)
  Argumentos:

  l: Una lista.
  p: Es una posición válida para la lista l, distinta de primero(l).

  Efecto: Devuelve la posición que precede a p en l.
  
  
• tPosicion posicion (tElemento x, tLista l)
  Argumentos:

  l: Una lista.
  x: Dirección válida de un elemento del tipo T con que se instancia la lista, distinta de NULL.

  Efecto: Si x se encuentra entre los elementos de la lista l, devuelve la posición de su primera ocurrencia. En otro caso, devuelve la posición fin(l).
  
  

3. EFICIENCIA.

Comparación de la eficiencia para las distintas implementaciones de las listas:

4. IMPLEMENTACIÓN DE LISTAS DOB. ENLAZADAS.

Una vez aclaradas las posibles ambigüedades y dudas que se pueden plantear, la implementación de las listas doblemente enlazadas quedaría como sigue:

typedef struct celda {
   tElemento elemento;
   struct celda *siguiente,*anterior;
} tipocelda;

typedef tipocelda *tPosicion;
typedef tipocelda *tLista;

static void error(char *cad)
{
   fprintf(stderr, "ERROR: %s\n", cad);
   exit(1);
}

tLista Crear()
{
   tLista l;
   
    	
    	
   

   l = (tLista)malloc(sizeof(tipocelda));
   if (l == NULL)
	Error("Memoria insuficiente.");
   l->siguiente = l->anterior = l;
   return l;
}

void Destruir (tLista l)
{
   tPosicion p;
   
    	
    	
   

   for (p=l, l->anterior->siguiente=NULL; l!=NULL; p=l) {
	l = l->siguiente;
	free(p);
   }
}   

tPosicion Primero (tLista l)
{
   
    	
    	
   
   return l->siguiente;
}

tPosicion Fin (tLista l)
{
   
    	
    	
   
   return l;
}

void Insertar (tElemento x, tPosicion p, tLista l)
{
   tPosicion nuevo;
   
    	
    	
   

   nuevo = (tPosicion)malloc(sizeof(tipocelda));
   if (nuevo == NULL) 
	Error("Memoria insuficiente.");
   nuevo->elemento = x;
   nuevo->siguiente = p;
   nuevo->anterior = p->anterior;
   p->anterior->siguiente = nuevo;
   p->anterior = nuevo;
}

void Borrar (tPosicion *p, tLista l)
{
   tPosicion q;
   
    	
    	
   
   if (*p == l){ 
	Error("Posicion fin(l)");
   }
   q = (*p)->siguiente;
   (*p)->anterior->siguiente = q;
   q->anterior = (*p)->anterior;
   free(*p);
   (*p) = q; 
}

tElemento elemento(tPosicion p, tLista l)
{
   
    	
    	
   
   if (p == l){ 
	Error("Posicion fin(l)");
   }
   return p->elemento;
}

tPosicion siguiente (tPosicion p, tLista l)
{
   
    	
    	
   
   if (p == l){ 
	Error("Posicion fin(l)");
   }
   return p->siguiente;
}

tPosicion anterior( tPosicion p, tLista l)
{
   
    	
    	
   
   if (p == l->siguiente){
	Error("Posicion primero(l)");
   }
   return p->anterior;
}

tPosicion posicion (tElemento x, tLista l)
{
   tPosicion p;
   int encontrado;
   
    	
    	
   

   p = primero(l);
   encontrado = 0;
   while ((p != fin(l)) && (!encontrado))
	if (p->elemento == x)
		encontrado = 1;
	else
		p = p->siguiente;
   return p;
}