Exercice n°1

Voilà... Maintenant, vous êtes des as en matière de liste chaînées, j'en suis sûr. Je vous propose donc quelques exercices. Le premier sera de coder de manière itérative la fonction nombreElements dont je vous rappelle le prototype :

int nombreElements(llist liste);

C'est un exercice qui ne devrait pas vous poser de problèmes : bonne chance.

int nombreElements(llist liste)
{
    int nb = 0;
    element* tmp = liste;
 
    /* On parcours la liste */
    while(tmp != NULL)
    {
        /* On incrémente */
        nb++;
        tmp = tmp->nxt;
    }
    /* On retourne le nombre d'éléments parcourus */
    return nb;
}

C'est aussi simple que ça. On parcourt simplement la liste tant que l'on n'est pas arrivé au bout, et on incrémente le compteur nb que l'on renvoie pour finir.

Exercice n°2

Nous allons maintenant écrire une fonction permettant d'effacer complètement une liste chaînée de la mémoire. Je vous propose d'écrire avec un algorithme itératif dans un premier temps, puis une seconde fois grâce à un algorithme récursif. Dans le premier cas, vous devez parcourir la liste, stocker l'élément suivant, effacer l'élément courant et avancer d'une case. A la fin la liste est vide, nous retournerons NULL.

llist effacerListe(llist liste)
{
    element* tmp = liste;
    element* tmpnxt;
 
    /* Tant que l'on n'est pas au bout de la liste */
    while(tmp != NULL)
    {
        /* On stocke l'élément suivant pour pouvoir ensuite avancer */
        tmpnxt = tmp->nxt;
        /* On efface l'élément courant */
        free(tmp);
        /* On avance d'une case */
        tmp = tmpnxt;
    }
    /* La liste est vide : on retourne NULL */
    return NULL;
}
llist effacerListe(llist liste)
{
    if(liste == NULL)
    {
        /* Si la liste est vide, il n'y a rien à effacer, on retourne 
        une liste vide i.e. NULL */
        return NULL;
    }
    else
    {
        /* Sinon, on efface le premier élément et on retourne le reste de la 
        liste effacée */
        element *tmp;
        tmp = liste->nxt;
        free(liste);
        return effacerListe(tmp);
    }
}

Et voilà : vous en savez maintenant un peu plus sur ce que sont les listes chaînées. Vous pourrez améliorer ceci en utilisant les listes doublement chaînées, qui sont en fait une liste d'éléments qui pointent à la fois sur l'élément suivant, mais aussi sur l'élément précédent, ce qui vous permet de revenir en arrière plus facilement qu'avec les listes simplement chaînées. Vous pouvez compléter votre bibliothèque avec des fonctions de tri, de recherche de minimum, de maximum et bien d'autre choses...

Passons maintenant à un petit QCM, afin de vérifier que vous avez tout saisi !

Eh bien il semblerait que vous êtes au point. Comme vous avez pu le constater, le choix d'utiliser ou non les listes chaînées est fait lors de l'implémentation de votre algorithme dans un langage. Vous devrez toujours faire des compromis.

J'avais parlé d'introduire les listes doublement chaînées, ce que je vais faire maintenant pour vous permettre d'aller plus loin. L'idée est la suivante : un élément ne va plus se composer d'une valeur et d'une adresse, mais d'une valeur et de deux adresses : l'adresse de l'élément suivant mais aussi l'adresse de l'élément précédent. On pourra tirer avantage de cette spécificité pour lire des listes à l'envers. Avoir l'adresse de l'élément précédent peut simplifier les algorithmes de vos fonctions, mais tout aussi bien les compliquer car c'est maintenant deux pointeurs qu'il faut gérer lors d'un ajout ou d'une suppression.

Nous sommes loin d'avoir codé une bibliothèque complète, mais vos connaissances vous permettent maintenant de continuer seuls et d'implémenter toutes sortes de fonctions.

Merci d'avoir lu ce tutoriel jusqu'au bout. Si une ou plusieurs erreurs s'y sont glissées (ce n'est pas exclu), prévenez-moi par MP.

Je sais que le sujet des listes chainées est souvent abordé lors de l'entrée dans les études supérieures, aussi je serais ravis d'apprendre qu'un professeur vous a redirigé sur mon tutoriel, si tel est le cas n'hésitez pas à me le faire savoir par message !

A bientôt !

L'auteur