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.
