Liste liée en C: Comment implémenter une liste liée en C?

son blog sur Linked List in C vous présente la structure de données Linked List en C et vous aide à comprendre l'implémentation des listes liées en détail avec des exemples.

Après les tableaux, la deuxième structure de données la plus populaire est la liste liée. Une liste chaînée est une structure de données linéaire, constituée d'une chaîne de nœuds dans laquelle chaque nœud contient une valeur et un pointeur vers le nœud suivant de la chaîne. Dans cet article, voyons comment mettre en œuvre une liste liée dans C.



Qu'est-ce que la liste liée en C?

Une liste liée est une structure de données linéaire. Chaque liste chaînée comporte deux parties, la section de données et la section d'adresse qui contient l'adresse de l'élément suivant dans la liste, qui s'appelle un nœud.



La taille de la liste liée n'est pas fixe et des éléments de données peuvent être ajoutés à n'importe quel emplacement de la liste. L'inconvénient est que pour arriver à un nœud, nous devons traverser tout le chemin du premier nœud au nœud dont nous avons besoin. La liste liée est comme un tableau mais contrairement à un tableau, elle n'est pas stockée séquentiellement dans la mémoire.

Les types les plus courants d'une liste liée sont:



  1. Liste de liens individuels
  2. Liste de liens doublement

Exemple de liste liée

Format: [données, adresse]

Tête -> [3,1000] -> [43,1001] -> [21,1002]



Dans l'exemple, le nombre 43 est présent à l'emplacement 1000 et l'adresse est présente au nœud précédent. Voici comment une liste chaînée est représentée.

Fonctions de base de la liste liée

Plusieurs fonctions peuvent être implémentées sur la liste chaînée en C. Essayons de les comprendre à l’aide d’un exemple de programme.Tout d'abord, nous créons une liste, l'afficher, l'insérer à n'importe quel endroit, supprimer un emplacement. Le code suivant vous montrera comment effectuer des opérations sur la liste.

#include #include void create () void display () void insert_begin () void insert_end () void insert_pos () void delete_begin () void delete_end () void delete_pos () struct node {int info struct node * next} struct node * start = NULL int main () {int choix while (1) {printf ('n MENU n') printf ('n 1.Créer n') printf ('n 2.Afficher n') printf ('n 3.Insérer à le début n ') printf (' n 4.Insert à la fin n ') printf (' n 5.Insert à la position spécifiée n ') printf (' n 6.Supprimer du début n ') printf (' n 7.Supprimer à partir de la fin n ') printf (' n 8.Supprimer de la position spécifiée n ') printf (' n 9.Sortie n ') printf (' n ----------------- --------------------- n ') printf (' Entrez votre choix: t ') scanf ('% d ', & choix) commutateur (choix) {cas 1 : create () break case 2: display () break case 3: insert_begin () break case 4: insert_end () break case 5: insert_pos () break case 6: delete_begin () break case 7: delete_end () break case 8: delete_pos () break case 9: exit (0) break par défaut: printf ('n Mauvais choix: n') break}} return 0} voi d create () {struct node * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') exit (0) } printf ('nEntrez la valeur des données pour le nœud: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}} void display () {struct node * ptr if (start == NULL) {printf ('nList est vide: n ') return} else {ptr = start printf (' nLes éléments de la liste sont: n ') while (ptr! = NULL) {printf ('% dt ', ptr-> info) ptr = ptr-> suivant}}} void insert_begin () {struct node * temp temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nEntrez le valeur de données pour le nœud: t ') scanf ('% d ', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {temp-> next = start start = temp }} void insert_end () {struct node * temp, * ptr temp = (struct node *) malloc (sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} p rintf ('nEntrez la valeur des données pour le nœud: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL) {start = temp} else {ptr = start while (ptr-> suivant! = NULL) {ptr = ptr-> suivant} ptr-> suivant = temp}} void insert_pos () {struct node * ptr, * temp int i, pos temp = (struct node *) malloc ( sizeof (struct node)) if (temp == NULL) {printf ('nOut of Memory Space: n') return} printf ('nEntrez la position du nouveau nœud à insérer: t') scanf ('% d' , & pos) printf ('nEntrez la valeur des données du nœud: t') scanf ('% d', & temp-> info) temp-> next = NULL if (pos == 0) {temp-> next = start start = temp} else {for (i = 0, ptr = startinext if (ptr == NULL) {printf ('nPosition not found: [Manipuler avec précaution] n') return}} temp-> next = ptr-> next ptr -> next = temp}} void delete_begin () {struct node * ptr if (ptr == NULL) {printf ('nList is Empty: n') return} else {ptr = start start = start-> next printf (' nL'élément supprimé est:% dt ', ptr-> info) free (ptr)}} void delete_end () {struct node * temp, * ptr if (start == NULL) {printf (' nList is Empty: ') exit (0) } else if (start-> next == NULL) {ptr = start start = NULL printf ('nL'élément supprimé est:% dt', ptr-> info) free (ptr)} else {ptr = start while (ptr- > next! = NULL) {temp = ptr ptr = ptr-> next} temp-> next = NULL printf ('nL'élément supprimé est:% dt', ptr-> info) free (ptr)}} void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nThe List is Empty: n') exit (0)} else {printf ('nEntrez la position du nœud à supprimer : t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nL'élément supprimé est:% dt ', ptr-> info) free (ptr )} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nL'élément supprimé est: % dt ', ptr-> info) gratuit (ptr)}}}

