Listes chainées

Le tableau est une structure de données extrêmement répandue en C.

  • son principal avantage est d’être une structure ordonnée, placée dans une zone mémoire contigüe, permettant un accès direct, et donc très rapide, à chacun de ses éléments par indexation avec la syntaxe tab[i];

  • son principal inconvénient est que le caractère contigü de la zone mémoire rend coûteux les opérations d’insertion et de suppression de nouvelles données puisqu’il faut créer un nouveau tableau à chaque opération de ce type et recopier les valeurs du tableau original dans ce nouveau tableau.

Une structure de données plus souple est la liste chainée :

  • les opérations d’insertion, suppression, déplacement des données sont facilitées

  • MAIS elle ne permet pas l’accès par indexation directe (il faut parcourir la liste séquentiellement pour accéder à la donnée recherchée).

L’élément constitutif d’une liste chainée est le noeud (node) qui comporte :

  • un (ou plusieurs) champ pour la donnée ;

  • et un champ contenant l’adresse du noeud suivant.

Pour ce qui suit, dans un souci de simplification, la donnée sera représentée par un nombre entier.

Le noeud, structure élémentaire d'une liste chainée

On peut utiliser ce node pour construire une liste chainée simple pour laquelle chacun de ces node est relié au suivant par un pointeur.

La liste chainée simple

Dans ce type de liste chainée :

  • on ne la parcoure que dans un seul sens ;

  • chaque node possède un pointeur vers le noeud suivant ;

  • le début est identifié par un pointeur vers le premier node ;

  • la fin est identifiée par un pointeur vers null.

Il existe des variations de cette liste chainée simple.

La liste chainée circulaire permet d’atteindre tous les node, quel que soit le point d’entrée :

La liste chainée circulaire

La liste chainée double implémente les parcours direct et inverse :

La liste chainée circulaire

Pour la suite, pour des raisons de simplicité, on ne traitera que la liste chainée simple.

Création d’un Node

Un Node se déclare sous forme de structure. L’utilisation de typedef facilite la réutilisation ultérieure :

1typedef struct node
2{
3int data;
4struct node *next;
5} Node;

Le premier champ (ligne 3) représente la donnée stockée par le Node et le second (ligne 4) un pointeur vers le Node suivant.

Bien que ce ne soit pas du tout efficace pour des structures comportant beaucoup de données, pour illustrer rapidement et simplement l’utilisation, on peut définir « manuellement » les Node.

1Node *head = NULL;
2head = malloc(sizeof(Node));
3head->data = 1;
4head->next = NULL;

Ce code fonctionne de la façon suivante :

  1. on déclare le Node en l’initialisant à NULL ;

  2. on alloue de la mémoire au Node ;

  3. on renseigne le champ data ;

  4. cette liste ne comportant qu’un seul Node, le champ next pointe vers NULL.

Le programme complet :

 1#include <stdio.h>
 2#include <stdlib.h>
 3
 4typedef struct node
 5{
 6    int data;
 7    struct node *next;
 8} Node;
 9
10int main()
11{
12    Node *head = NULL;
13
14    head = malloc(sizeof(Node));
15    head->data = 1;
16    head->next = NULL;
17    printf("%p head   : (%d, %p)\n", head, head->data, head->next);
18
19    return 0;
20}

L’affichage à la forme suivante. Les adresses dépendent de la machine utilisée

0x7fffe147a2a0 head   : (1, (nil))

L’information s’interprète de la façon suivante :

  • le Node est placé à l’adresse 0x7fffe147a2a0 ;

  • le champ data contient la valeur 1 ;

  • ce Node ne pointe sur rien (NULL ou nil).

Ceci est résumé dans la figure suivante :

Un noeud unique

Ajout d’un Node

Pour ajouter un Node, on réitère l’opération de création :

  1. déclaration ;

  2. allocation de mémoire ;

  3. affectation de valeur ;

puis le Node est inséré en définissant :

  1. le Node qui le précède (et doit pointer sur lui) ;

  2. et le Node qui le suit (NULL si c’est le dernier)

Le programme complet :

 1#include <stdio.h>
 2#include <stdlib.h>
 3
 4typedef struct node
 5{
 6    int data;
 7    struct node *next;
 8} Node;
 9
10int main()
11{
12Node *head = NULL;
13head = malloc(sizeof(Node));
14head->data = 1;
15head->next = NULL;
16printf("%p head   : (%d, %p)\n", head, head->data, head->next);
17
18Node *first = NULL;
19first = malloc(sizeof(Node));
20first->data = 1;
21head->next = first;
22first->next = NULL;
23printf("%p head    : (%d, %p)\n", head, head->data, head->next);
24printf("%p first   : (%d, %p)\n", first, first->data, first->next);
25
26    return 0;
27}

L’affichage (dépendant de la machine)

0x7fffd78102a0 head    : (1, 0x7fffd78112d0)
0x7fffd78112d0 first   : (1, (nil))

et la représentation graphique:

Deux noeuds

Exercice

Ecrire les lignes de code permettant d’ajouter un troisième Node de valeur la somme des deux précédents à la liste chaînée. Exécuter le code. Dessiner schématiquement le résultat obtenu sur votre machine.

On considère la liste chainée ci dessous.

Trois noeuds

  • Quel est le résultat de l’affichage de head->next ?

  • Quel est le résultat de l’affichage de head->next->next ?

  • Quel est le résultat de l’affichage de head->next->next->next ?

  • Quel est le résultat de l’affichage de head->next->data ?

  • Quel est le résultat de l’affichage de head->next->next->data ?

L’ajout « manuel » n’est évidemment pas une solution et la bonne méthode est de factoriser les opérations nécessaires dans une fonction.

Ajout d’un Node en tête de liste

