LISTAS




1. INTRODUCCIÓN.

Dado un dominio D, una lista de elementos de dicho conjunto es una sucesión finita de elementos del mismo.En lenguaje matemático, una lista es una aplicación de un conjunto de la forma {1,2, ... ,n} en un dominio D:

R:{1,2, ... ,n} ---> D

Una lista se suele representar de la forma:

<a1,a2, ... ,an> con ai = a(i)

A n se le llama longitud de la lista.

A 1,2,...,n se les llama posiciones de la lista. El elemento a(i)=ai, se dice que ocupa la posicion i. Si la lista tiene n elementos, no existe ningún elemento que ocupe la posición n+1. Sin embargo, conviene tener en cuenta dicha posición, a la que se llama posición detras de la última, ya que esta posición indicará el final de la lista. A a1 se le llama primer elemento de la lista y a an último elemento de la lista. Si n=0 diremos que la lista está vacía y lo representaremos como <>. Los elementos de una lista estan ordenados por su posición. Así, se dice que ai precede a ai+1 y que ai sigue a ai-1. A continuación vamos a especificar un ejemplo de posibles operaciones primitivas entre listas. Al conjunto de las listas (es decir, al tipo lista) lo llamaremos tLista. Al conjunto de los elementos básicos(es decir, al tipo que se almacenará en la lista) tElemento. También vamos a considerar el tipo posición como tPosicion. Esto lo haremos así, ya que no siempre las posiciones las vamos a representar por números naturales del lenguaje que se utilice. Lo único importante de la representación que se utilice es que sea un conjunto finito y totalmente ordenado: hay un primer y un último elemento y dado un elemento se puede determinar el siguiente (si no es último) y el anterior (si no es el primero).

Hay que tener en cuenta que si una lista tiene longitud n y se elimina el elemento que ocupa una determinada posición intermedia i, entonces la longitud pasa a ser n-1 y el elemento que estaba en la posición i+1 pasará a ocupar la posición i, el de la posición i+2 pasará a ocupar la posición i+1 y así sucesivamente.


2. OPERACIONES PRIMITIVAS DE LAS LISTAS.

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


ESPECIFICACIÓN SEMANTICA Y SINTACTICA.

Respecto al conjunto de primitivas que hemos presentado, no son más que un ejemplo representativo de las primitivas más importantes que nos sirve para ilustrar la forma en que se debe construir el tipo de dato abstracto Lista. Obviamente, en una implementacion real es posible optar por un conjunto distinto de primitivas teniendo en cuenta varios puntos:


EJEMPLOS DE USO.

Es importante aprender a usar las listas basándonos en estas especificaciones, aunque este tipo no venga en el lenguaje en el que estemos trabajando y no conozcamos la implementación que se va a usar.

Por ejemplo, vamos a escribir un porcedimiento que escriba todos los elementos de una lista. Suponiendo que para tElemento existe un procedimiento, ,escribe(x), que escribe un elemento de dicho tipo.

void salida (tLista t)
{
   tposicion p;
   telemento x;

   for (p = primero(l); p != fin(l); p = siguiente(p, l)){
   	x = elemento(p, l);
   	escribe(x);
   }
}


Veamos otro ejemplo de copia de una lista en otra:

tLista copia (tLista l)
{
   tLista l2;
   tPosicion p;

   anula(&l2);	
   for (p=primero(l);p!=fin(l);p=siguiente(p,l))
       insertar(elemento(p,l),fin(l2),l2);
   return l2;
}


En el siguiente ejemplo, vamos a ver un porcedimiento para eliminar todos los elementos repetidos de la lista. Suponemos que el tipo básico es tElemento y que existe una función lógica, igual(x,y), que nos dice cuando son iguales dos elementos de este tipo. Se podría pensar en que bastaría considerar la igualdad del C(==), pero es posible que no coincidad con la igualdad de tElemento. Por ejemplo, consideremos los numeros racionales definidos como:

typedef struct {
    int num;
    int den;
}racional;


Entonces si x,y son de tipo racional, entonces pueden representar el mismo racional, ser iguales, aunque no se verifique x.num==y.num && x.den==y.den .La función igual sería en este caso:

int igual (int x;int y)
{
 return (x.num*y.den == y.num*x.den);
}


Con estas consideraciones, el procedimiento para eliminar las repeticiones de una lista sería como sigue:

