Pourquoi privilégier les listes chaînées ?

Dans l'apprentissage du C, le tableau est généralement la première structure de données utilisée pour stocker des collections. Cependant, les tableaux imposent des contraintes majeures : - Ils occupent un bloc de mémoire contigu.

• Leur taille doit être définie à la compilation ou lors de l'allocation initiale, ce qui manque de flexibilité.
• Si l'accès à un élément est rapide ($O(1)$), l'insertion ou la suppression au milieu du tableau nécessite de décaler les éléments, entraînant une complexité de $O(n)$.

La liste chaînée pallie ces limitations. Elle est idéale pour les situations où le nombre d'éléments fluctue fréquemment, car elle permet des modifications structurelles efficaces. ### Architecture et cnocepts fondamentaux

Contrairement aux tableaux, une liste chaînée n'est pas stockée de manière linéaire en mémoire. Elle se compose de nœuds reliés entre eux par des références. - Le Nœud : C'est l'unité de base. Il contient un champ de données (le contanu utile) et un champ pointeur (l'adresse du nœud suivant).

• La Tête (Head) : Un pointeur pointant vers le premier élément. Si la liste est vide, ce pointeur est nul.
• La Queue (Tail) : Le dernier élément de la liste, dont le pointeur vers le "suivant" est égal à NULL.

Avantages et compromis

L'utilisation des listes chaînées offre plusieurs bénéfices : 1. Flexibilité mémoire : Les nœuds peuvent être dispersés n'importe où dans le tas (heap). 2. Allocation dynamique : On peut ajouter ou retirer des éléments à la volée selon les besoins réels du programme, évitant ainsi le gaspillage de ressources. 3. Opérations d'insertion/suppression : Une fois l'emplacement trouvé, modifier la structure ne demande que la mise à jour de quelques pointeurs ($O(1)$).

Le revers de la médaille réside dans l'accès aux données. Pour lire le $n$-ième élément, il est impossible d'utiliser un index direct comme avec un tableau ; il faut parcourir la liste depuis le début, ce qui donne une complexité de recherche en $O(n)$. ### Structure de données en C

Voici comment définir un nœud pour une liste chaînée simple stockant des entiers : ``` typedef struct Element { int donnee; struct Element *suivant; } Element, *Liste;

### Opérasions de création

Il existe deux stratégies principales pour construire une liste : l'insertion par la tête ou par la queue. #### 1. Insertion par la tête

Cette méthode place chaque nouvel élément au début de la liste. ```
void insererEnTete(Liste *L, int nombre) {
    Liste nouveau;
    for (int i = 0; i < nombre; i++) {
        nouveau = (Liste)malloc(sizeof(Element));
        nouveau->donnee = rand() % 100;
        nouveau->suivant = *L;
        *L = nouveau;
    }
}

2. Insertion par la queue

Cette méthode conserve l'ordre de création en ajoutant les éléments à la fin. ``` void insererEnQueue(Liste *L, int nombre) { Liste nouveau, dernier; *L = NULL; dernier = NULL;

for (int i = 0; i < nombre; i++) {
    nouveau = (Liste)malloc(sizeof(Element));
    nouveau->donnee = rand() % 100;
    nouveau->suivant = NULL;

    if (*L == NULL) {
        *L = nouveau;
    } else {
        dernier->suivant = nouveau;
    }
    dernier = nouveau;
}

}

### Recherche d'un élément

Pour extraire une valeur à une position spécifique, nous utilisons un curseur qui parcourt la chaîne. ```
int obtenirElement(Liste L, int position, int *valeur) {
    int compteur = 0;
    Liste curseur = L;

    while (curseur && compteur < position) {
        curseur = curseur->suivant;
        compteur++;
    }

    if (!curseur) return 0; // Échec

    *valeur = curseur->donnee;
    return 1; // Succès
}

Insertion à une position donnée

L'insertion nécessite de manipuler les pointeurs du nœud précédent pour intégrer le nouveau maillon. ``` int insererAilleurs(Liste *L, int position, int valeur) { Liste courant = *L; int j = 0;

while (courant && j < position - 1) {
    courant = courant->suivant;
    j++;
}

if (!courant) return 0;

Liste maille = (Liste)malloc(sizeof(Element));
maille->donnee = valeur;
maille->suivant = courant->suivant;
courant->suivant = maille;

return 1;

}

### Suppression d'un nœud

Pour supprimer un élément, on court-circuite le nœud cible en reliant son prédécesseur à son successeur, puis on libère la mémoire. ```
int supprimerElement(Liste *L, int position) {
    Liste prec = *L, cible;
    int j = 0;

    while (prec->suivant && j < position - 1) {
        prec = prec->suivant;
        j++;
    }

    if (!(prec->suivant)) return 0;

    cible = prec->suivant;
    prec->suivant = cible->suivant;
    free(cible);

    return 1;
}

Libération de la mémoire

Il est crucial de libérer chaque nœud individuellement pour éviter les fuites de mémoire lors de la destruction de la liste. ``` void viderListe(Liste *L) { Liste temp, curseur; curseur = *L;

while (curseur) {
    temp = curseur->suivant;
    free(curseur);
    curseur = temp;
}
*L = NULL;

}