.. _c-12-listes-chainees:

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.

.. image:: images/c-12-listes-chainees-fig-01.png
   :width: 25 %
   :alt: Le noeud, structure élémentaire d'une liste chainée
   :align: center

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.

.. image:: images/c-12-listes-chainees-fig-02.png
   :width: 50 %
   :alt: La liste chainée simple
   :align: center

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 :

.. image:: images/c-12-listes-chainees-fig-03.png
   :width: 50 %
   :alt: La liste chainée circulaire
   :align: center

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

.. image:: images/c-12-listes-chainees-fig-04.png
   :width: 50 %
   :alt: La liste chainée circulaire
   :align: center

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 :

.. code-block:: c
    :linenos:

    typedef struct node
    {
    int data;
    struct node *next;
    } 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*.

.. code-block:: c
    :linenos:
    
    Node *head = NULL;
    head = malloc(sizeof(Node));
    head->data = 1;
    head->next = NULL;

Ce code fonctionne de la façon suivante :

#. on déclare le *Node* en l'initialisant à ``NULL`` ;
#. on alloue de la mémoire au *Node* ;
#. on renseigne le champ *data* ;
#. cette liste ne comportant qu'un seul *Node*, le champ *next* pointe vers ``NULL``.

Le programme complet :

.. code-block:: c
    :linenos:

    #include <stdio.h>
    #include <stdlib.h>

    typedef struct node
    {
        int data;
        struct node *next;
    } Node;

    int main()
    {
        Node *head = NULL;

        head = malloc(sizeof(Node));
        head->data = 1;
        head->next = NULL;
        printf("%p head   : (%d, %p)\n", head, head->data, head->next);

        return 0;
    }

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 :

.. image:: images/c-12-listes-chainees-fig-05.png
   :width: 10 %
   :alt: Un noeud unique
   :align: center

Ajout d'un *Node*
-----------------

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

#. déclaration ;
#. allocation de mémoire ;
#. affectation de valeur ;

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

#. le *Node* qui le précède (et doit pointer sur lui) ;
#. et le *Node* qui le suit (``NULL`` si c'est le dernier)


Le programme complet :

.. code-block:: c
    :linenos:

    #include <stdio.h>
    #include <stdlib.h>

    typedef struct node
    {
        int data;
        struct node *next;
    } Node;

    int main()
    {
    Node *head = NULL;
    head = malloc(sizeof(Node));
    head->data = 1;
    head->next = NULL;
    printf("%p head   : (%d, %p)\n", head, head->data, head->next);

    Node *first = NULL;
    first = malloc(sizeof(Node));
    first->data = 1;
    head->next = first;
    first->next = NULL;
    printf("%p head    : (%d, %p)\n", head, head->data, head->next);
    printf("%p first   : (%d, %p)\n", first, first->data, first->next);

        return 0;
    }

L'affichage (dépendant de la machine) ::

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

et la représentation graphique:

.. image:: images/c-12-listes-chainees-fig-06.png
   :width: 20 %
   :alt: Deux noeuds
   :align: center

.. admonition:: 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.

..
    Node *third = NULL;
    third = malloc(sizeof(Node));
    third->data = first->data + second->data;
    second->next = third;
    third->next = NULL;
    printf("%p head    : (%d, %p)\n", head, head->data, head->next);
    printf("%p first   : (%d, %p)\n", first, first->data, first->next);
    printf("%p second  : (%d, %p)\n", second, second->data, second->next);
    printf("%p third  : (%d, %p)\n", third, third->data, third->next);

.. quiz:: quizz-01
    :title: Liste chainée

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

    .. image:: images/c-12-listes-chainees-fig-07.png
        :width: 30 %
        :alt: Trois noeuds
        :align: center

    - Quel est le résultat de l'affichage de ``head->next`` ? :quiz:`{"type":"FB","answer":"12d0", "size":5}`
    - Quel est le résultat de l'affichage de ``head->next->next`` ? :quiz:`{"type":"FB","answer":"22d0", "size":5}`
    - Quel est le résultat de l'affichage de ``head->next->next->next`` ? :quiz:`{"type":"FB","answer":"null", "size":5}`
    - Quel est le résultat de l'affichage de ``head->next->data`` ? :quiz:`{"type":"FB","answer":"1", "size":5}`
    - Quel est le résultat de l'affichage de ``head->next->next->data`` ? :quiz:`{"type":"FB","answer":"2", "size":5}`

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.