void elimina (tLista l, int (*es_igual)(tElemento, tElemento))
{
   tposicion p, q;

   for (p = primero(l); p != fin(l); p = siguiente(p, l)){
   	q = siguiente(p ,l);
   	while (q != fin(l))
   		if ((*es_igual)(elemento(p, l), elemento(q, l)))
   			borrar(q, l);
   		else
   			q = siguiente(q, l);
   }
}


Unos comentarios respecto a esto ejemplo:



3. IMPLEMENTACIÓN DE LAS LISTAS.


IMPLEMENTACIÓN DE LISTAS MEDIANTE VECTORES.

Las listas se pueden implementar usando las posiciones consecutivas de un vector.Como las listas tienen longitud variable y los vectores longitud fija, esto se resuelve considerando vectores de tamaño igual a la longitud maxima de la lista y un entero donde se indica la posición donde se encuentra el último elemento de la lista.

Así podriamos tener:

#define LMAX = 100;			/* Una constante adecuada. */

typedef int tElemento;    		/* Por ejemplo. */

typedef struct{
	tElemento elementos[LMAX];
   	int n;
} Lista;

typedef Lista *tLista;
typedef int tPosicion;






FUNCIÓN DE ABSTRACCIÓN:

Dado el objeto del tipo rep r = {elementos, n}, el objeto abstracto que representa es:
<r.elementos[0], r.elementos[1], ... , r.elementos[n-1]>


INVARIANTE DE LA REPRESENTACIÓN:

VERDAD.

La implementación de la mayoria de las operaciones es prácticamente inmediata. Por ejemplo, las mas simples son:

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

void anula (tLista *l)
{
   *l = (tLista) malloc (sizeof(Lista));
   if (*l==NULL) {
      error("No hay memoria.");
   }
   (*l)->n=-1;
}

tPosicion primero (tLista l)
{
   return 0;
}

tPosicion fin (tLista l)
{
  return(l->n+1); 
}

tPosicion siguiente (tPosicion p, tLista l)
{
   if ((p < 0) || (p > l->n))
      error("Posición no válida.");
   return (p + 1);
}

tPosicion anterior (tPosicion p, tLista l)
{
   if ((p <= 0) || (p > l->n+1))
      error("Posición no válida.");
   return (p - 1);
}

tElemento elemento (tPosicion p, tLista l)
{
   if ((p < 0) || (p > l->n))
      error("Posición no válida.");
   return (l->elementos[p]);
}


Las únicas operaciones que pueden presentar un poco de dificultad son las de insertar,borrar y posicion. La función posición tiene que realizar una búsqueda lineal en un vector. En caso de que el elemento considerado no esté en el vector, esta función debe devolver lo mismo que fin(l).

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

   q = encontrado = 0;
   while ((q <= l->n) && (!encontrado)) {
   	if (l->elementos[q] == x)
   		encontrado=1;
   	else q++;
   };
   return q;
}


Para la operación de inserción hay que hacer previamente un hueco donde realizar dicha inserción. Para el borrado, hay que "rellenar" el hueco dejado por el elemento borrado. En la figura podemos observar en las flechas superiores los movimientos de los elementos que se han tenido que realizar para insertar en la posición p (coinciden con los movimientos en sentido contrario que se deben realizar para borrar el elemento que se encuentra en dicha posición).




Como consecuencia de ello, habrá que mover, en ambos casos, todos los elementos que ocupen una posición superior a la considerada para realizar la inserción o borrado. Esto tiene como consecuencia que la eficiencia de las operaciones no es muy buena, del orden del tamaño de la lista.

void insertar (tElemento x, tPosicion p, tLista l)
{
   tPosicion q;
   if ((p > l->n+1) || (p < 0))
   	error("Error p incorrecta.");
   else if (l->n >= LMAX-1)
   		error("Lista llena");
   	 else{
   	   for (q = l->n; q >= p; q--)
   		l->elementos[q+1]  = l->elementos[q];
	   l->n++;
   	   l->elementos[p] = x;
        }
}

void borrar (tPosicion p,tLista l)
{
  if ((p > l->n) || (p < 0))
    error("p incorrecta.");
  else {
    l->n--;
    for (; p <= l->n; p++) 
	l->elementos[p]=l->elementos[p+1];
  }
}


