Manipulation and Use of Linked Lists in C
Manipulation and Use of Linked Lists in C
Computer Science · notes
Fiche de révisionRésumé
Rédigée à partir de ce document, puis vérifiée avant publication.
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.
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 :
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.
Une fois la liste chaînée déclarée, vous pouvez manipuler ses éléments. Voici quelques opérations courantes :
Il existe deux manières d'ajouter un élément à une liste chaînée : en tête ou en fin de liste.
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;
}
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;
}
}
La suppression d'un élément peut également se faire en tête ou en fin de liste.
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;
}
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;
}
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;
}
Voici les points essentiels à retenir concernant les listes chaînées :
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;
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.
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.
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.