Introduction aux Listes Linéaires

Une liste linéaire est une structure de données fondamentale, caractérisée par une séquence finie d'éléments de même type. Chaque élément, sauf le premier, possède un prédécesseur unique, et chaque élément, sauf le dernier, a un successeur unique. Lorsque la liste est vide, elle ne contient aucun élément.

Formellement, une liste linéaire $L$ de $n$ éléments peut être représentée comme :

$$ L = (e_1, e_2, ..., e_i, e_{i+1}, ..., e_n) $$

• $e_i$ est l'élément à la $i$-ème position dans la liste.
• $e_1$ est le premier élément (ou tête de liste).
• $e_n$ est le dernier élément (ou queue de liste).

Opérations Fondamentales sur les Listes Linéaires

Les opérations de base définissent l'interface d'une structure de données. Pour une liste linéaire, elles incluent :

// 1. Initialisation : Crée une liste linéaire vide.
InitialiserListe(&L)

// 2. Vérification d'Empty : Retourne vrai si la liste est vide, faux sinon.
EstVide(L)

// 3. Calcul de la Taille : Retourne le nombre d'éléments dans la liste.
ObtenirTaille(L)

// 4. Accès par Position : Récupère l'élément à la position spécifiée.
ObtenirElement(L, indice)

// 5. Recherche par Valeur : Trouve la position du premier élément correspondant à une valeur donnée.
RechercherElement(L, valeur)

// 6. Insertion : Insère un nouvel élément à une position donnée.
InsererElement(&L, indice, element)

// 7. Suppression : Supprime l'élément à une position donnée et retourne sa valeur.
SupprimerElement(&L, indice, &elementSupprime)

// 8. Libération : Détruit la liste, libérant toutes les ressources.
DetruireListe(&L)

Ces opérations sont cruciales pour plusieurs raisons :

• Elles encapsulent la logique de manipulation des données, facilitant la collaboration et la maintenance du code.
• Elles standardisent l'accès et la modification de la structure, réduisant la duplication de code et les erreurs.

Implémentation Séquentielle des Listes Linéaires (Tableau Dynamique)

L'implémentation séquentielle d'une liste linéaire, souvent appelée "tableau dynamique" ou "liste séquentielle", stocke les éléments dans des emplacements mémoire contigus. La relation logique d'adjacence entre les éléments est ainsi directement reflétée par leur adjacence physique en mémoire.

Définition de la Structure

En C, une implémentation séquentielle pourrait être définie comme suit :

#define CAPACITE_INITIALE 50

typedef struct {
    TypeElement *elements;  // Pointeur vers le tableau d'éléments alloué dynamiquement
    int tailleActuelle;     // Nombre d'éléments actuellement dans la liste
    int capaciteMaximale;   // Capacité maximale du tableau alloué
} ListeSequentielle;

L'utilisation d'un tableau alloué dynamiquement permet d'ajuster la taille de la liste pendant l'exécution du programme. Lorsque la capacité maximale est atteinte, un nouveau tableau plus grand est alloué, les éléments sont copiés, et l'ancien tableau est libéré. Ceci évite les débordements (overflow) et offre plus de flexibilité qu'une allocation statique.

Initialisation d'une liste séquentielle en C/C++ :

// En C
liste.elements = (TypeElement *)malloc(sizeof(TypeElement) * CAPACITE_INITIALE);

// En C++
liste.elements = new TypeElement[CAPACITE_INITIALE];

Caractéristiques

• Accès Aléatoire : Un élément à une position donnée peut être accédé directement en temps constant $O(1)$ grâce à l'arithmétique des pointeurs.
• Densité de Stockage Élevée : Seuls les éléments de données sont stockés, sans surcharge de pointeurs pour lier les éléments.
• Coût des Insertions/Suppressions : Les opérations d'insertion ou de suppression au milieu de la liste nécessitent le déplacement d'un grand nombre d'éléments pour maintenir la contiguïté, entraînant une complexité temporelle de $O(n)$.

Implémentation des Opérations Clés sur une Liste Séquentielle

Opération d'Insertion

Pour insérer un élément à la position $indice$ (1-basée), il est nécessaire de décaler tous les éléments de $indice$ à $tailleActuelle$ d'une position vers la droite, puis de placer le nouvel élément à $indice - 1$.

bool InsererElement(ListeSequentielle *liste, int indice, TypeElement element) {
    if (indice < 1 || indice > liste->tailleActuelle + 1) {
        // Indice invalide
        return false;
    }
    if (liste->tailleActuelle >= liste->capaciteMaximale) {
        // La liste est pleine, gestion de la réallocation omise pour la concision
        return false; 
    }

    // Décaler les éléments vers la droite
    for (int j = liste->tailleActuelle; j >= indice; j--) {
        liste->elements[j] = liste->elements[j - 1];
    }

    // Insérer le nouvel élément
    liste->elements[indice - 1] = element;
    liste->tailleActuelle++;
    return true;
}

Opération de Suppression

La suppression d'un élément à la position $indice$ implique de le récupérer, puis de décaler tous les éléments suivants d'une position vers la gauche pour combler le vide.

bool SupprimerElement(ListeSequentielle *liste, int indice, TypeElement *elementSupprime) {
    if (indice < 1 || indice > liste->tailleActuelle) {
        // Indice invalide
        return false;
    }

    // Sauvegarder l'élément à supprimer
    *elementSupprime = liste->elements[indice - 1];

    // Décaler les éléments vers la gauche
    for (int j = indice; j < liste->tailleActuelle; j++) {
        liste->elements[j - 1] = liste->elements[j];
    }

    liste->tailleActuelle--;
    return true;
}

La complexité temporelle pour la suppression varie :

• Meilleur cas : Suppression du dernier élément, $O(1)$.
• Pire cas : Suppression du premier élément, $O(n)$ opérations de décalage.
• Cas moyen : Environ $O(n/2)$ opérations de décalage, donc $O(n)$.

Opération de Recherche par Valeur

Pour trouver la position d'un élément donné par sa valeur, la liste est parcourue séquentiellement.

int RechercherElement(ListeSequentielle liste, TypeElement valeurCible) {
    for (int i = 0; i < liste.tailleActuelle; i++) {
        if (liste.elements[i] == valeurCible) {
            return i + 1; // Retourne la position (1-basée)
        }
    }
    return 0; // Élément non trouvé
}

La complexité temporelle pour la recherche varie :

• Meilleur cas : L'élément cible est le premier, $O(1)$.
• Pire cas : L'élément cible est le dernier ou absent, $O(n)$.
• Cas moyen : Environ $O(n/2)$ comparaisons, donc $O(n)$.

Opération d'Accès par Position

Accéder à un élément par son indice est une opération directe dans une liste séquentielle.

TypeElement ObtenirElement(ListeSequentielle liste, int indice) {
    if (indice < 1 || indice > liste.tailleActuelle) {
        // Gérer l'erreur, par exemple retourner une valeur par défaut ou lever une exception
        // Pour cet exemple, nous retournons une valeur arbitraire ou non valide
        // Dans une implémentation réelle, cela nécessiterait un mécanisme de gestion d'erreur plus robuste
        return (TypeElement){0}; // Exemple : retourne un élément nul si TypeElement est un struct simple
    }
    return liste.elements[indice - 1]; // Retourne l'élément à l'indice (0-basé) correspondant
}