---

---

Les listes chaînées

Vous connaissez sûrement déjà les listes chaînées. Elles sont très pratiques, mais il faut s'occuper soit même de la gestion de la mémoire, de chaîner les éléments, à chaque fois que l'on veut ajouter ou supprimer un élément. La bibliothèque GLib propose des listes chaînées génériques que nous allons pouvoir utiliser dans nos applications Gtk+.

1. Les listes chaînées simples : GSList

Regardons tout d'abord comment est défini cet objet :

struct GSList
{
    gpointer data;
    struct GSList *next;
};

Nous voyons donc qu'elle nous permet de créer la plus simple des liste chaînée, c'est à dire que chaque élément connaît son suivant et rien d'autre. La liste s'organise suivant ce schéma :

Etudions comment créer une telle liste.

1.1 Création d'une GSList

Il faut d'abord avoir le pointeur sur le premier élément de la liste. Pour cela, rien de plus simple :

GSList *premier = NULL;

Ensuite, il n'existe pas de fonction spécifique pour créer la liste, il suffit juste d'ajouter un élément à la liste. Plusieurs fonctions sont disponibles mais nous allons en étudier deux.

GSList* g_slist_append (GSList *list, gpointer data);
GSList* g_slist_prepend (GSList *list, gpointer data);

La première g_slist_append ajoute un nouvel élément à la fin de la liste, alors que g_slist_prepend l'ajoute au début de la liste. La variable list est bien sûr la liste chaînée à laquelle on veut ajouter un élément comportant la donnée data. Il suffit de faire un cast pour donner le type de data. Si l'on veut que notre premier élément soit un widget, il suffira d'écrire la ligne de code suivante :

premier = g_slist_append(premier, (GtkWidget*) widget);

La valeur de retour est très importante : elle correspond à l'adresse du premier élément de la liste. En effet, au départ notre élément premier ne pointe nul part (premier = NULL), il faut donc toujours récupérer cette adresse (surtout dans le cas de g_slist_prepend où le premier élément change).

1.2 Récupérer les données d'une GSList

Là aussi, nous n'allons étudier que deux fonctions :

GSList* g_slist_nth (GSList *list, guint n);
gpointer g_slist_nth_data (GSList *list, guint n);

list est bien sur la liste à laquelle l'élément recherché appartient, et n est la position de l'élément dans la liste (le premier élément est à n=0). Avec ces deux fonctions, il suffit juste de connaître la position d'un élément pour récupérer la donnée qu'il contient.

La première fonction renvoie un pointeur sur une variable du type GSList. Il faudra donc utiliser l'opérateur -> pour récupérer la valeur data. La deuxième, par contre, renvoie directement la valeur de data.

Si la valeur donnée à n ne fait pas partie de la liste, la valeur de retour sera NULL.

Supposons qu'une variable de type GtkWidget soit stockée dans le premier élément d'une liste nommé liste, et que l'on veuille récupérer ce widget, il faudra alors coder :

temp_list = g_slist_nth(liste, 0);
widget = (GtkWidget*) (temp_list->data);

ou

widget = (GtkWidget*) g_slist_nth_data(liste, 0);

1.3 Suppression d'élément d'un GSList

Pour supprimer un élément définitivement d'une liste, la fonction à utiliser est la suivante :

GSList* g_slist_remove (GSList *list, gconstpointer data);

Cette fonction cherche le premier élément de la liste contenant la donnée data et le supprime. La valeur de retour est là aussi très importante car elle correspond (toujours pareil) au nouveau premier élément de la liste. Si par hasard, plusieurs éléments contiennent la donnée data, seul le premier sera supprimé. Dans ce cas, pour tous les supprimer, il faut utiliser cette fonction (dont l'utilisation est identique à la première) :

GSList* g_slist_remove_all (GSList *list, gconstpointer data);

Pour supprimer une liste entière, la fonction est :

void g_slist_free (GSList *list);

Avec toutes ces fonctions, nous en savons suffisamment pour pouvoir utiliser une liste simple.

2. Les listes chaînées double : GList

Cette liste est légèrement différente car en plus de connaître son suivant, chaque élément connaît aussi l'élément qui le précède. Cette structure est définie ainsi :

struct GList
{
    gpointer data;
    struct GList *next;
    struct GList *prev;
};

Cette nouvelle liste s'organise donc ainsi :

L'étude sera cette fois beaucoup plus rapide car vous allez le voir, les fonctions pour les GList sont quasiment identiques à celles de GSList.

2.1 Création d'une GList

Là encore, il nous faut un pointeur sur le premier élément de la liste.

GList *premier = NULL;

Comme pour les GList, il n'y a pas de fonction spécifique il suffit d'ajouter des éléments avec les fonctions suivantes :

GList* g_list_append (GList *list, gpointer data);
GList* g_list_prepend (GList *list, gpointer data);

Les paramètres sont identiques que pour son homologue GSList et la valeur de retour est toujours un pointeur sur le premier élément de la liste.

2.2 Récupérer les données d'une GList

Une nouvelle fois, les fonctions ressemblent à celles des GSList :

GList* g_list_nth (GList *list, guint n);
gpointer g_list_nth_data (Glist *list, guint n);

2.3 Suppression d'élément d'un GSList

Les fonctions de suppression sont toujours semblables :

GList* g_list_remove (GList *list, gconstpointer data);
GList* g_list_remove_all (GList *list, gconstpointer data);
void g_list_free (GList *list);

Bien sur pour ces deux types de listes, d'autres fonctions existent pour ajouter, déplacer, ordonner, supprimer des éléments. Ces dernières sont (comme à l'accoutumé) dans la section en savoir plus.

