- La liste chaînée peut être définie comme une collection d'objets appelés nœuds qui sont stockés aléatoirement dans la mémoire.
- Un nœud contient deux champs, à savoir les données stockées à cette adresse particulière et le pointeur qui contient l'adresse du nœud suivant dans la mémoire.
- Le dernier nœud de la liste contient un pointeur vers la valeur null.
Utilisations de la liste chaînée
- Il n'est pas nécessaire que la liste soit présente de manière contiguë dans la mémoire. Le nœud peut résider n'importe où dans la mémoire et être lié pour créer une liste. Cela permet une utilisation optimisée de l’espace.
- la taille de la liste est limitée à la taille de la mémoire et n'a pas besoin d'être déclarée à l'avance.
- Le nœud vide ne peut pas être présent dans la liste chaînée.
- Nous pouvons stocker les valeurs de types ou d'objets primitifs dans la liste à chaînage unique.
Pourquoi utiliser une liste chaînée plutôt qu'un tableau ?
Jusqu'à présent, nous utilisions une structure de données matricielle pour organiser le groupe d'éléments qui doivent être stockés individuellement dans la mémoire. Cependant, Array présente plusieurs avantages et inconvénients qu'il faut connaître afin de décider de la structure de données qui sera utilisée tout au long du programme.
Le tableau contient les limitations suivantes :
- La taille du tableau doit être connue à l'avance avant de l'utiliser dans le programme.
- L’augmentation de la taille du tableau est un processus qui prend du temps. Il est presque impossible d’augmenter la taille du tableau au moment de l’exécution.
- Tous les éléments du tableau doivent être stockés de manière contiguë dans la mémoire. L'insertion d'un élément dans le tableau nécessite le déplacement de tous ses prédécesseurs.
La liste chaînée est la structure de données qui peut surmonter toutes les limitations d'un tableau. L'utilisation d'une liste chaînée est utile car,
les essentiels de la construction d'ubuntu
- Il alloue la mémoire de manière dynamique. Tous les nœuds de la liste chaînée sont stockés de manière non contiguë dans la mémoire et liés entre eux à l'aide de pointeurs.
- Le dimensionnement n'est plus un problème puisqu'on n'a pas besoin de définir sa taille au moment de la déclaration. La liste s'agrandit selon la demande du programme et est limitée à l'espace mémoire disponible.
Liste à chaînage unique ou chaîne à sens unique
Une liste chaînée unique peut être définie comme la collection d’un ensemble ordonné d’éléments. Le nombre d'éléments peut varier selon les besoins du programme. Un nœud dans la liste à chaînage unique se compose de deux parties : la partie données et la partie lien. La partie données du nœud stocke les informations réelles qui doivent être représentées par le nœud tandis que la partie liaison du nœud stocke l'adresse de son successeur immédiat.
Une chaîne à sens unique ou une liste à chaînage unique ne peuvent être parcourues que dans une seule direction. En d’autres termes, on peut dire que chaque nœud ne contient que le pointeur suivant, donc on ne peut pas parcourir la liste dans le sens inverse.
Prenons un exemple où les notes obtenues par l'étudiant dans trois matières sont stockées dans une liste chaînée comme le montre la figure.
programme de nombres premiers en java
Dans la figure ci-dessus, la flèche représente les liens. La partie données de chaque nœud contient les notes obtenues par l'étudiant dans les différentes matières. Le dernier nœud de la liste est identifié par le pointeur nul qui est présent dans la partie adresse du dernier nœud. Nous pouvons avoir autant d’éléments dont nous avons besoin dans la partie données de la liste.
Complexité
| Structure de données | Complexité temporelle | Complétude de l'espace | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Moyenne | Pire | Pire | |||||||
| Accéder | Recherche | Insertion | Effacement | Accéder | Recherche | Insertion | Effacement | ||
| Liste à chaînage unique | dans) | dans) | je(1) | je(1) | Sur) | Sur) | O(1) | O(1) | Sur) |
Opérations sur une liste à lien unique
Il existe diverses opérations qui peuvent être effectuées sur une seule liste chaînée. Une liste de toutes ces opérations est donnée ci-dessous.
Création de nœud
struct node { int data; struct node *next; }; struct node *head, *ptr; ptr = (struct node *)malloc(sizeof(struct node *)); Insertion
L'insertion dans une liste à chaînage unique peut être effectuée à différentes positions. En fonction de la position du nouveau nœud inséré, l'insertion est classée dans les catégories suivantes.
commande autocad en ligne
| SN | Opération | Description |
|---|---|---|
| 1 | Insertion au début | Cela implique d’insérer n’importe quel élément au début de la liste. Nous avons juste besoin de quelques ajustements de liens pour faire du nouveau nœud la tête de liste. |
| 2 | Insertion en fin de liste | Cela implique une insertion à la fin de la liste chaînée. Le nouveau nœud peut être inséré comme seul nœud dans la liste ou comme dernier. Différentes logiques sont mises en œuvre dans chaque scénario. |
| 3 | Insertion après le nœud spécifié | Cela implique une insertion après le nœud spécifié de la liste chaînée. Nous devons sauter le nombre souhaité de nœuds afin d'atteindre le nœud après lequel le nouveau nœud sera inséré. . |
Suppression et parcours
La suppression d'un nœud d'une liste à chaînage unique peut être effectuée à différentes positions. En fonction de la position du nœud à supprimer, l'opération est classée dans les catégories suivantes.
| SN | Opération | Description |
|---|---|---|
| 1 | Suppression au début | Cela implique la suppression d'un nœud dès le début de la liste. C’est l’opération la plus simple parmi toutes. Il suffit de quelques ajustements dans les pointeurs de nœuds. |
| 2 | Suppression en fin de liste | Cela implique de supprimer le dernier nœud de la liste. La liste peut être vide ou pleine. Différentes logiques sont mises en œuvre pour les différents scénarios. |
| 3 | Suppression après le nœud spécifié | Cela implique de supprimer le nœud après le nœud spécifié dans la liste. nous devons sauter le nombre souhaité de nœuds pour atteindre le nœud après quoi le nœud sera supprimé. Cela nécessite de parcourir la liste. |
| 4 | Traversée | Lors du parcours, nous visitons simplement chaque nœud de la liste au moins une fois afin d'y effectuer une opération spécifique, par exemple, imprimer une partie des données de chaque nœud présent dans la liste. |
| 5 | Recherche | Lors de la recherche, nous faisons correspondre chaque élément de la liste avec l'élément donné. Si l'élément est trouvé sur l'un des emplacements, l'emplacement de cet élément est renvoyé, sinon null est renvoyé. . |
Liste chaînée en C : programme piloté par menu
#include #include struct node { int data; struct node *next; }; struct node *head; void beginsert (); void lastinsert (); void randominsert(); void begin_delete(); void last_delete(); void random_delete(); void display(); void search(); void main () { int choice =0; while(choice != 9) { printf('
*********Main Menu*********
'); printf('
Choose one option from the following list ...
'); printf('
===============================================
'); printf('
1.Insert in begining
2.Insert at last
3.Insert at any random location
4.Delete from Beginning
5.Delete from last
6.Delete node after specified location
7.Search for an element
8.Show
9.Exit
'); printf('
Enter your choice?
'); scanf('
%d',&choice); switch(choice) { case 1: beginsert(); break; case 2: lastinsert(); break; case 3: randominsert(); break; case 4: begin_delete(); break; case 5: last_delete(); break; case 6: random_delete(); break; case 7: search(); break; case 8: display(); break; case 9: exit(0); break; default: printf('Please enter valid choice..'); } } } void beginsert() { struct node *ptr; int item; ptr = (struct node *) malloc(sizeof(struct node *)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter value
'); scanf('%d',&item); ptr->data = item; ptr->next = head; head = ptr; printf('
Node inserted'); } } void lastinsert() { struct node *ptr,*temp; int item; ptr = (struct node*)malloc(sizeof(struct node)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter value?
'); scanf('%d',&item); ptr->data = item; if(head == NULL) { ptr -> next = NULL; head = ptr; printf('
Node inserted'); } else { temp = head; while (temp -> next != NULL) { temp = temp -> next; } temp->next = ptr; ptr->next = NULL; printf('
Node inserted'); } } } void randominsert() { int i,loc,item; struct node *ptr, *temp; ptr = (struct node *) malloc (sizeof(struct node)); if(ptr == NULL) { printf('
OVERFLOW'); } else { printf('
Enter element value'); scanf('%d',&item); ptr->data = item; printf('
Enter the location after which you want to insert '); scanf('
%d',&loc); temp=head; for(i=0;inext; if(temp == NULL) { printf('
can't insert
'); return; } } ptr ->next = temp ->next; temp ->next = ptr; printf('
Node inserted'); } } void begin_delete() { struct node *ptr; if(head == NULL) { printf('
List is empty
'); } else { ptr = head; head = ptr->next; free(ptr); printf('
Node deleted from the begining ...
'); } } void last_delete() { struct node *ptr,*ptr1; if(head == NULL) { printf('
list is empty'); } else if(head -> next == NULL) { head = NULL; free(head); printf('
Only node of the list deleted ...
'); } else { ptr = head; while(ptr->next != NULL) { ptr1 = ptr; ptr = ptr ->next; } ptr1->next = NULL; free(ptr); printf('
Deleted Node from the last ...
'); } } void random_delete() { struct node *ptr,*ptr1; int loc,i; printf('
Enter the location of the node after which you want to perform deletion
'); scanf('%d',&loc); ptr=head; for(i=0;inext; if(ptr == NULL) { printf('
Can't delete'); return; } } ptr1 ->next = ptr ->next; free(ptr); printf('
Deleted node %d ',loc+1); } void search() { struct node *ptr; int item,i=0,flag; ptr = head; if(ptr == NULL) { printf('
Empty List
'); } else { printf('
Enter item which you want to search?
'); scanf('%d',&item); while (ptr!=NULL) { if(ptr->data == item) { printf('item found at location %d ',i+1); flag=0; } else { flag=1; } i++; ptr = ptr -> next; } if(flag==1) { printf('Item not found
'); } } } void display() { struct node *ptr; ptr = head; if(ptr == NULL) { printf('Nothing to print'); } else { printf('
printing values . . . . .
'); while (ptr!=NULL) { printf('
%d',ptr->data); ptr = ptr -> next; } } } Sortir:
*********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 1 Enter value 1 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 2 Enter value? 2 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 3 Enter element value1 Enter the location after which you want to insert 1 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 8 printing values . . . . . 1 2 1 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 2 Enter value? 123 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 1 Enter value 1234 Node inserted *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 4 Node deleted from the begining ... *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 5 Deleted Node from the last ... *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 6 Enter the location of the node after which you want to perform deletion 1 Deleted node 2 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 8 printing values . . . . . 1 1 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 7 Enter item which you want to search? 1 item found at location 1 item found at location 2 *********Main Menu********* Choose one option from the following list ... =============================================== 1.Insert in begining 2.Insert at last 3.Insert at any random location 4.Delete from Beginning 5.Delete from last 6.Delete node after specified location 7.Search for an element 8.Show 9.Exit Enter your choice? 9