Aller au contenu

Manipulation and Use of Linked Lists in C

Listes chaînées en C Les listes chaînées en C sont une structure de données qui permet de stocker des éléments de manière dynamique. Contrairement aux tableaux, les listes chaînées ne nécessitent pas de taille fixe et permettent une manipulation plus flexible des éléments.

D'après le document Manipulation and Use of Linked Lists in C

Cet article a été rédigé automatiquement à partir du document source, puis vérifié avant publication.

Document source

Manipulation and Use of Linked Lists in C

Computer Science · PDF · 9 pages · 2011

Afficher l'aperçu du document

Consulter le document original →

Listes chaînées en C

Les listes chaînées en C sont une structure de données qui permet de stocker des éléments de manière dynamique. Contrairement aux tableaux, les listes chaînées ne nécessitent pas de taille fixe et permettent une manipulation plus flexible des éléments. Cet article couvre la déclaration des listes chaînées, ainsi que les opérations courantes telles que l'ajout, la suppression et la recherche d'éléments.

Généralités sur les listes chaînées

Les listes chaînées sont composées d'éléments appelés nœuds, où chaque nœud contient une valeur et un pointeur vers le nœud suivant. Cela permet d'ajouter et de supprimer des éléments sans avoir à déplacer les autres éléments, contrairement aux tableaux où les éléments sont stockés de manière contiguë en mémoire.

Chaque nœud d'une liste chaînée est constitué de deux parties :

  • La valeur que vous souhaitez stocker.
  • L'adresse de l'élément suivant, qui sera NULL si c'est le dernier élément de la liste.

Déclaration en C d'une liste chaînée

Pour déclarer une liste chaînée en C, vous devez définir une structure pour représenter un nœud. Voici un exemple de déclaration d'une liste simplement chaînée d'entiers :

#include <stdlib.h>

typedef struct element element;
struct element {
    int val;
    struct element *nxt;
};

typedef element* llist;

int main() {
    llist ma_liste1 = NULL;
    element *ma_liste2 = NULL;
    struct element *ma_liste3 = NULL;

    return 0;
}

Il est important d'initialiser la liste chaînée à NULL.

Manipulation des listes chaînées

Une fois la liste chaînée déclarée, vous pouvez manipuler ses éléments. Voici quelques opérations courantes :

Ajouter un élément

Il existe deux manières d'ajouter un élément à une liste chaînée : en tête ou en fin de liste.

Ajouter en tête

Pour ajouter un élément en tête, vous créez un nouvel élément, lui assignez une valeur, puis le reliez à la liste existante :

llist ajouterEnTete(llist liste, int valeur) {
    element* nouvelElement = malloc(sizeof(element));
    nouvelElement->val = valeur;
    nouvelElement->nxt = liste;
    return nouvelElement;
}

Ajouter en fin de liste

Pour ajouter un élément en fin de liste, vous devez parcourir la liste jusqu'au dernier élément et le relier au nouvel élément :

llist ajouterEnFin(llist liste, int valeur) {
    element* nouvelElement = malloc(sizeof(element));
    nouvelElement->val = valeur;
    nouvelElement->nxt = NULL;

    if (liste == NULL) {
        return nouvelElement;
    } else {
        element* temp = liste;
        while (temp->nxt != NULL) {
            temp = temp->nxt;
        }
        temp->nxt = nouvelElement;
        return liste;
    }
}

Supprimer un élément

La suppression d'un élément peut également se faire en tête ou en fin de liste.

Supprimer un élément en tête

Pour supprimer le premier élément, vous devez stocker l'adresse du deuxième élément avant de libérer le premier :

llist supprimerElementEnTete(llist liste) {
    if (liste != NULL) {
        element* aRenvoyer = liste->nxt;
        free(liste);
        return aRenvoyer;
    }
    return NULL;
}

Supprimer un élément en fin de liste

Pour supprimer le dernier élément, vous devez parcourir la liste jusqu'à l'avant-dernier élément :

llist supprimerElementEnFin(llist liste) {
    if (liste == NULL) return NULL;

    if (liste->nxt == NULL) {
        free(liste);
        return NULL;
    }

    element* tmp = liste;
    element* ptmp = liste;

    while (tmp->nxt != NULL) {
        ptmp = tmp;
        tmp = tmp->nxt;
    }

    ptmp->nxt = NULL;
    free(tmp);
    return liste;
}

Rechercher un élément

Pour rechercher un élément dans une liste chaînée, parcourez la liste jusqu'à trouver l'élément avec la valeur recherchée :

llist rechercherElement(llist liste, int valeur) {
    element *tmp = liste;
    while (tmp != NULL) {
        if (tmp->val == valeur) {
            return tmp;
        }
        tmp = tmp->nxt;
    }
    return NULL;
}

Points clés à retenir

Voici les points essentiels à retenir concernant les listes chaînées :

  • Les listes chaînées permettent une gestion dynamique de la mémoire.
  • Chaque nœud contient une valeur et un pointeur vers le nœud suivant.
  • Les opérations d'ajout et de suppression sont flexibles et ne nécessitent pas de déplacement d'éléments.
  • Les listes chaînées peuvent être parcourues pour rechercher des éléments ou compter le nombre d'éléments.

Questions fréquentes

Comment déclarer une liste chaînée en C ?

Pour déclarer une liste chaînée en C, vous devez définir une structure pour les nœuds et un type de pointeur pour la liste. Par exemple :

typedef struct element element;
struct element {
    int val;
    struct element *nxt;
};
typedef element* llist;

Comment ajouter un élément à une liste chaînée ?

Vous pouvez ajouter un élément en tête ou en fin de liste. Pour ajouter en tête, créez un nouvel élément et reliez-le à la liste existante. Pour ajouter en fin, parcourez la liste jusqu'au dernier élément et reliez-le au nouvel élément.

Comment supprimer un élément d'une liste chaînée ?

Pour supprimer un élément en tête, stockez l'adresse du deuxième élément avant de libérer le premier. Pour supprimer en fin, parcourez la liste jusqu'à l'avant-dernier élément et libérez le dernier.

Comment rechercher un élément dans une liste chaînée ?

Pour rechercher un élément, parcourez la liste et comparez chaque valeur jusqu'à trouver celle recherchée. Si trouvée, renvoyez l'adresse de l'élément.

Partager

Commentaires

Aucun commentaire pour le moment. Posez la première question.

Les commentaires sont relus avant publication. Votre e-mail n'est jamais affiché.

← Toutes les révisions