La première partie de ce code crée une structure. Une structure de liste liée est créée afin qu'elle puisse contenir les données et l'adresse dont nous avons besoin. Ceci est fait pour donner au compilateur une idée de la façon dont le nœud devrait être.

classe __init__ python
struct node {int info struct node * next}

Dans la structure, nous avons une variable de données appelée info pour contenir des données et une variable de pointeur pour pointer vers l'adresse. Il existe différentes opérations qui peuvent être effectuées sur une liste chaînée, comme:

  • créer()
  • afficher()
  • insert_begin ()
  • insert_end ()
  • ] insert_pos ()
  • delete_begin ()
  • delete_end ()
  • delete_pos ()

Ces fonctions sont appelées par la fonction principale pilotée par menu. Dans la fonction principale, nous prenons les entrées de l'utilisateur en fonction de l'opération que l'utilisateur souhaite effectuer dans le programme. L'entrée est ensuite envoyée au boîtier de commutation et basée sur l'entrée de l'utilisateur.

En fonction de l'entrée fournie, la fonction sera appelée. Ensuite, nous avons différentes fonctions qui doivent être résolues. Jetons un coup d'œil à chacune de ces fonctions.

Créer une fonction

Tout d'abord, il existe une fonction de création pour créer la liste liée. C'est la manière de base de créer la liste chaînée. Regardons le code.

void create () {struct node * temp, * ptr printf ('nEntrez la valeur des données pour le nœud: t') scanf ('% d', & temp-> info) temp-> next = NULL if (start == NULL ) {start = temp} else {ptr = start while (ptr-> next! = NULL) {ptr = ptr-> next} ptr-> next = temp}}

Production

Insérer - Liste liée - Edureka

Tout d'abord, deux pointeurs sont créés du type node, ptr et temp . Nous prenons la valeur qui doit être ajoutée dans la liste liée de l'utilisateur et la stockons dans la partie info de la variable temporaire et attribuons la valeur nulle à temp de next qui est la partie adresse. Il y a un pointeur de départ contenant le début de la liste. Ensuite, nous vérifions le début de la liste. Si le début de la liste est nul, alors nous affectons temp au pointeur de départ. Sinon, nous traversons jusqu'au dernier point où les données ont été ajoutées.

Pour cela, nous attribuons à ptr la valeur de départ et parcourons jusqu'à ptr-> suivant = nul . Nous attribuons ensuite ptr-> suivant l'adresse de temp. De la même manière, un code est donné pour l'insertion au début, l'insertion à la fin et l'insertion à un emplacement spécifié.

Fonction d'affichage

Voici le code de la fonction d'affichage.

void display () {struct node * ptr if (start == NULL) {printf ('nList is empty: n') return} else {ptr = start printf ('nLes éléments de la liste sont: n') while (ptr! = NULL) {printf ('% dt', ptr-> info) ptr = ptr-> suivant}}}

Production

Dans la fonction d'affichage, nous vérifions d'abord si la liste est vide et retournons si elle est vide. Dans la partie suivante, nous attribuons la valeur de départ à ptr. Nous exécutons ensuite une boucle jusqu'à ce que ptr soit nul et imprimons l'élément de données pour chaque nœud, jusqu'à ce que ptr soit nul, ce qui spécifie la fin de la liste.

Supprimer la fonction

Voici l'extrait de code pour supprimer un nœud de la liste liée.