Aparte de la mala eficiencia de estas dos operaciones, que veremos como se mejorará en otras implementaciones, otro inconveniente de esta implementación es que las listas tienen un tamaño máximo del que no se puede pasar. Es decir, no corresponden exactamente a las especificaciones consideradas en un principio. Por otra parte, siempre hay una porción de espacio reservada para los elementos de la lista, y que no se utiliza al ser el tamaño de la lista, en un momento dado menor que el tamaño máximo. Esto se hace más grave si las distintas listas que se representen son de un tamaño muy distinto.

Otro detalle importante de esta implementación es, cómo hemos mencionado anteriormente, la necesidad de una función de destrucción ya que ahora mismo la memoria que se requiere cada vez que se hace una llamada a la función anula no es recuperada en ningún momento.Sería interesante añadir una nueva función tal como la siguiente (Nótese que si la constante LMAX es grande y se hace uso de un número alto de listas esta función no sólo se hace interesante sino que necesaria:

void destruye (tLista l) 
{
   free(l);
}


Teniendo en cuenta los problemas que presenta la implementación que hemos presentado mediante vectores y considerando las posibilidades que nos brinda el lenguaje C, podemos proponer una versión mas optimizada:

typedef int tElemento		/* Por ejemplo. */

typedef struct{
   tElemento *elementos;
   int Lmax;
   int n;
}Lista;

typedef Lista *tLista; 
typedef int tPosicion;  

tLista crear (int tamanoMax)
{
   tLista l; 

   l = (tLista) malloc(sizeof(Lista)); 
   if (l == NULL)
   	error("Memoria Insuficiente");
   l->Lmax = tamanoMax;
   l->n = -1;
   l->elementos = (tElemento *)malloc(tamanoMax*sizeof(tElemento));
   if (l->elementos == NULL)
   	error("Memoria Insuficiente.");
}

void destruir (tLista l)
{
   free(l->elementos);
   free(l);   
}


Donde las demás primitivas quedarían de la misma forma sustituyendo LMAX por l->LMAX

En esta nueva implementación conseguimos resolver con exito dos cosas:

  1. Tamaños variables: Ahora la primitiva anula ha sido sustituida por la primitiva crear a la que se pasa un parámetro indicando el tamaño maximo que tendra la lista.La mejora, por lo tanto, ha sido sustancial teniendo en cuenta que el tamaño máximo que es necesario para la versión anterior debe ser superior a la más grande de las listas que se manejan y por consiguiente para pequeñas listas habría una gran cantidad de memoria desperdiciada.

  2. Creación y Destrucción: Aunque en la versión anterior se solucionó el problema al proponer la función destruye, es importante destacar que en esta versión también se ofrece el constructor y destructor del tipo de dato permitiendo de esta forma recuperar los recursos ocupados por las listas que no se volverán a usar.

Es importante destacar la forma en que se deben usar las funciones de un tipo de dato abstracto (normalmente en la especificación junto con algún ejemplo si es necesario). Así destacaremos que que en este nuevo conjunto de primitivas incluyendo crear y destruir el uso del TDA debe ser:

  1. Declaración de la variable de tipo tLista.
  2. Creación de la lista mediante la primitva crear.
  3. Uso de la lista mediante primitivas distintas a la de creación y destrucción.
  4. Destrucción de la lista mediante la primitiva destruir.

Teniendo en cuenta:

  1. El uso de la primitiva crear sobre una lista ya creada provocará una pérdida de los recursos de memoria ocupados por esta lista y la actualización de su valor a la lista vacía.
  2. El uso de la primitiva destruir a una lista no creada o a una lista que aunque se creó ha sido destruida es erróneo y provocará resultados imprevisibles.
  3. Obviamente, después de la destrucción de una lista, se podrá usar de nuevo la misma variable en la creación, uso y destrucción de una nueva lista.

Como ejemplo mostramos una función que guarda en una lista los números enteros del 0 al 9, despues la recorre eliminando los impares y por último escribe el resultado dos veces, desde el primer elemento al último y desde el último al primero:

void EJEMPLO ()
{
   int a;
   tLista l;
   tPosicion p;

   l = crear(10);
   for (a=0; a<10; a++)
	insertar(a, primero(l), l);
   for (p=primero(l); p!=fin(l); ) {
   	a = elemento(p,l);
	if (a%2) 
		borrar(p,l);
   	else 
		p = siguiente(p,l);
   }
   for (p=primero(l); p!=fin(l); p=siguiente(p,l)) {
 	a = elemento(p,l);
	printf("Elemento: %d \n",a);
   }
   printf(" \n \n ");
   for (p=fin(l); p!=primero(l); p=anterior(p,l)) {
	a = elemento(anterior(p,l), l);
	printf("Elemento: %d \n",a);
   }
   destruir(l);
}



IMPLEMENTACIÓN DE LISTAS MEDIANTE CELDAS ENLAZADAS POR PUNTEROS.




Una implementación de las listas que evita los problemas anteriormente mencionados para los vectores, es la que está basada en el uso de punteros. Esta implementación se basa en representar cada elemento, ai, de una lista <a1,a2, ...,an> como una celda dividida en dos partes: un primer campo donde se almacena el elemento en cuestión; y un segundo campo donde se almacena un puntero, que nos indica donde está el siguiente elemento de la lista, tal como se muestra en la parte (a) de la figura.

La celda que contiene el último elemento de la lista tiene un puntero donde se almacena NULL. Así, la lista quedaria como se muestra en la parte (b) de la figura.

Para realizar más facilmente las operaciones es conveniente considerar una celda inicial, llamada de cabecera y donde no se almacena ningún elemento de la lista. De esta forma la lista propiamente diche vendrá representada por un puntero que indique la dirección de la cabecera y que permite obtener los distintos elementos de la misma como se muestra finalmente en la parte (c) de la figura.




Para estas listas es conveniente representar la posición mediante un puntero que acceda al elemento correspondiente. Sin embargo, no se va a consider un puntero con la dirección de la celda donde está el elemento considerado, sino la dirección de la celda donde está el elemento anterior. Con esto se puede acceder a dicho elemento (mediante el puntero correspondiente), y también será más útil para las operaciones de inserción y borrado. La posición del primer elemento, vendrá representada entonces por un puntero apuntando a la celda de cabecera, es decir, idéntico a la lista, l. La posición del elemento ai se representará mediante un puntero, indicando la celda del elemento ai-1. La posición detrás del último elemento será un puntero apuntando a an.

Debido a que la posición lógica de un elemento viene determinada por la posición física del anterior puede dar lugar a un error de programación si se trabaja con varias posiciones a la vez y se realizan borrados. Por ejemplo, consideremos una lista con 3 elementos y 2 punteros indicando la posición del segundo (puntero p) y tercer (puntero q) elemento (ver figura).




Si no atendemos a la implementación, el borrar el elemento de la posición p (elemento a2) podemos considerar dos resultados:

En general, el primer caso corresponde a la implementación realizada mediante vectores y el segundo a la realizada mediante celdas enlazadas teniendo en cuenta:

Es por ello que el uso simultáneo de varias posiciones conviene que sea manejado con cuidado. Obviamente, el que el acceso a un elemento se produzca por medio del elemento anterior conviene que sea indicado en la especificación del TDA mediante el correspondiente aviso de que el borrado de un elemento invalidad los valores de posición del inmediatamente posterior (por ejemplo, se puede indicar el comportamiento de los valores posición cuando se usan las funciones de inserción y de borrado).

En C, la definición de tipos correspondiente a la implementación por punteros sería:

typedef struct Celda{
	tElemento elemento;
	struct Celda *siguiente;
}celda;

typedef celda *tPosicion;
typedef celda *tLista;


FUNCIÓN DE ABSTRACCIÓN

Dado el objeto del tipo rep l={elemento, siguiente}, el objeto abstracto que representa es:
<l->siguiente->elemento, l->siguiente->siguiente->elemento, ... ,l->siguiente-> (n) ->siguiente->elemento>
Donde r->siguiente-> (n+1) ->siguiente == NULL.

INVARIANTE DE REPRESENTACIÓN

Todas las direcciones de los campos siguiente proceden de llamadas (tposicion) malloc(sizeof(celda)) o son NULL.

Y las operaciones se pueden implementar como sigue:

tLista crear ()
    
    

{
   tLista l;

   l = (tLista)malloc(sizeof(celda));
   if (l == NULL)
   	error("Memoria Insuficiente.");
   l->siguiente = NULL;
   return l;
}

void destruir (tLista l)
    
    

{
   tPosicion p;

   for (p = l; l != NULL; p = l){
   	l = l->siguiente;
   	free(p);
   }
}
   
tPosicion fin (tLista l)
    
    

{
   tPosicion p;

   p=l;
   While (p->siguiente != NULL) {
      p = p->siguiente;
   }
   return p;
}


Repecto a esta función es importante senñalar , que siempre tiene que recorrer toda la lista para devolver el puntero que se muestra en la figura. Por lo que su eficiencia es del orden de la longitud de la lista. Habría que procurar no utilizarla demasiado si se usa esta implementación.




Por ejemplo, un ciclo while con una condición p!=fin(l) se debe sustituir por:
q=fin(l);
while (p!=q)...



void insertar (tElemento x, tPosicion p, tLista l)
    
    

{
   tPosicion q;

   q = (tPosicion)malloc(sizeof(celda));
   if (q == NULL)
	error("Memoria Insuficiente.");
   q->elemento = x;
   q->siguiente = p->siguiente;
   p->siguiente = q;
}


La forma en la que se realiza la inserción puede observarse en la figura.



Es importante señalar varias cosas de este procedimiento:



tPosicion siguiente (tPosicion p, tLista l)
    
    

{
   if (p->siguiente==NULL) {
 	error("No hay siguiente de fin.");
   }
   return p->siguiente;
}

tPosicion primero (tLista l)
    
    

{
   return l;
}

tPosicion posicion (tElemento x, tLista l)
    
    

{
   tPosicion p;
   int encontrado;

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


Notas referentes a la función posicion:



tElemento elemento (tPosicion p, tLista l) 
    
    

{
   if (p->siguiente == NULL) {
 	 error("Error: posicion fin(l).");
   }
   return p->siguiente->elemento;
}

void borrar (tPosicion p, tLista l)
    
    

{
   tPosicion q;	

   if (p->siguiente == NULL)
	error("Error: posicion fin(l).");
   q = p->siguiente;
   p->siguiente = q->siguiente;
   free(q);
}


Respecto a esta implementación son válidos los mismos comentarios que para la función insercion.


4. COMPARACIÓN DE MÉTODOS.

Resulta de interés saber si es mejor usar una implementación de listas basada celdas enlazadas o en matrices en una circunstancia dada. Frecuentemente la contestación depende de las operaciones uqe queramos llevar a cabo, o de cuales son llevadas a cabo con mayor asiduiadad. Otras veces, la decisión es en base a la longitud de la lista.

Los puntos principales a considerar son los siguentes:

  1. La implementación matricial nos obliga a especificar el tamaño máximo de una lista en tiempo de compilación. Si no podemos poner una cota a la longitud de la lista, posiblemente deberíamos coger una implementación basada en punteros. Lógicamente, este problema ha sido parcialmente solucionado con la parametrización del tamaño máximo de la lista, pero aún así hay que delimitar el tamaño máximo para cada una de las listas.

  2. Ciertas operaciones requieren más tiempo en unas implementaciones que en otras. Por ejemplo insertar y borrar realizan un número constante de pasos para una lista enlazada, pero necesitan tiempo proporcional al número de elementos siguientes cuando usamos la representación matricial.Inversamente, ejecutar fin requiere tiempo constante con la implementación matricial, pero tiempo proporcional a la lista si usamos la implementación por punteros simplemente-enlazadas (aunque recordemos que el problema es solucionable añadiendo un puntero). Por otro lado, en las listas doblemente-enlazadas se requiere tiempo constante para todas las operaciones (excepto la de posición que requiere un tiempo proporcional a la longitud de la lista).

  3. La implementación matricial puede derrochar espacio, ya que usa la cantidad máxima de espacio independientemente del número de elementos presentes en la lista en un momento dado. La implementación por punteros usa tanto espacio como necesita para los elementos que hay en la lista, pero necesita espacio adicional para los punteros de cada celda.Por último, las listas doblemente-enlazadas aunque son las más eficientes requieren dos punteros para cada elemento.

  4. En las listas enlazadas la posición de un elemento se determina con un puntero a la celda del elemento anterior por lo que hay que tener cuidado con la operación de borrado si se trabaja con varias posiciones tal y como vimos anteriormente. En el caso de la implementación matricial, si borramos un elemento, todas las posiciones posteriores a ese elemento apuntarán al siguiente al que apuntaban y si existe una posición apuntando al final de la lista, ésta queda invalidada. (El comportamiento tambien es distinto para la inserción). En el caso de las listas doblemente-enlazadas, su comportamiento es el mas cómodo siempre que la implementación realizada no provoque que la posición usada en el borrado quede invalidada.




Tutor de Estructuras de Datos Interactivo
Exposito Lopez Daniel, Abraham García Soto, Martin Gomez Antonio Jose
Director de proyecto: Joaquín Fernández Valdivia
5º Licenciatura Informatica
ETSII 99/00 (Universidad de Granada).