PARTIE 2 (Suite) : INSERTION

TP 6 : Implémentation Basique

Nous allons voir deux opérations fondamentales : insertAtHead (au début) et insertAtEnd (à la fin).

1. Insertion en Tête (Insert at Head)

Complexité : O(1) (Très rapide)

Algorithme :

1. Créer un nouveau nœud (newNode).
2. Faire pointer newNode->next vers l’actuel head.
3. Mettre à jour head pour qu’il pointe vers newNode.

Code :

void insertAtHead(Node** head, int value) {
    Node* newNode = createNode(value);
    newNode->next = *head;
    *head = newNode;
}

Note : On utilise Node** head (pointeur de pointeur) car on doit modifier l’adresse contenue dans la variable head du main.

Schéma Visuel :

2. Insertion à la Fin (Insert at End)

Complexité : O(n) (Doit parcourir toute la liste)

Algorithme :

1. Créer newNode.
2. Si la liste est vide (head == NULL), head = newNode.
3. Sinon, parcourir la liste jusqu’au dernier nœud (celui dont next est NULL).
4. Faire pointer le dernier nœud vers newNode.

Code :

void insertAtEnd(Node** head, int value) {
    Node* newNode = createNode(value);

    if (*head == NULL) {
        *head = newNode;
        return;
    }

    Node* temp = *head;
    while (temp->next != NULL) { // Parcours jusqu'au dernier
        temp = temp->next;
    }

    temp->next = newNode;
}

Schéma Parcours :

TP 6 : Exercice

Implémentez les fonctions ci-dessus et testez-les en insérant 5 éléments (ex: 10, 20, 30…) et affichez la liste après chaque étape.