PARTIE 2 (Suite) : RECHERCHE ET INVERSION

TP 8 : Recherche et Modification

La recherche dans une liste chaînée est linéaire O(n). Contrairement à un tableau trié où l’on peut faire une recherche binaire, ici on doit suivre les liens un par un.

Node* search(Node* head, int key) {
    Node* current = head;
    while (current != NULL) {
        if (current->data == key) {
            return current; // Trouvé
        }
        current = current->next;
    }
    return NULL; // Pas trouvé
}

TP 9 : Inversion d’une Liste Chaînée (Reverse)

C’est un classique des entretiens d’embauche ! Il faut inverser le sens des flèches.

Algorithme (Itératif) : On a besoin de 3 pointeurs :

1. prev (Précédent) : initialisé à NULL.
2. current (Courant) : initialisé à head.
3. next (Suivant) : stocke le prochain nœud avant de casser le lien.

Boucle :

while (current != NULL) {
    next = current->next;  // 1. Sauver le prochain
    current->next = prev;  // 2. Inverser le lien (pointe vers l'arrière)
    prev = current;        // 3. Avancer prev
    current = next;        // 4. Avancer current
}
head = prev; // Nouvelle tête est le dernier élément (prev)

Schéma Inversion :

Questions pour le TP

• Quelle est la complexité temporelle ? (Réponse : O(n))
• Quelle est la complexité spatiale ? (Réponse : O(1), car on n’alloue pas de nouvelle liste, on modifie juste les liens).