.. admonition:: 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[.

    ..
        // return random integer in [rmin:rmax[ range
        int getRandomInteger(int rmin, int rmax)
        {
            return rmin + rand() % (rmax - rmin);
        }

.. admonition:: 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.

    ..
        // List length
        int listLength(Node* head)
        {
        int length = 0;
        Node* current = head;

        while ( current != NULL){
            length++;
            current = current->next;
        }
        return length;
        }

.. admonition:: 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.

    ..
        // display the list
        void printList(Node* head)
        {
            Node* current = head;

            fprintf(stderr, "List = [\n");
            while (current != NULL)
            {
                fprintf(stderr, "node address : %p \t node->data : %2d \t node->next : %p\n", current, current->data, current->next);
                current = current->next;
            }
            fprintf(stderr, "]\n");
        }

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.

.. code-block:: c
    :linenos:

    // Insert Node at first position
    Node* insertNodeAtFirst(Node* head, int data)
    {
        Node* new_node = malloc(sizeof(Node));
        new_node->data = data;
        new_node->next = head;
        return new_node;
    }

.. admonition:: Exercice

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

.. quiz:: quizz-02
    :title: Ajout d'un *Node*

        On considère le code ci dessus.

        - la ligne :quiz:`{"type":"FB","answer":"4", "size":3}` crée le nouveau *Node* à insérer en réservant la mémoire nécessaire ;
        - la ligne :quiz:`{"type":"FB","answer":"5", "size":3}` initialise la donnée du *Node* à insérer ;
        - la ligne :quiz:`{"type":"FB","answer":"6", "size":3}` positionne le *Node* dans la liste.

La fonction :func:`main` mettant en oeuvre la fonction :func:`insertNode AtFirst` est donnée ci dessous.

.. code-block:: c
    :linenos:

        // main()
        int main()
        {

            Node* head;

            int data;
            int nnodes;

            // Build list with insertNodeAtFirst()

            nnodes = 10;
            head = NULL;
            printf("STARTING with an empty list\n");
            for (int n = 0; n < nnodes; n++)
            {
                data = getRandomInteger(1, 50);
                printf("... inserting %3d at first\n", data);
                head = insertNodeAtFirst(head, data);
            }
            printf("DONE\n");
            printList(head);
            printf("length = %d\n", listLength(head));
            fprintf(stderr, "***\n");

            return 0;
        }


.. admonition:: 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.

.. admonition:: Exercice

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

.. admonition:: 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".

    ..
        // Is list empty ?
        int isEmpty(Node* head)
        {
        if ( head == NULL ) return 1;
        return 0;
        }

La fonction :func:`main` mettant en oeuvre l'insertion d'un *Node* en fin de liste est donnée ci dessous.

.. code-block:: c
    :linenos:

        // main()
        int main()
        {

            Node* head;

            int data;
            int nnodes;

            // Build list with insertNodeAtEnd()

            nnodes = 10;
            head = NULL;
            printf("STARTING with an empty list\n");
            for (int n = 0; n < nnodes; n++)
            {
                data = getRandomInteger(1, 50);
                printf("... inserting %3d at end\n", data);
                head = insertNodeAtEnd(head, data);
            }
            printf("DONE\n");
            printList(head);
            printf("length = %d\n", listLength(head));
            fprintf(stderr, "***\n");

            return 0;
        }


.. admonition:: 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 :func:`main` donnée ci dessus.

..
    // insert node at the end of the list
    Node* insertNodeAtEnd(Node* head, int data)
    {

        if ( isEmpty(head) )
        {
            head = malloc(sizeof(Node));
            head->data = data;
            head->next = NULL;
            return head;
        }

        Node* current = head;
        Node* new_node = malloc(sizeof(Node));
        new_node->data = data;

        while (current->next != NULL)
        {
            current = current->next;
        }
        current->next = new_node;
        new_node->next = NULL;
        return head;
    }

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);``

..
    // insert node by index
    Node* insertNodeAtIndex(Node* head, int data, int index)
    {
        if ( index > listLength(head) ) return head;
        
        if ( isEmpty(head) && index == 0 )
        {
            head = malloc(sizeof(Node));
            head->data = data;
            head->next = NULL;
            return head;
        }

        Node* new_node = malloc(sizeof(Node));
        Node* current = head;
        int i = 0;

        while (i < index - 1)
        {
            current = current->next;
            i++;
        }
        new_node->data = data;
        new_node->next = current->next;
        current->next = new_node;
        return head;
    }

..
    // delete node in front of the list
    Node* deleteFirstNode(Node* head){

        if ( isEmpty(head) ){
            return head;
        }

        Node* current = head;
        head = head->next;
        free(current);
        return head;
    }

..
    // delete node at the end of the list
    Node* deleteLastNode(Node* head){

        if ( isEmpty(head) ){
            return head;
        }

        Node* current = head;
        Node* previous;
        while ( current->next != NULL ){
            previous = current;
            current = current->next;
        }

        previous->next = NULL;
        free(current);
        return head;
    }

..
    // delete node by index
    Node* deleteNodeAtIndex(Node* head, int index)
    {
        if ( index > listLength(head) ) return head;
        
        if ( isEmpty(head) ) return head;

        if ( index == 0 ) {
            head = head->next;
            return head;
        }

        Node* current = head;
        Node* previous;
        int i = 0;

        while ( i < index )
        {
            previous = current;
            current = current->next;
            i++;
        }
        previous->next = current->next;
        free(current); 
        return head;
    }