Aujourd'hui, nous voir comment la glib-2.0 nous permet de manipuler facilement et de manière très complète les listes chaînées.

Les listes chaînées sont des structures de données dynamiques permettant de stocker un grand nombre d'éléments, de manière beaucoup plus souple qu'avec un simple tableau. Chacun des éléments d'une telle liste (d'une telle chaîne), est composé d'une donnée, d'un pointeur sur l'élément précédent de la chaîne et d'un pointeur sur l'élément suivant. Au sein de la glib-2.0, ces éléments, ces maillons, sont représentés par la structure suivante:

où data est un pointeur générique sur un élément de type quelconque, next est un pointeur sur le maillon suivant de la chaîne et prev est un pointeur sur le maillon précédent de la chaîne. Si l'élément précédent n'existe pas (notre maillon est le premier de la chaîne), prev vaut NULL. De même, pour le dernier maillon de la chaîne, next vaut NULL.

Tout ce dont on a besoin pour pouvoir manipuler une telle chaîne, c'est un pointeur sur le début (le premier maillon) de celle-ci. Si ce pointeur vaut NULL, c'est que la chaîne est vide.

list doit être un pointeur sur une chaîne valide, ou NULL, si l'on veut créer le premier maillon d'une nouvelle chaîne.
data est un pointeur sur l'élément que l'on veut introduire dans la chaîne. La valeur renvoyée par cette fonction est le nouveau pointeur sur le début de la chaîne. Il est important de bien sauvegarder cette nouvelle valeur, car c'est la seule référence réelle à la chaîne. La fonction g_list_append() ajoute l'élément à la fin de la chaîne. Si l'on veut ajouter un élément en début de chaîne, on utilisera la fonction suivante :

Il est également possible d'insérer un élément dans une chaîne à un endroit quelconque à l'aide de la fonction :

Le paramètre position indique où il faut insérer le nouvel élément. S'il est négatif ou plus grand que la taille actuelle de la chaîne, le nouvel élément sera inséré à la fin de la chaîne. S'il vaut zéro, il sera inséré en début de chaîne. Sinon, il sera inséré comme le ``position^ième'' élément de la chaîne.

La dernière façon d'ajouter un maillon dans une chaîne est d'utiliser la fonction suivante :

Cette fonction permet d'insérer les éléments suivant un ordre précis défini par la fonction cmp_fonction. Cette fonction doit avoir le prototype suivant:

où a et b sont des pointeurs sur les données de deux maillons de la chaîne. Cette fonction doit renvoyer une valeur positive si a est supérieur à b (ici, le sens du mot "supérieur" est entièrement défini par la fonction...), une valeur négative si a est inférieur à b et 0 si a et b sont égaux. Par exemple, pour une liste où tous les éléments sont des chaînes de caractères, on peut insérer une nouvelle chaîne, dans l'ordre alphabétique par un appel du genre:

A vrai dire, je déconseille plutôt l'utilisation de g_list_insert_sorted() lorsque l'on veut créer une grande chaîne triée à partir de données brutes. Il est en général beaucoup plus rapide d'utiliser g_list_prepend() pour chacun des éléments, puis de trier la chaîne une fois constituée à l'aide de la fonction suivante:

où le paramètre cmp_fonction a le même rôle que dans la fonction g_list_insert_sorted().