Avant de commencer à traiter l’insertion d’un Node en tête de liste, quelques fonctions utilitaires vont nous faciliter le travail.

Exercice

Pour pouvoir insérer des données aléatoires dans la liste chainée, il serait pratique de disposer d’une fonction ad-hoc. Ecrire la fonction de prototype int getRandomInteger(int rmin, int rmax); permettant de retourner un nombre aléatoire dans l’intervalle [rmin:rmax[.

Exercice

Pour connaitre facilement la taille d’une liste chainée, il serait pratique de disposer d’une fonction de prototype int listLength(Node* head); permettant de retourner la longueur d’une liste définie par son noeud de tête. Ecrire le code de cette fonction.

Pour ce faire, se rappeler que la fin d’une liste est définie par NULL et tant que la fin n’est pas atteinte, il faut continuer à traverser la liste en comptant le nombre de Node rencontrés.

Exercice

Pour afficher simplement le contenu d’une liste chainée, il serait pratique de disposer d’une fonction de prototype void printList(Node* head); permettant d’afficher pour chaque Node :

  • son adresse ;

  • la valeur de la donnée ;

  • l’adresse du Node vers lequel il pointe.

Ecrire le code de cette fonction en reprenant le principe de traversée de liste utilisé à l’exercice précédent.

Examinons maintenant le processus d’ajout d’un Node en tête de liste. Intuitivement, on comprend bien qu’il va falloir :

  • créer le nouveau Node à insérer ;

  • l’initialiser ;

  • et modifier la structure de la liste.

Ces opérations sont implémentées par le code ci dessous.

1// Insert Node at first position
2Node* insertNodeAtFirst(Node* head, int data)
3{
4    Node* new_node = malloc(sizeof(Node));
5    new_node->data = data;
6    new_node->next = head;
7    return new_node;
8}

Exercice

Représenter graphiquement l’opération d’ajout d’un Node en tête d’une liste existante.

On considère le code ci dessus.

  • la ligne crée le nouveau Node à insérer en réservant la mémoire nécessaire ;

  • la ligne initialise la donnée du Node à insérer ;

  • la ligne positionne le Node dans la liste.

La fonction main() mettant en oeuvre la fonction insertNode AtFirst() est donnée ci dessous.

 1    // main()
 2    int main()
 3    {
 4
 5        Node* head;
 6
 7        int data;
 8        int nnodes;
 9
10        // Build list with insertNodeAtFirst()
11
12        nnodes = 10;
13        head = NULL;
14        printf("STARTING with an empty list\n");
15        for (int n = 0; n < nnodes; n++)
16        {
17            data = getRandomInteger(1, 50);
18            printf("... inserting %3d at first\n", data);
19            head = insertNodeAtFirst(head, data);
20        }
21        printf("DONE\n");
22        printList(head);
23        printf("length = %d\n", listLength(head));
24        fprintf(stderr, "***\n");
25
26        return 0;
27    }

Exercice

Rassembler les bouts de code ci dessus dans un seul fichier. Compiler, exécuter et observer attentivement le résultat. Les Node ont ils bien été ajoutés à chaque fois en tête de la liste ?

Ajout d’un Node en fin de liste

Dans le cas général, ajouter un Node à la fin de la liste revient à traverser (parcourir) la liste, détecter le dernier élément, et enfin insérer le Node entre lui et le Node NULL. Dans le cas particulier de la liste vide, on peut remarquer qu’ajouter un noeud en tête ou en fin de liste est similaire.

Exercice

Représenter graphiquement cette opération, et en particulier ce qui se passe pour le dernier Node.

Exercice

Ajouter un Node en fin de liste nécessite de traiter le cas particulier de la liste vide. Pour ce faire écrire une fonction de prototype int isEmpty(Node* head); retournant la vérité de « la liste débutant par head est vide ».

La fonction main() mettant en oeuvre l’insertion d’un Node en fin de liste est donnée ci dessous.

 1    // main()
 2    int main()
 3    {
 4
 5        Node* head;
 6
 7        int data;
 8        int nnodes;
 9
10        // Build list with insertNodeAtEnd()
11
12        nnodes = 10;
13        head = NULL;
14        printf("STARTING with an empty list\n");
15        for (int n = 0; n < nnodes; n++)
16        {
17            data = getRandomInteger(1, 50);
18            printf("... inserting %3d at end\n", data);
19            head = insertNodeAtEnd(head, data);
20        }
21        printf("DONE\n");
22        printList(head);
23        printf("length = %d\n", listLength(head));
24        fprintf(stderr, "***\n");
25
26        return 0;
27    }

Exercice

Ecrire la fonction de prototype Node* insertNodeAtEnd(Node* head, int data); insérant un Node à la fin de la liste définie par head et retournant un pointeur vers la tête de la nouvelle liste. Tester cette fonction à partir de la fonction main() donnée ci dessus.

Autres opérations sur les listes

Il existe un grand nombre d’opérations possibles sur les listes. A titre d’exercice, écrivez les fonctions suivantes :

  • une fonction permettant d’insérer un Node à une position donnée dans la liste et retournant un pointeur vers la tête de la nouvelle liste. Le prototype : Node* insertNodeAtIndex(Node* head, int data, int index); ;

  • une fonction permettant de supprimer le Node en tête de liste et retournant un pointeur vers la tête de la nouvelle liste. Le prototype : Node* deleteFirstNode(Node* head); ;

  • une fonction permettant de supprimer le Node en fin de liste et retournant un pointeur vers la tête de la nouvelle liste. Le prototype : Node* deleteLastNode(Node* head); ;

  • une fonction permettant de supprimer le Node à une position donnée dans la liste et retournant un pointeur vers la tête de la nouvelle liste. Le prototype : Node* deleteNodeAtIndex(Node* head, int index);