Structures de données en C/C++

Liste simplement chaînée

Chaque nœud contient une valeur et un lien vers le suivant.

Qu’est-ce que Liste simplement chaînée ?

Chaque nœud contient une valeur et un lien vers le suivant.

Construisez, parcourez et détruisez une liste chaînée.

Points importants

Définissez les invariants avant les opérations.
Gérez les cas vide, plein et échec d’allocation.
Étudiez ensemble complexité et ownership.

Exemples de code C et 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 attendu

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 attendu

1 2 3

Comparaison entre C et C++

C alloue avec malloc et libère chaque nœud. unique_ptr en C++ détruit automatiquement toute la chaîne depuis la tête.

Structures et opérations sont séparées, avec allocation explicite.

C++

Classes et conteneurs protègent les invariants et les ressources.

Exercices pratiques

Exécutez les deux versions puis modifiez-les pour observer leurs garanties.

Testez les états vide et plein.
Implémentez le nettoyage et cherchez les fuites.
Comparez à un conteneur standard.