Listas Enlazada

LISTAS ENLAZADAS.

La lista enlazada es un TDA que nos permite almacenar datos de una forma organizada, al igual que los vectores pero, a diferencia de estos, esta estructura es dinámica, por lo que no tenemos que saber "a priori" los elementos que puede contener.

En una lista enlazada, cada elemento apunta al siguiente excepto el último que no tiene sucesor y el valor del enlace es null. Por ello los elementos son registros que contienen el dato a almacenar y un enlace al siguiente elemento. Los elementos de una lista, suelen recibir también el nombre de nodos de la lista.

struct lista {

gint dato;

lista *siguiente;

};

Representa el dato a almacenar. Puede ser de cualquier tipo; en este ejemplo se trata de una lista de enteros.

Es un puntero al siguiente elemento de la lista; con este puntero enlazamos con el sucesor, de forma que podamos construir la lista.

Esquema de un nodo y una lista enlazada.

Para que esta estructura sea un TDA lista enlazada, debe tener unos operadores asociados que permitan la manipulación de los datos que contiene. Los operadores básicos de una lista enlazada son:

• Insertar: inserta un nodo con dato x en la lista, pudiendo realizarse esta inserción al principio o final de la lista o bien en orden.

• Eliminar: elimina un nodo de la lista, puede ser según la posición o por el dato.

• Buscar: busca un elemento en la lista.

• Localizar: obtiene la posición del nodo en la lista.

• Vaciar: borra todos los elementos de la lista

GSList

La definición de la estructura GSList o, lo que es lo mismo, un nodo de la lista, está definido de la siguiente manera:

struct GSList {

gpointer data;

GSList *next;

};

Representa el dato a almacenar. Se utiliza un puntero genérico por lo que puede almacenar un puntero a cualquier tipo de dato o bien almacenar un entero utilizando las macros de conversión de tipos.

Se trata de un puntero al siguiente elemento de la lista.

Las macros de conversión disponibles son las siguientes:

• GINT_TO_POINTER ()

• GPOINTER_TO_INT ()

• GUINT_TO_POINTER ()

• GPOINTER_TO_UINT ()

Las funciones que acompañan a la estructura GSList y que implementan los operadores básicos de las listas enlazadas, son las siguientes:

Operadores de inserción en listas enlazadas.

Operador Funciones asociadas a GSList.

Insertar al principio. GSList* g_slist_prepend (GSList *list, gpointer data)

Insertar al final. GSList* g_slist_append (GSList *list, gpointer data)

Insertar en la posición indicada. GSList* g_slist_insert (GSList *list, gpointer data, gint position)

Insertar en orden. GSList* g_slist_insert_sorted (GSList *list, gpointer data, GCompareFunc func)

Las funciones de inserción al principio de la lista, g_slist_prepend, y al final, g_slist_append, son sencillas de usar. Sólo hay que pasarles como parámetros la lista donde queremos añadir el dato así como el dato a insertar y la función devuelve una lista con el nuevo dato insertado.

La función g_slist_insert inserta el dato en la posición indicada. Su uso también es sencillo como puede verse en el siguiente ejemplo.

Insertar un nuevo dato en una posición determinada.

/* obtiene el numero de nodos de la lista */

length = g_slist_length (list);

g_print ("\nEscribe el nº de indice donde se insertara el dato (el indice maximo es %d): ", length);

scanf ("%d", &index);

/* inserta el valor en la posicion indicada */

if (index < length) {

list = g_slist_insert (list, GINT_TO_POINTER (value), index);

print_list (list);

}

En este ejemplo se utiliza la función g_slist_length para obtener el número de nodos que contiene la lista. A esta función hay que pasarle como parámetro la lista de la que se desea obtener el número de nodos y devuelve como resultado el número de nodos de ésta.

guint * g_slist_length

...