void delete_pos () {int i, pos struct node * temp, * ptr if (start == NULL) {printf ('nThe List is Empty: n') exit (0)} else {printf ('nEntrez la position du nœud à supprimer: t ') scanf ('% d ', & pos) if (pos == 0) {ptr = start start = start-> next printf (' nL'élément supprimé est:% dt ', ptr-> info ) free (ptr)} else {ptr = start for (i = 0inext if (ptr == NULL) {printf ('nPosition not Found: n') return}} temp-> next = ptr-> next printf ('nThe l'élément supprimé est:% dt ', ptr-> info) free (ptr)}}}

Production

Dans le processus de suppression, il vérifie d'abord si la liste est vide, si oui, elle existe. S'il n'est pas vide, il demande à l'utilisateur de supprimer la position. Une fois que l'utilisateur entre dans la position, il vérifie si c'est la première position, si oui, il attribue ptr pour démarrer et déplace le pointeur de départ vers l'emplacement suivant et supprime ptr. Si la la position n'est pas nulle , puis il exécute une boucle for de 0 à la position saisie par l'utilisateur et stockée dans le pos variable. Il y a une instruction if pour décider si la position saisie n'est pas présente. Si ptr est égal à null , alors il n'est pas présent.

nous assigner ptr à temp dans la boucle for, et ptr passe ensuite à la partie suivante. Après cela, lorsque la position est trouvée. Nous faisons en sorte que la variable temp contienne la valeur de ptr-> suivant sautant ainsi le ptr. Ensuite, ptr est supprimé. De même, cela peut être fait pour la suppression du premier et du dernier élément.

Liste doublement liée

Elle s'appelle la liste doublement chaînée car il y a deux pointeurs , un point vers le nœud suivant et d'autres vers le nœud précédent. Les opérations effectuées dans une liste à liaison double sont similaires à celles d'une liste à liaison unique. Voici le code des opérations de base.

#include #include struct Node typedef struct Node * PtrToNode typedef PtrToNode List typedef PtrToNode Position struct Node {int e Position previous Position next} void Insert (int x, List l, Position p) {Position TmpCell TmpCell = (struct Node *) malloc (sizeof (struct Node)) if (TmpCell == NULL) printf ('Memory out of spacen') else {TmpCell-> e = x TmpCell-> previous = p TmpCell-> next = p-> next p-> next = TmpCell}} void Delete (int x, List l) {Position p, p1, p2 p = Find (x, l) if (p! = NULL) {p1 = p -> previous p2 = p -> next p1 - > suivant = p -> suivant if (p2! = NULL) // si le nœud n'est pas le dernier nœud p2 -> précédent = p -> précédent} else printf ('L'élément n'existe pas !!! n')} void Display (List l) {printf ('Les éléments de la liste sont ::') Position p = l-> next while (p! = NULL) {printf ('% d ->', p-> e) p = p- > suivant}} int main () {int x, pos, ch, i List l, l1 l = (struct Node *) malloc (sizeof (struct Node)) l-> previous = NULL l-> next = NULL List p = l printf ('IMPLÉMENTATION DE LISTE DOUBLE LIÉE DE L IST ADTnn ') faire {printf (' nn1. CREATEn 2. DELETEn 3. DISPLAYn 4. QUITnnEntrez le choix :: ') scanf ('% d ', & ch) switch (ch) {case 1: p = l printf (' Entrez l'élément à insérer :: ') scanf ('% d', & x) printf ('Entrez la position de l'élément ::') scanf ('% d', & pos) for (i = 1 isuivant} Insérer (x, l, p) cas de rupture 2: p = l printf ('Entrez l'élément à supprimer ::') scanf ('% d', & x) Supprimer (x, p) cas de rupture 3: Affichage (l) break}} while (ch<4) } 

Production

Donc, comme vous pouvez le voir, le concept des opérations est assez simple. La liste à double chaînage a les mêmes opérations que celle de la liste à chaînage unique en langage de programmation C. La seule différence est qu'il existe une autre variable d'adresse qui aide à mieux parcourir la liste dans une liste doublement liée.

J'espère que vous avez compris comment effectuer des opérations de base sur des listes simples et doublement liées en C.

Si vous souhaitez apprendre la liste liée en Java, voici un .

Si vous rencontrez des questions, n'hésitez pas à poser toutes vos questions dans la section commentaires de «Liste liée en C» et notre équipe se fera un plaisir de vous répondre.