Implémentez une liste doublement chaînée en C | Tutoriel de programmation

Introduction

Dans ce projet, vous allez apprendre à implémenter une structure de données de liste doublement chaînée en C. Une liste doublement chaînée est un type de liste chaînée où chaque nœud contient des pointeurs vers son prédécesseur et son successeur, permettant une traversée efficace dans les deux directions, vers l'avant et vers l'arrière.

👀 Aperçu

$ gcc test_list.c list.c -o test
$./test
welcome
to
labex
online

🎯 Tâches

Dans ce projet, vous allez apprendre :

Comment initialiser une liste doublement chaînée
Comment traverser la liste doublement chaînée et exécuter une fonction de rappel pour chaque nœud
Comment insérer un nouveau nœud après un nœud donné dans la liste doublement chaînée
Comment insérer un nouveau nœud avant un nœud donné dans la liste doublement chaînée
Comment supprimer un nœud de la liste doublement chaînée

🏆 Réalisations

Après avoir terminé ce projet, vous serez capable de :

Comprendre la structure et les opérations de base d'une liste doublement chaînée
Implémenter les fonctions clés requises pour gérer une liste doublement chaînée
Monter en évidence la capacité à travailler avec des pointeurs et l'allocation dynamique de mémoire en C
Appliquer vos connaissances pour corriger et améliorer l'implémentation de liste doublement chaînée fournie

Correction des fautes de segmentation

Dans cette étape, la fonction free_list ne met pas à jour le pointeur current après avoir libéré un nœud, ce qui entraînera une erreur de segmentation. Le problème doit maintenant être corrigé.

Localisez la fonction free_list() dans le fichier list.c.
Voici la fonction free_list() mise à jour :

void free_list(struct List* list) {
    struct Node* current = list->head;
    struct Node* next = NULL;

    while (current) {
        next = current->next;
        free(current);
        current = next; // Mise à jour
    }
    free(list);
}

Insérer un nœud après un nœud donné

Dans cette étape, vous allez apprendre à insérer un nouveau nœud après un nœud donné dans la liste doublement chaînée.

Localisez la fonction insert_after() dans le fichier list.c.
Cette fonction prend un struct List*, un struct Node* (le nœud après lequel insérer le nouveau nœud) et les données du nouveau nœud.
La fonction devrait créer un nouveau struct Node et initialiser son champ data avec les données fournies.
La fonction devrait ensuite mettre à jour les pointeurs next et prev du nouveau nœud et du nœud prev pour insérer correctement le nouveau nœud.
Enfin, la fonction devrait mettre à jour le pointeur tail si le nouveau nœud est inséré à la fin de la liste.

Voici la fonction insert_after() mise à jour :

void insert_after(struct List* list, struct Node* prev, void* data) {
    struct Node* newnode = (struct Node *) malloc(sizeof(struct Node));
    newnode->data = data;

    if (prev) { // Mise à jour
        newnode->next = prev->next;
        newnode->prev = prev;
        prev->next = newnode;
        if (newnode->next) newnode->next->prev = newnode;
        else list->tail = newnode; // Mise à jour
    } else {
        newnode->next = list->head;
        newnode->prev = NULL;
        if (list->head) list->head->prev = newnode;
        else list->tail = newnode; // Mise à jour
        list->head = newnode;
    }
}

Localisez insert_after (list, NULL, data); et changez-le en le code suivant :

insert_after (list, list->tail, data);

Insérer un nœud avant un nœud donné

Dans cette étape, vous allez apprendre à insérer un nouveau nœud avant un nœud donné dans la liste doublement chaînée.

Localisez la fonction insert_before() dans le fichier list.c.
Cette fonction prend un struct List*, un struct Node* (le nœud avant lequel insérer le nouveau nœud) et les données du nouveau nœud.
La fonction devrait créer un nouveau struct Node et initialiser son champ data avec les données fournies.
La fonction devrait ensuite mettre à jour les pointeurs next et prev du nouveau nœud et du nœud next pour insérer correctement le nouveau nœud.
Enfin, la fonction devrait mettre à jour le pointeur head si le nouveau nœud est inséré au début de la liste.

Voici la fonction insert_before() mise à jour :

void insert_before(struct List* list, struct Node* next, void* data) {
    struct Node* newnode = (struct Node *) malloc(sizeof(struct Node));
    newnode->data = data;

    if (next) { // Mise à jour
        newnode->prev = next->prev;
        newnode->next = next;
        next->prev = newnode;
        if (newnode->prev) newnode->prev->next = newnode;
        else list->head = newnode; // Mise à jour
    } else {
        newnode->prev = list->tail;
        newnode->next = NULL;
        if (list->tail) list->tail->next = newnode;
        else list->head = newnode; // Mise à jour
        list->tail = newnode;
    }
}

Localisez insert_before (list, NULL, data); et changez-le en le code suivant :

insert_before (list, list->head, data);

Supprimer un nœud de la liste doublement chaînée

Dans cette étape, vous allez apprendre à supprimer un nœud de la liste doublement chaînée.

Localisez la fonction delete_from() dans le fichier list.c.
Cette fonction prend un struct List* et un struct Node* (le nœud à supprimer).
La fonction devrait mettre à jour les pointeurs next et prev des nœuds voisins pour supprimer le nœud donné de la liste.
La fonction devrait également mettre à jour les pointeurs head et tail si le nœud supprimé était le head ou le tail de la liste.
Enfin, la fonction devrait libérer la mémoire occupée par le nœud supprimé.

Voici la fonction delete_from() mise à jour :

void delete_from(struct List* list, struct Node* node) {
    if (node->prev) node->prev->next = node->next;
    else list->head = node->next; // Mise à jour

    if (node->next) node->next->prev = node->prev;
    else list->tail = node->prev; // Mise à jour

    free(node);
}

Maintenant, l'implémentation de la liste doublement chaînée dans le fichier list.c devrait fonctionner correctement. Vous pouvez utiliser le fichier test_list.c fourni pour tester la fonctionnalité de la liste doublement chaînée. Les résultats des tests sont les suivants :

$ gcc test_list.c list.c -o test
$./test
welcome
to
labex
online

Résumé

Félicitations ! Vous avez terminé ce projet. Vous pouvez pratiquer d'autres laboratoires sur LabEx pour améliorer vos compétences.

Implémentation d'une liste doublement chaînée en C