Dans ce didacticiel, vous apprendrez différents types de liste liée. Vous trouverez également l'implémentation de la liste chaînée dans C.
Avant de connaître le type de liste liée, assurez-vous de connaître la structure de données LinkedList.
Il existe trois types courants de liste liée.
- Liste liée individuellement
- Liste doublement liée
- Liste liée circulaire
Liste liée individuellement
C'est le plus courant. Chaque nœud a des données et un pointeur vers le nœud suivant.
Liste liée individuellement
Le nœud est représenté par:
struct node ( int data; struct node *next; )
Une liste liée à trois membres peut être créée comme suit:
/* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->next = two; two->next = three; three->next = NULL; /* Save address of first node in head */ head = one;
Liste doublement liée
Nous ajoutons un pointeur vers le nœud précédent dans une liste doublement liée. Ainsi, nous pouvons aller dans les deux sens: en avant ou en arrière.
Liste doublement liée
Un nœud est représenté par
struct node ( int data; struct node *next; struct node *prev; )
Une liste de trois membres à double liaison peut être créée comme
/* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->next = two; one->prev = NULL; two->next = three; two->prev = one; three->next = NULL; three->prev = two; /* Save address of first node in head */ head = one;
Liste liée circulaire
Une liste liée circulaire est une variante d'une liste liée dans laquelle le dernier élément est lié au premier élément. Cela forme une boucle circulaire.
Liste liée circulaire
Une liste liée circulaire peut être liée de manière simple ou double.
- pour une liste liée individuellement, le pointeur suivant du dernier élément pointe vers le premier élément
- Dans la liste doublement liée, le pointeur précédent du premier élément pointe également vers le dernier élément.
Une liste circulaire unique à trois membres peut être créée comme suit:
/* Initialize nodes */ struct node *head; struct node *one = NULL; struct node *two = NULL; struct node *three = NULL; /* Allocate memory */ one = malloc(sizeof(struct node)); two = malloc(sizeof(struct node)); three = malloc(sizeof(struct node)); /* Assign data values */ one->data = 1; two->data = 2; three->data = 3; /* Connect nodes */ one->next = two; two->next = three; three->next = one; /* Save address of first node in head */ head = one;