Il n'y aura pas dans ce chapitre d'exemple d'utilisation, mais vous pourrez voir l'intérêt particulier de ces deux types de listes dans les chapitres suivants.

3. En savoir plus :

3.1 Fonctions documentées

GSList* g_slist_insert (GSList *list, gpointer data, gint position); GList* g_list_insert (GList *list, gpointer data, gint position);

Ajoute un nouvel élément dans une liste à la position demandée. Entrée(s) : list : la liste. data : la valeur à ajouter. position : la position à laquelle sera ajouté l'élément. Si cette valeur est invalide (négative ou trop grande) l'élément sera ajouter à la fin de la liste. Sortie : le pointeur sur le premier élément de la liste.

GSList* g_slist_insert_before (GSList *list, GSList *sibling, gpointer data); GList* g_list_insert_before (GList *list, GList *sibling, gpointer data);

Ajoute un nouvel élément avant un autre élément. Entrée(s) : list : la liste. sibling : élément avant lequel doit être insérée notre nouvelle valeur. data : valeur à ajouter. Sortie : le pointeur sur le premier élément de la liste.

GSList* g_slist_remove_link (GSList *list, GSList *link); GList* g_list_remove_link (GList *list, GList *link);

Supprime un élément d'une liste. L'élément supprimer deviendra le premier d'un nouvelle liste. Entrée(s) : list : la liste. link : l'élément à supprimer de la liste. Sortie : le pointeur sur le premier élément de la liste.

GSList* g_slist_delete_link (GSList *list, GSList *link); GList* g_list_delete_link (GList *list, GList *link);

Supprime un élément d'un liste. Entrée(s) : list : la liste. link : l'élément à supprimer. Sortie : le pointeur sur le premier élément de la liste.

guint g_slist_length (GSList *list); guint g_list_length (GList *list);

Pour connaître le nombre d'élément d'un liste. Entrée(s) : list : la liste. Sortie : le nombre d'éléments de la liste.

GSList* g_slist_copy (GSList *list); GList* g_list_copy (GList *list);

Crée une copie d'une liste. Entrée(s) : list : la liste. Sortie : le pointeur sur le premier élément de la nouvelle liste.

GSList* g_slist_reverse (GSList *list); GList* g_list_reverse (GList *list);

Inverse les éléments d'une liste Entrée(s) : list : la liste. Sortie : le pointeur sur le premier élément de la liste.

GSList* g_slist_concat (GSList *list1, GSList *list2); GList* g_list_concat (GList *list1, GList *list2);

Ajoute une liste à la fin d'une autre. Entrée(s) : list1 : la liste de départ. list2 : liste à ajouter à la suite de list1. Sortie : le pointeur sur le premier élément de la liste.

GList* g_list_first (GList *list);

Pour récupérer le premier élément d'une liste. Entrée(s) : list : la liste. Sortie : le pointeur sur le premier élément de la liste.

GSList* g_slist_last (GSList *list); GList* g_list_last (GList *list);

Pour récupérer le dernier élément d'une liste. Entrée(s) : list : la liste. Sortie : le pointeur sur le dernier élément de la liste.

g_slist_next(list) g_list_next(list)

Une macro permettant d'obtenir l'élément suivant d'une liste. Entrée(s) : list : la liste. Sortie : le pointeur sur l'élément suivant ou NULL si l'on est en fin de liste.

g_list_previous(list)

Une macro permettant d'obtenir l'élément précédent d'une liste. Entrée(s) : list : la liste. Sortie : un pointeur sur l'élément précédent ou NULL si on est en début de liste.

GSList* g_slist_find (GSList *list, gconstpointer data); GList* g_list_find (GList *list, gconstpointer data);

Récupère l'élément contenant une certaine donnée. Entrée(s) : list : la liste. data : la donnée à chercher. Sortie : un pointeur sur l'élément trouvé ou NULL s'il n'y en a pas.

gint g_slist_position (GSList *list, GSList *llink); gint g_list_position (GList *list, GList *llink);

Pour connaître la position d'un élément. Entrée(s) : list : la liste. llink : l'élément à chercher. Sortie : la position de l'élément dans la liste ou -1 s'il n'existe pas.

gint g_slist_index (GSList *list, gconstpointer data); gint g_list_index (GList *list, gconstpointer data);

Pour connaître la position d'un élément contenant une certaine donnée. Entrée(s) : list : la liste. data : la donnée à chercher. Sortie : la position de l'élément dans la liste ou -1 s'il n'existe pas.

Date de mise à jour : 19 septembre 2002.

---

---