Listas enlazadas

Estructuras de datos: listas enlazadas, pilas y colas.
Listas enlazadas.
Introducción
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 exceptoel ú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 siguienteelemento de la lista; con este puntero enlazamos con el sucesor, de forma que podamos construir la lista. |
Figura 1. 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 xen 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
Después de esta breve introducción, que sólo pretendeservir como recordatorio, pasaremos a ver cómo es la estructura GSList que, junto con el conjunto de funciones que la acompañan, forman el TDA lista enlazada en GLib™.
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 unpuntero 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 ()
Más adelante, en esta misma sección, se verán ejemplos del uso deestas macros.
Las funciones que acompañan a la estructura GSList y que implementan los operadores básicos de las listas enlazadas, son las siguientes:
Tabla 6. 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...