Lorsque l'on parle d'un maillon (ou d'un élément), il faut bien faire attention à ne pas confondre deux notions:
•        

le pointeur sur l'élément proprement dit, de type gpointer, donc générique. Il peut s'agir d'un pointeur sur une structure, d'un pointeur sur une chaîne de caractères ou même d'un entier, par exemple en utilisant la macro GINT_TO_POINTER().
•         le pointeur sur la structure de type GList, qui contient les pointeurs sur les maillons précédents et suivants et sur l'élément proprement dit.

C'est pourquoi il existe plusieurs fonctions permettant de supprimer un maillon de la chaîne:

supprime le premier maillon de la liste list dont la donnée est désignée par le pointeur data.

Il peut bien entendu exister plusieurs maillons possédant le même pointeur data (ou s'il on a affaire à une liste d'entier, plusieurs maillons avec la même valeur numérique...). Aussi est-il possible de supprimer tous les maillons dont la donnée est pointée par data avec la fonction suivante:

Il est également possible de supprimer un maillon, en connaissant un pointeur sur sa structure GList avec la fonction suivante:

Attention! Contrairement aux précédentes, cette fonction ne libère pas la mémoire réservée par la structure GList (je ne parle pas de celle qui est éventuellement pointée par le pointeur data). C'est pourquoi on l'utilise assez peu. On lui préférera la fonction:

Une fois une liste constituée, il est possible d'effectuer un certain nombre d'opérations. Vous connaissez déjà g_list_sort(), qui permet de trier la liste.

Il faut bien garder à l'idée que cette fonction ne fait que copier les structures GList, en les reliant entre elles. Les éventuelles structures pointées par les pointeurs data ne sont pas copiées.

Cette fonction concatène la liste list2 à la liste list1. Rien n'est copié. Il s'agit juste d'une fusion des deux listes.

Un seul appel à cette fonction appellera la fonction fonction autant de fois qu'il y a de maillons dans la chaîne. Cette fonction est appelée avec deux arguments. Le premier est le pointeur data de chacun des maillons, le second est le paramètre donnee_sup. Par exemple, pour afficher toutes les données d'une liste de chaînes de caractères, on pourra utiliser la fonction suivante:

Puis, cette fonction pourra être appelée pour chacun des maillons grâce à l'appel suivant:

Il est possible d'effectuer différents types de recherche dans une liste. Par exemple, il est possible de retrouver le premier ou le dernier maillon d'une chaîne à partir d'un maillon quelconque de cette chaîne à l'aide, respectivement, des deux fonctions suivantes:

Les deux macros suivantes permettent respectivement de retrouver le maillon précédant ou suivant un maillon donné:

Il est possible de retrouver le n^ième maillon d'une liste grâce à la fonction suivante:

En fait, cette fonction fait bien plus que cela. Elle retrouve aussi le n^ième maillon après un maillon donné. Par exemple, Pour retrouver le 5^ième maillon après le maillon maillon1, on utilisera:

Réciproquement, il est possible de retrouver le n^ième maillon avant un maillon donné avec la fonction suivante:

Pour une recherche un peu plus avancée, la fonction suivante permet de retrouver le maillon (le pointeur GList *) à partir de son pointeur data.

Pour cela, elle compare, un à un tous les pointeurs data des maillons de la chaîne au paramètre data. S'ils sont égaux, le maillon correspondant est renvoyé.

Si vous voulez utiliser une fonction particulière pour tester l'égalité des pointeurs data, vous pouvez utiliser la fonction suivante:

où fonction est une fonction de la même sorte que celles utilisées avec g_list_insert_sorted().

Toutes les fonctions de recherche présentées jusqu'à maintenant renvoient un pointeur sur la structure GList du maillon si un maillon est effectivement trouvé, et NULL sinon.

En connaissant un maillon dans une liste, il est possible de connaître son rang avec la fonction suivante:

De même, il est possible de connaître la position du premier maillon dont le pointeur data est data:

Enfin, la fonction suivante renvoie le nombre de maillons que comporte une liste donnée:

Voyons maintenant un programme exemple qui met en uvre quelques-unes de toutes ces fonctions.

Il existe un autre type de listes, gérées par la glib-2.0. Il s'agit des GSLists. Elles fonctionnent de la même façon que les GLists, mais les maillons des GSLists ne possèdent pas de pointeurs prev. Cela permet de gagner un peu de place, mais pour le coup, certaines fonctions ne sont plus accessibles.
Les fonctions qui gèrent les GLists portent le même nom que celles des GLists. Simplement, le préfixe g_list_ est remplacé par g_slist_.

La prochaine fois, nous étudierons une autre structure de données gérée par la glib-2.0: les arbres.