Aller au contenu

Listes Chaînées

Sont traitées dans cette page les notions des CM n°1 et CM n°2.

Listes Simplement Chaînées

Nous voyons ici les principaux algorithmes lors de l'utilisation des listes simplement chaînées vues en L1. Elles sont la base de toutes les notions qui vont suivre.

Structures de bases et parcours

Avant d'implémenter les fonctions...

Afin de comprendre l'implémentation des fonctions qui vont suivre, il est nécessaire d'introduire les structures qui sont la base de notre travail pour les listes simplement chaînées.

Pour définir les types structurés, on utilise la convention d'écriture suivante (employée par Nicolas Flasque) :

  • Si le nom débute par s, il désigne la structure en tant que tel
  • Si le nom débute par t, il désigne le type défini sur cette structure (c'est ce que l'on va utiliser dans nos fonctions)

Structure du maillon

On définit le type t_cell (équivalent à maillon) de la manière suivante :

  • Un champ value pour stocker une valeur
  • Un champ next pour pointer sur la cellule suivante

On peut la représenter de la manière suivante :

Schéma de la structure d'un maillon
Schéma de la structure d'un maillon

Implémentation en langage C 
typedef struct s_cell
{
    int value;
    struct s_cell * next;
} t_cell;

Structure de la liste chaînée

Jusqu’ici, une liste est représentée par un pointeur sur une cellule (maillon), donc t_cell *. À partir de maintenant, une liste est une structure avec un champ head stockant le pointeur.

On peut la représenter de la manière suivante :

Schéma de la structure d'une liste simplement chaînée
Schéma de la structure d'une liste simplement chaînée

Implémentation en langage C 
typedef struct s_std_list
{
    t_cell * head;
} t_std_list

Parcourir une liste simplement chaînée

Pour parcourir la liste simplement chaînée et afficher ses valeurs dans l'ordre, on va définir un curseur qui est pointeur sur la tête de liste afin de lui faire parcourir toute la liste. Le curseur continue d'avancer tant que son adresse est différente de NULL.

Le prototype de la fonction est :

void showStdList(t_std_list list)
Implémentation en langage C 
void showStdList(t_std_list list) {
    t_cell* current = list.head;
    printf("list [head @-]-->");

    if (current == NULL) {
        printf("NULL\n");
        return;
    }

    while (current != NULL) {
        printf("[ %d | @-]-->", current->value);  // utilisez %p au lieu de @- pour imprimer l'adresse réelle
        current = current->next;
    }

    printf("NULL\n");
}

Fonctions d'ajout

Que va-t-on faire ?

Nous allons commencer par les fonctions d'ajout dans la liste simplement chaînée. En débutant par la création d'un maillon à partir d'une valeur, puis en ajoutant ce maillon dans la liste.

Création d'un maillon

L'idée de cette fonction est tout simplement de concentrer les actions suivantes :

  • Mise à jour de la valeur value
  • Affectation de l'adresse NULL au pointeur next

Le prototype de la fonction est : 

t_cell *createCell(int val)

Implémentation en langage C 
t_cell *createCell(int val)
{
    t_cell *p_res = NULL;

    p_res = malloc(1 * sizeof(t_cell));

    if (p_res == NULL){ // (1)!
        return NULL;
    }

    p_res->value = val;
    p_res->next = NULL;

    return p_res;
}
  1. On vérifie si la fonction malloc a réussi à allouer de la mémoire dynamiquement pour créer une nouvelle cellule (t_cell). Dans ce cas on retourne l'adresse NULL.

Chaînage en tête de liste

On souhaite écrire une fonction pour ajouter (chaîner) une cellule en tête de liste. Cette fonction modifie la liste = elle modifie l'adresse de la première cellule. On doit donc lui transmettre un pointeur vers cette liste.

On peut représenter le chaînage en tête de la manière suivante :

Schéma du chaînage en tête
Schéma du chaînage en tête

Son prototype est :

void addHeadStd(t_std_list *p_list, int val)
Implémentation en langage C 
void addHeadStd(t_std_list *p_list, int val)
{
    t_cell *newcell;
    newcell = createCell(val);

    newcell->next = p_list->head; // (1)!
    p_list->head = newcell; // (2)!

    return;
}
  1. L'adresse next du maillon que l'on veut insérer est celle de l'actuelle tête de la liste.
  2. On n'oublie pas de mettre à jour l'adresse de la tête ! Ici c'est celle du maillon inséré.

