CodeUtility
Faciliter la vie des développeurs !
Structures de données en C/C++

La liste simplement chaînée en C et C++

Dans cette leçon, vous allez construire, parcourir et libérer une liste simplement chaînée en C et en C++.

Introduction

Une liste simplement chaînée (singly linked list) est formée de nœuds (nodes), chacun contenant une valeur et un pointeur vers le nœud suivant. Contrairement à un tableau, les nœuds n'ont pas besoin d'être côte à côte en mémoire, on peut donc ajouter un élément sans déplacer les autres.

Points importants

  • Définissez les conditions qui doivent toujours être vraies (invariants) avant d'écrire les opérations.
  • Traitez les cas de structure vide, pleine et d'échec d'allocation mémoire.
  • Évaluez ensemble la complexité et la gestion mémoire de chaque opération.

Voir comment ça marche

Ajoutez des nœuds au début ou à la fin et cliquez sur un nœud pour le supprimer. Appuyez sur Lecture pour suivre les pointeurs next de head jusqu'à NULL.

Exemples de code C et C++

C
Exécuter →
main.c
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int value;
    struct Node *next;
} Node;

int main(void) {
    Node *head = NULL;
    for (int value = 3; value >= 1; --value) {
        Node *node = malloc(sizeof *node);
        if (!node) return 1;
        *node = (Node){value, head};
        head = node;
    }
    while (head) {
        Node *next = head->next;
        printf("%d ", head->value);
        free(head);
        head = next;
    }
    puts("");
    return 0;
}
Résultat de l’exécution
1 2 3
C++
Exécuter →
main.cpp
#include <iostream>
#include <memory>

struct Node {
    int value;
    std::unique_ptr<Node> next;
};

int main() {
    std::unique_ptr<Node> head;
    for (int value = 3; value >= 1; --value) {
        head = std::make_unique<Node>(Node{value, std::move(head)});
    }
    for (Node *node = head.get(); node; node = node->next.get()) {
        std::cout << node->value << ' ';
    }
    std::cout << '\n';
}
Résultat de l’exécution
1 2 3

Comparaison entre C et C++

Dans la version C, chaque nœud est alloué avec malloc, et à la fin le programme doit parcourir toute la liste pour appeler free sur chaque nœud. Dans la version C++, les nœuds sont reliés par des std::unique_ptr, donc quand le premier nœud est détruit, toute la chaîne qui suit est libérée automatiquement.

C

Les données (struct) et les opérations sont séparées, et la mémoire est allouée et libérée à la main.

C++

Les classes et les conteneurs protègent la cohérence des données et gèrent eux-mêmes leurs ressources.

Exercices d'approfondissement

Exécutez les deux versions, puis modifiez le code pour observer la différence de sécurité qu'apporte chaque langage.

  • Ajoutez des tests pour l'état vide et pour le moment où la capacité maximale est atteinte.
  • Écrivez la libération de la mémoire et vérifiez qu'il n'y a pas de fuite.
  • Comparez la complexité avec celle du conteneur équivalent de la bibliothèque standard.

S'entraîner avec un défi

Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.

Tous les défis