CPGE OUJDA                                                                        SPE       

Les listes chaînées

Lorsque vous créez un algorithme utilisant des conteneurs, il existe différentes manières de les implémenter, la façon la plus courante étant les tableaux, que vous connaissez tous. Lorsque vous créez un tableau, les éléments de celui-ci sont placés de façon contiguë en mémoire. Pour pouvoir le créer, il vous faut connaître sa taille. Si vous voulez supprimer un élément au milieu du tableau, il vous faut recopier les éléments temporairement, ré-allouer de la mémoire pour le tableau, puis le remplir à partir de l'élément supprimé. En bref, ce sont beaucoup de manipulations coûteuses en ressources.
Une liste chaînée est différente dans le sens où les éléments de votre liste sont répartis dans la mémoire et reliés entre eux par des pointeurs. Vous pouvez ajouter et enlever des éléments d'une liste chaînée à n'importe quel endroit, à n'importe quel instant, sans devoir recréer la liste entière.
Nous allons essayer de voir ceci plus en détail sur ces schémas :

Image utilisateur

Vous avez sur ce schéma la représentation que l'on pourrait faire d'un tableau et d'une liste chaînée. Chacune de ces représentations possède ses avantages et inconvénients. C'est lors de l'écriture de votre programme que vous devez vous poser la question de savoir laquelle des deux méthodes est la plus intéressante.

Chaque élément d'une liste chaînée est composé de deux parties :

Image utilisateur

Déclaration en C d'une liste chaînée 

1
 2
 3
 4
 5
 6
 7
 8
 9
10
 
#include <stdlib.h>
 
typedef struct element element;
struct element
{
    int val;
    struct element *nxt;
};
 
typedef element* llist;

On crée le type element qui est une structure contenant un entier (val) et un pointeur sur élément (nxt), qui contiendra l'adresse de l'élément suivant. Ensuite, il nous faut créer le type llist (pour linked list = liste chaînée) qui est en fait un pointeur sur le type element. Lorsque nous allons déclarer la liste chaînée, nous devrons déclarer un pointeur sur element, l'initialiser à NULL, pour pouvoir ensuite allouer le premier élément. N'oubliez pas d'inclure stdlib.h afin de pouvoir utiliser la macro NULL. Comme vous allez le constater, nous avons juste crée le type llist afin de simplifier la déclaration.
Voilà comment déclarer une liste chaînée (vide pour l'instant) :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
 
 
#include <stdlib.h>
 
typedef struct element element;
struct element
{    int val;
    struct element *nxt;
};
 typedef element* llist;
   int main(int argc, char **argv)
{
    /* Déclarons 3 listes chaînées de façons différentes mais équivalentes */
    llist ma_liste1 = NULL;
    element *ma_liste2 = NULL;
    struct element *ma_liste3 = NULL;
     return 0;
}

Il est important de toujours initialiser la liste chaînée à NULL. Le cas échéant, elle sera considérée comme contenant au moins un élément. C'est une erreur fréquente. A garder en mémoire donc. De manière générale, il est plus sage de toujours initialiser vos pointeurs.

Manipuler les listes chaînées

Ajouter en tête

Lors d'un ajout en tête, nous allons créer un élément, lui assigner la valeur que l'on veut ajouter, puis pour terminer, raccorder cet élément à la liste passée en paramètre. Lors d'un ajout en tête, on devra donc assigner à nxt l'adresse du premier élément de la liste passé en paramètre. Visualisons tout ceci sur un schéma :

Image utilisateur

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
 
llist ajouterEnTete(llist liste, int valeur)
{
    /* On crée un nouvel élément */
    element* nouvelElement = malloc(sizeof(element));
 
    /* On assigne la valeur au nouvel élément */
    nouvelElement->val = valeur;
     /* On assigne l'adresse de l'élément suivant au nouvel élément */
    nouvelElement->nxt = liste;
 
    /* On retourne la nouvelle liste, i.e. le pointeur sur le premier élément */
    return nouvelElement;
}

C'est l'ajout le plus simple des deux. Il suffit de créer un nouvel élément puis de le relier au début de la liste originale. Si l'original est , (vide) c'est NULL qui sera assigne au champ nxt du nouvel element. La liste contiendra dans ce cas-là un seul élément.

Ajouter en fin de liste

Cette fois-ci, c'est un peu plus compliqué. Il nous faut tout d'abord créer un nouvel élément, lui assigner sa valeur, et mettre l'adresse de l'élément suivant à NULL. En effet,, comme cet élément va terminer la liste nous devons signaler qu'il n'y a plus d'élément suivant. Ensuite, il faut faire pointer le dernier élément de liste originale sur le nouvel élément que nous venons de créer. Pour ce faire, il faut créer un pointeur temporaire sur element qui va se déplacer d'élément en élément, et regarder si cet élément est le dernier de la liste. Un élément sera forcément le dernier de la liste si NULL est assigné à son champ nxt.

Image utilisateur

 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
 
llist ajouterEnFin(llist liste, int valeur)
{
    /* On crée un nouvel élément */
    element* nouvelElement = malloc(sizeof(element));
 
    /* On assigne la valeur au nouvel élément */
    nouvelElement->val = valeur;
 
    /* On ajoute en fin, donc aucun élément ne va suivre */
    nouvelElement->nxt = NULL;
 
    if(liste == NULL)
    {
        /* Si la liste est videé il suffit de renvoyer l'élément créé */
        return nouvelElement;
    }
    else
    {
        /* Sinon, on parcourt la liste à l'aide d'un pointeur temporaire et on
        indique que le dernier élément de la liste est relié au nouvel élément */
        element* temp=liste;
        while(temp->nxt != NULL)
        {
            temp = temp->nxt;
        }
        temp->nxt = nouvelElement;
        return liste;
    }
}


Comme vous pouvez le constater, nous nous déplaçons le long de la liste chaînée grâce au pointeur temp. Si l'élément pointé par temp n'est pas le dernier (temp->nxt != NULL), on avance d'un cran (temp = temp->nxt) en assignant à temp l'adresse de l'élément suivant. Une fois que l'on est au dernier élément, il ne reste plus qu'à le relier au nouvel élément.
Si vous pensez avoir bien saisi ces deux fonctions, je vous invite à passer à la partie suivante, dans laquelle je vais vous proposer quelques exercices. Le premier sera fondamental puisqu'il nous permettra d'afficher le contenu d'une liste chaînée.

 

M Naji