Chaînage en queue de liste

On souhaite écrire une fonction pour ajouter (chaîner) une cellule en queue de liste. Cette fonction modifie la liste (= elle modifie l'adresse de la première cellule) si la liste est vide. On doit donc lui transmettre un pointeur vers cette liste.

On peut représenter le chaînage en queue de la manière suivante :

Schéma du chaînage en queue
Schéma du chaînage en queue

Le prototype de la fonction est :

void addTailStd(t_std_list *p_list, int val)
Implémentation en langage C 
void addTailStd(t_std_list *p_list, int val)
{
    t_cell *newcell;
    newcell = createCell(val);

    if (p_list->head == NULL) // (1)!
    {
        p_list->head = newcell;
    }
    else // (2)!
    {
        t_cell *cur = p_list->head;
        while (cur->next != NULL)
        {
            cur = cur->next;
        }
        cur->next = newcell;
    }
}
  1. Si la liste est vide, il suffit de positionner la tête sur le maillon créé
  2. Sinon, on parcourt la liste à l'aide d'un pointeur temporaire et on indique que le dernier maillon de la liste est relié au nouveau maillon

Fonctions de suppression

Suppression en tête de liste

On souhaite écrire une fonction pour supprimer la cellule en tête de liste. Cette fonction modifie la liste en mettant à jour l'adresse de la première cellule. Si la liste est vide, il n'y a rien à faire.

Le prototype de la fonction est :

void removeHeadStd(t_std_list *list)
Implémentation en langage C 
void removeHeadStd(t_std_list *list)
{
    if (list->head == NULL) // (1)!
    {
        return;
    }
    else
    {
        t_cell* cur = list->head;
        list->head = list->head->next; // (2)!
        free(cur); // (3)!
    }
}
  1. Si la liste est vide, alors il n'y a pas de cellule à supprimer, on termine la fonction.
  2. On met à jour la tête de la liste en pointant vers la cellule suivante.
  3. On libère la mémoire occupée par l'ancienne tête de la liste.

Suppression en queue de liste

On souhaite écrire une fonction pour supprimer la cellule en queue de liste. Cette fonction modifie la liste en supprimant la dernière cellule. Si la liste est vide, il n'y a rien à faire.

Le prototype de la fonction est :

void removeTailStd(t_std_list *list)
Implémentation en langage C 
void removeTailStd(t_std_list *list)
{
    if (list->head == NULL) // (1)!
    {
        return;
    }
    else
    {
        t_cell *cur = list->head; // (2)!
        t_cell *prev = list->head; // (3)!
        while(cur->next != NULL)
        {
            prev = cur;
            cur = cur->next;
        }
        prev->next = NULL; // (4)!
        free(cur); // (5)!
    }
}
  1. Si la liste est vide, alors il n'y a pas de cellule à supprimer, on termine la fonction.
  2. Ce curseur (cur) parcourt la liste jusqu'à atteindre la dernière cellule.
  3. Ce second curseur (prev) permet de garder une référence à l'avant-dernier maillon, celui qui deviendra le dernier après la suppression.
  4. On met à jour le champ next de l'avant-dernier maillon pour qu'il pointe vers NULL, signifiant la fin de la liste.
  5. On libère la mémoire occupée par la dernière cellule.

Cas général de la suppression

On souhaite écrire une fonction pour supprimer une cellule quelconque dans une liste chaînée, en fonction d'une valeur donnée. Cette fonction parcourt la liste pour trouver la cellule à supprimer, puis met à jour les liens entre les cellules.

Son prototype est :

void removeValStd(t_std_list *list, int val)
Implémentation en langage C 
void removeValStd(t_std_list *list, int val)
{
    if (list->head == NULL) //(1)!
    {
        return;
    }

    t_cell *cur = list->head; //(2)!
    t_cell *prev = NULL; //(3)!

    while (cur != NULL && cur->val != val) //(4)!
    {
        prev = cur;
        cur = cur->next;
    }

    if (cur == NULL) //(5)!
    {
        return; // Valeur non trouvée
    }

    if (prev == NULL) //(6)!
    {
        p_list->head = cur->next; // La tête doit être supprimée
    }
    else
    {
        prev->next = cur->next; // Relie le précédent au suivant
    }

    free(cur); //(7)!
}
  1. Si la liste est vide, il n'y a rien à supprimer, donc on arrête la fonction.
  2. Le pointeur cur parcourt la liste pour localiser la cellule à supprimer.
  3. Le pointeur prev garde une trace de la cellule précédente, afin de pouvoir mettre à jour son lien next.
  4. On parcourt la liste jusqu'à trouver la cellule contenant la valeur recherchée, ou jusqu'à la fin de la liste.
  5. Si on atteint la fin de la liste sans trouver la valeur, la fonction se termine.
  6. Si la cellule à supprimer est la tête, on met à jour la tête de la liste. Sinon, on lie la cellule précédente à celle qui suit la cellule supprimée.
  7. Enfin, on libère la mémoire de la cellule supprimée.

Listes Head & Tail

Structures de bases et parcours

Structure de la liste HT

Les maillons utilisés pour cette listes sont les mêmes que définis dans la partie précédente. Cette fois, la structure de la liste HT contient deux pointeurs : on garde le pointeur head qui pointera vers la tête de la liste, et on ajoute un pointeur sur cellule tail qui pointera sur le dernier élément de la liste.

On peut la représenter de la manière suivante :

Schéma de la structure d'une liste Head & Tail
Schéma de la structure d'une liste Head & Tail

Implémentation en langage C 
typedef struct s_ht_list
{
    t_cell * head;
    t_cell * tail;
} t_ht_list

Parcours d'une liste HT

L'algorithme de parcours d'une liste Head & Tail est le même que pour une liste simplement chaînée. Il faut simplement faire attention à bien mettre à jour le type impliqué dans la fonction, on passe d'une t_std_list à une t_ht_list.

void showHTList(t_ht_list list)

Vérifier qu'une valeur est présente dans une liste HT

Nous cherchons à écrire une fonction qui doit indiquer si une certaine valeur entière est stockée dans une liste donnée en paramètre. Elle renvoie 1 si la valeur est présente, et 0 sinon.

Le prototype de la fonction est :

int isValInHtList(t_ht_list, int);
Implémentation en langage C 
int isValInHtList(t_ht_list list, int val)
{
    t_cell *temp = list.head;
    int found = 0;

    while ((temp != NULL) && (val != temp->value))
    {
        temp = temp->next;
    }

    if (temp != NULL)
    {
        found = 1;
    }

    return found;
}

Fonctions d'ajout

Chaînage en queue de liste

Cette fonction modifie la liste car la valeur de tail va changer mais la valeur de head peut également être modifiée si la liste est vide. On doit donc lui transmettre un pointeur vers cette liste.

Le prototype de la fonction est :

void addTailHt(t_ht_list *p_list, int val)
Implémentation en langage C 
void addTailHt(t_ht_list *p_list, int val)
{
    t_cell *new = createCell(val);

    if (p_list->head == NULL) //(1)!
    {
        p_list->head = new;
        p_list->tail = new;
    }
    else //(2)!
    {
        p_list->tail->next = new;
        p_list->tail = new;
    }

    return;
}
  1. Si la liste est vide, il suffit de positionner la tête et la queue sur le maillon créé
  2. Sinon, on chaîne le maillon créé à l'adresse suivante de la queue actuelle de la liste, puis on déplace la queue sur ce nouveau maillon chaîné.

Cas général de l'insertion

On dispose d'une t_ht_list (potentiellement vide) dont les éléments sont classés par ordre croissant. On souhaite y ajouter une nouvelle cellule (avec une certaine valeur) de manière à ce que les éléments de la liste soient toujours bien triés.

On distingue 3 cas :

  • La liste est vide
  • La liste n'est pas vide et on doit insérer la nouvelle cellule avant la fin
  • La liste n'est pas vide et on doit insérer la nouvelle cellule à la fin

Premier point : Comment repérer qu'une liste est vide ?

→ On dispose d'une fonction int isEmpty(t_ht_list); pour ce test.

Deuxième point : Comment savoir où insérer la nouvelle cellule ? (dans la liste triée)

→ Tant que sa valeur est plus grande que la valeur de la cellule courante

Troisième point : Comment savoir si on doit insérer dans la liste ou à la fin ?

→ Si on a parcouru toute la liste sans trouver de valeur plus grande, on doit insérer à la fin

Le prototype de la fonction est :

void insertOrderedHtList(t_ht_list *p_htlist, int val)
Implémentation en langage C 
void insertOrderedHtList(t_ht_list *p_htlist, int val)
{
    t_cell *newcell, *temp, *prev;
    newcell = createCell(val);

    if (isEmptyHtList(*p_htlist))
    {
        p_htlist->head = p_htlist->tail = newcell;  
    }
    else
    {
        temp = p_htlist->head;
        prev = temp;

        while ((temp !=NULL)&&(temp->value < newcell->value))
        {
            prev = temp;
            temp = temp->next;
        }

        if (prev == temp)
        {
            newcell->next = p_htlist->head,
            p_htlist->head = newcell;
        }
        else
        {
            prev->next = newcell;
            newcell->next = temp;

            if (temp==NULL)
            {
                p_htlist->tail = newcell;  
            }
        }
    }
}

Fonctions de suppression

Cas général de la suppression

On cherche à écrire une fonction qui supprime une valeur donnée en paramètre dans une liste HT. Dans cette fonction, on va commencer par appeler la fonction isValInHtList() pour savoir s’il y a bien une cellule à supprimer (donc pas besoin de tester le cas où la liste est vide). Nous allons parcourir la liste et aurons besoin, comme pour une liste simplement chaînée, de deux pointeurs temp et prev.

Le prototype de la fonction est :

void removeValFromHtList(t_ht_list *p_list, int val)
Implémentation en langage C 
void removeValFromHtList(t_ht_list *p_list, int val)
{
    t_cell * temp, prev;

    if (isValInHtList(*p_list, val)==0)
    {
        return;
    }

    temp = p_list->head;
    prev = temp;

    while ((temp != NULL)&&(temp->value != val))
    {
        prev = temp;
        temp = temp->next;
    }

    if (temp == p_list->head) //(1)!
    {
        p_list->head = p_list->head->next;


        if (p_list->head == NULL) //(2)!
        {
            p_list->tail == NULL;
        }
    }
    else
    {
        prev->next = temp->next;

        if (temp == p_list->tail) //(3)!
        {
            p_list->tail = prev;
        }
    }

}
  1. S'il s'agit de la tête de la liste.
  2. S'il s'agissait de la seule cellule de la liste.
  3. S'il s'agit de la queue de la liste.

Listes Circulaires

Structures de bases et parcours

Structure de la liste circulaire

Une liste chaînée circulaire, dont le type est t_circ_list, n'est rien de plus qu'une liste HT t_ht_list (puisqu'on stocke l'adresse de la première cellule et que la dernière doit la pointer). Il faut juste faire attention à ce que la dernière cellule pointe sur la première, au lieu de pointer sur NULL.

On peut la représenter de la manière suivante :

Schéma de la structure d'une liste circulaire avec un élément
Schéma de la structure d'une liste circulaire avec un élément

On se contente, pour définir ce type, de :

typedef t_ht_list t_circ_list;

Créer une liste circulaire vide

On souhaite écrire une fonction qui permet de créer une liste circulaire vide, c'est-à-dire créer simplement une liste HT en faisant attention à bien mettre à jour le type.

Le prototype de la fonction est :

t_circ_list createEmptyCircList()
Implémentation en langage C 
t_circ_list createEmptyCircList()
{
    t_circ_list cl;
    cl.head = NULL;
    cl.tail = NULL;

    return cl;
}

Afficher une liste circulaire

On cherche à rédiger une fonction qui affiche les valeurs stockées dans une liste chaînée circulaire, de la première à la dernière sous la forme suivante :

  • Une liste vide doit afficher []
  • Une liste non vide (imaginons ici une liste à 3 valeurs) doit afficher [val1 | val2 | val3](forever)

Le prototype de la fonction est :

void displayCList(t_circ_list clist)
Implémentation en langage C 
void displayCList(t_circ_list clist)
{
    t_cell *temp;
    if (clist.head == NULL)
    {
        printf("[]");
    }
    else 
    {
        temp = clist.head;
        printf("[");
        while (temp != clist.tail)
        {
            printf("%d|", temp->value);
            temp = temp->next; 
        }
        printf("%d](forever)",clist.tail->value);
    }
    testprintf("\n");
    return;
}

Fonctions d'ajout

Chaînage en tête de liste

On souhaite écrire une fonction pour insérer une cellule en tête de liste chaînée circulaire, cellule qui stockera un entier int passé en paramètre.

La fonction ne comporte que deux cas distincts à traiter :

  • La liste est vide
  • La liste n’est pas vide Il faudra par contre être attentif à ce que la liste reste bien circulaire (la dernière pointe sur la première)

Le prototype de la fonction est :

void addHeadCircList(t_circ_list *p_cl, int value)
Implémentation en langage C 
void addHeadCircList(t_circ_list *p_cl, int value)
{
    t_cell *nouv = createCell(value);
    if (p_cl->head == NULL)
    {
        p_cl->head = p_cl->tail = nouv;
        p_cl->tail->next = p_cl->head;
    }
    else
    {
        nouv->next = p_cl->head;
        p_cl->head = nouv;
        p_cl->tail->next = p_cl->head;
    }

    return;
}

Fonctions de suppression

Cas général de la suppression

On cherche à écrire une fonction dont le rôle est de supprimer, si elle existe, la première occurrence de la cellule stockant la valeur val (deuxième paramètre), dans une liste dont on à l’adresse (pointeur) en premier paramètre.

On peut représenter le cas général de la suppression de la manière suivante :

Schéma de la suppression d'un élément dans une liste circulaire
Schéma de la suppression d'un élément dans une liste circulaire

Le prototype de la fonction est :

void removeCellCircList(t_cir_list * p_list, int val)
Implémentation en langage C 
void removeCellCircList(t_cir_list * p_list, int val)
{ 
    // liste vide
    if (NULL == p_list->head) {
        return;      
    }

    // si la liste contient 1 seule cellule
    if (p_list->head == p_list->tail && p_list->head->value == val){
        free(p_list->head);
        p_list->head = p_list->tail = NULL;
        return;
    }

    // parcours de la liste contenant au moins 2 cellules.
    t_cell * temp = NULL;
    t_cell * prev = NULL;
    temp = prev = p_list->head;

    // on avance dans la liste tant que la cellule n’est pas la
    // dernière et que sa valeur n’est pas celle recherchée
    while ((temp->next != p_list->head) && (temp->value != val)){
        prev = temp;
        temp = temp->next;
    }

    // on a trouvé la cellule (sauf si c’est la dernière)
    if (temp->value == val){
        // si c’est la première : head et tail à modifier
        if (temp == p_list->head){
            p_list->head = p_list->head->next;
            p_list->tail->next = p_list->head;
        }
        else {
            prev->next = temp->next;
        }
    }

    // si la val est trouvée dans la dernière cellule 
    if (p_list->tail->value == val){
        prev->next = temp->next;
        p_list->tail = prev;
    }

    // dans tous les cas, il faut libérer la cellule trouvée p
    // elle est pointée par temp
    if (temp->value == val){
        free(temp);
        // INUTILE car variable locale temp = temp→next = NULL;
    }
}

Suppression en queue de liste

On cherche à écrire une fonction dont le rôle est de supprimer la dernière cellule (c’est-à-dire celle en queue de liste) d'une liste circulaire dont l’adresse est passée en premier paramètre. La liste peut être vide, contenir une seule cellule, ou plusieurs cellules.

On peut représenter le cas de la suppression en queue de liste de la manière suivante :

Schéma de la suppression de la queue dans une liste circulaire
Schéma de la suppression de la queue dans une liste circulaire

Le prototype de la fonction est :

void removeTailCircList(t_cir_list * p_list)
Implémentation en langage C 
void removeTailCircList(t_cir_list * p_list)
{
    // liste vide
    if (NULL == p_list->head) {
        return;
    }

    // si la liste contient 1 seule cellule
    if (p_list->head == p_list->tail) {
        free(p_list->head);
        p_list->head = p_list->tail = NULL;
        return;
    }

    // suppression de la queue
    t_cell * temp = p_list->tail;
    t_cell * prev = p_list->head;

    // on parcourt la liste pour trouver l'avant-dernier élément
    while (prev->next != p_list->tail) {
        prev = prev->next;
    }

    // mise à jour des pointeurs
    prev->next = p_list->head;
    p_list->tail = prev;

    // libération de la cellule
    free(temp);
}

Listes Doublement Chaînées

À venir...