PARTIE 2 : LISTES LINÉAIRES CHAÎNÉES

Introduction

Une liste chaînée est une structure de données linéaire où les éléments ne sont pas stockés dans des emplacements mémoire contigus (contrairement aux tableaux). Chaque élément pointe vers le suivant.

Avantages vs Tableau :

• Taille dynamique (pas de taille fixe à la compilation).
• Insertion/Suppression facile (pas besoin de décaler les éléments).

Inconvénients :

• Accès séquentiel (pas d’accès direct tab[i]).
• Utilisation mémoire supplémentaire pour les pointeurs.

Structure d’un Nœud (Node)

Un élément de la liste est appelé un Nœud (Node). Il contient :

1. La Donnée (Data).
2. Un Pointeur vers le nœud suivant (Next).

typedef struct Node {
    int data;           // Donnée
    struct Node *next;  // Pointeur vers le suivant
} Node;

Représentation Visuelle

• Head : Un pointeur qui garde l’adresse du premier élément. Si la liste est vide, Head = NULL.
• Le dernier élément pointe vers NULL.

Création d’un Nouveau Nœud

Pour créer un nœud, on utilise l’allocation dynamique (malloc).

Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node)); // Allocation mémoire
    if (newNode == NULL) {
        exit(1); // Erreur mémoire
    }
    newNode->data = value;
    newNode->next = NULL;
    return newNode;
}

Schéma Création :

Dans la prochaine leçon, nous verrons comment assembler ces nœuds pour former une liste.