linked list data structure c with illustration
Une étude détaillée de la liste liée en C ++.
Une liste liée est une structure de données dynamique linéaire pour stocker des éléments de données. Nous avons déjà vu des tableaux dans nos rubriques précédentes sur le C ++ de base. Nous savons également que les tableaux sont une structure de données linéaire qui stocke des éléments de données dans des emplacements contigus.
Contrairement aux tableaux, la liste liée ne stocke pas les éléments de données dans des emplacements mémoire contigus.
Une liste chaînée se compose d'éléments appelés «nœuds» qui contiennent deux parties. La première partie stocke les données réelles et la seconde partie a un pointeur qui pointe vers le nœud suivant. Cette structure est généralement appelée «liste chaînée unique».
=> Découvrez les meilleurs didacticiels de formation C ++ ici.
Ce que vous apprendrez:
Liste liée en C ++
Nous examinerons en détail la liste liée individuellement dans ce didacticiel.
Le diagramme suivant montre la structure d'une liste liée individuellement.
Comme indiqué ci-dessus, le premier nœud de la liste chaînée est appelé «head» tandis que le dernier nœud est appelé «Tail». Comme nous le voyons, le dernier nœud de la liste chaînée aura son prochain pointeur comme nul car il n'aura aucune adresse mémoire pointée.
Puisque chaque nœud a un pointeur vers le nœud suivant, les éléments de données de la liste liée n'ont pas besoin d'être stockés à des emplacements contigus. Les nœuds peuvent être dispersés dans la mémoire. Nous pouvons accéder aux nœuds à tout moment car chaque nœud aura une adresse du nœud suivant.
Nous pouvons ajouter des éléments de données à la liste liée ainsi que supprimer facilement des éléments de la liste. Ainsi, il est possible d'agrandir ou de réduire dynamiquement la liste chaînée. Il n'y a pas de limite supérieure sur le nombre d'éléments de données pouvant figurer dans la liste liée. Ainsi, tant que la mémoire est disponible, nous pouvons avoir autant d'éléments de données ajoutés à la liste chaînée.
Outre l'insertion et la suppression faciles, la liste liée ne gaspille pas non plus d'espace mémoire car nous n'avons pas besoin de spécifier à l'avance le nombre d'éléments dont nous avons besoin dans la liste liée. Le seul espace occupé par la liste liée est pour stocker le pointeur vers le nœud suivant, ce qui ajoute un peu de surcharge.
Ensuite, nous discuterons des différentes opérations qui peuvent être effectuées sur une liste chaînée.
Opérations
Tout comme les autres structures de données, nous pouvons également effectuer diverses opérations pour la liste chaînée. Mais contrairement aux tableaux, dans lesquels nous pouvons accéder directement à l'élément en utilisant l'indice même s'il est quelque part entre les deux, nous ne pouvons pas faire le même accès aléatoire avec une liste chaînée.
Pour accéder à n'importe quel nœud, nous devons parcourir la liste liée depuis le début et ce n'est qu'alors que nous pouvons accéder au nœud souhaité. Par conséquent, accéder aux données de manière aléatoire à partir de la liste chaînée s'avère coûteux.
fusion du code source de tri c ++
Nous pouvons effectuer diverses opérations sur une liste chaînée comme indiqué ci-dessous:
# 1) Insertion
L'opération d'insertion d'une liste liée ajoute un élément à la liste liée. Bien que cela puisse paraître simple, étant donné la structure de la liste liée, nous savons que chaque fois qu'un élément de données est ajouté à la liste liée, nous devons changer les pointeurs suivants des nœuds précédent et suivant du nouvel élément que nous avons inséré.
La deuxième chose que nous devons considérer est l'endroit où la nouvelle donnée doit être ajoutée.
Il y a trois positions dans la liste liée où un élément de données peut être ajouté.
# 1) Au début de la liste chaînée
Une liste chaînée est affichée ci-dessous 2-> 4-> 6-> 8-> 10. Si nous voulons ajouter un nouveau nœud 1, comme premier nœud de la liste, alors la tête pointant vers le nœud 2 pointera maintenant vers 1 et le pointeur suivant du nœud 1 aura une adresse mémoire du nœud 2 comme indiqué ci-dessous chiffre.
Ainsi, la nouvelle liste chaînée devient 1-> 2-> 4-> 6-> 8-> 10.
# 2) Après le nœud donné
Ici, un nœud est donné et nous devons ajouter un nouveau nœud après le nœud donné. Dans la liste liée ci-dessous a-> b-> c-> d -> e, si nous voulons ajouter un nœud f après le nœud c, la liste liée ressemblera à ceci:
Ainsi dans le schéma ci-dessus, on vérifie si le nœud donné est présent. S'il est présent, nous créons un nouveau nœud f. Ensuite, nous pointons le pointeur suivant du nœud c pour pointer vers le nouveau nœud f. Le pointeur suivant du nœud f pointe maintenant vers le nœud d.
# 3) À la fin de la liste liée
Dans le troisième cas, nous ajoutons un nouveau nœud à la fin de la liste chaînée. Considérons que nous avons la même liste chaînée a-> b-> c-> d-> e et que nous devons ajouter un nœud f à la fin de la liste. La liste liée ressemblera à celle ci-dessous après l'ajout du nœud.
Ainsi, nous créons un nouveau nœud f. Ensuite, le pointeur de queue pointant vers null est pointé vers f et le pointeur suivant du nœud f est pointé vers null. Nous avons implémenté les trois types de fonctions d'insertion dans le programme C ++ ci-dessous.
En C ++, nous pouvons déclarer une liste chaînée en tant que structure ou en tant que classe. Déclarer une liste chaînée en tant que structure est une déclaration traditionnelle de style C. Une liste chaînée en tant que classe est utilisée dans le C ++ moderne, principalement en utilisant une bibliothèque de modèles standard.
Dans le programme suivant, nous avons utilisé la structure pour déclarer et créer une liste chaînée. Il aura des données et un pointeur vers l'élément suivant comme membres.
#include using namespace std; // A linked list node struct Node { int data; struct Node *next; }; //insert a new node in front of the list void push(struct Node** head, int node_data) { /* 1. create and allocate node */ struct Node* newNode = new Node; /* 2. assign data to node */ newNode->data = node_data; /* 3. set next of new node as head */ newNode->next = (*head); /* 4. move the head to point to the new node */ (*head) = newNode; } //insert new node after a given node void insertAfter(struct Node* prev_node, int node_data) { /*1. check if the given prev_node is NULL */ if (prev_node == NULL) { coutnext = prev_node->next; /* 5. move the next of prev_node as new_node */ prev_node->next = newNode; } /* insert new node at the end of the linked list */ void append(struct Node** head, int node_data) { /* 1. create and allocate node */ struct Node* newNode = new Node; struct Node *last = *head; /* used in step 5*/ /* 2. assign data to the node */ newNode->data = node_data; /* 3. set next pointer of new node to null as its the last node*/ newNode->next = NULL; /* 4. if list is empty, new node becomes first node */ if (*head == NULL) { *head = newNode; return; } /* 5. Else traverse till the last node */ while (last->next != NULL) last = last->next; /* 6. Change the next of last node */ last->next = newNode; return; } // display linked list contents void displayList(struct Node *node) { //traverse the list to display each node while (node != NULL) { coutnext; } if(node== NULL) cout Production:
Liste chaînée finale:
30–> 20–> 50–> 10–> 40–> null
Ensuite, nous implémentons l'opération d'insertion de liste chaînée en Java. En langage Java, la liste chaînée est implémentée en tant que classe. Le programme ci-dessous est similaire en logique au programme C ++, la seule différence est que nous utilisons une classe pour la liste chaînée.
class LinkedList { Node head; // head of list //linked list node declaration class Node { int data; Node next; Node(int d) {data = d; next = null; } } /* Insert a new node at the front of the list */ public void push(int new_data) { //allocate and assign data to the node Node newNode = new Node(new_data); //new node becomes head of linked list newNode.next = head; //head points to new node head = newNode; } // Given a node,prev_node insert node after prev_node public void insertAfter(Node prev_node, int new_data) { //check if prev_node is null. if (prev_node == null) { System.out.println('The given node is required and cannot be null'); return; } //allocate node and assign data to it Node newNode = new Node(new_data); //next of new Node is next of prev_node newNode.next = prev_node.next; //prev_node->next is the new node. prev_node.next = newNode; } //inserts a new node at the end of the list public void append(intnew_data) { //allocate the node and assign data Node newNode = new Node(new_data); //if linked list is empty, then new node will be the head if (head == null) { head = new Node(new_data); return; } //set next of new node to null as this is the last node newNode.next = null; // if not the head node traverse the list and add it to the last Node last = head; while (last.next != null) last = last.next; //next of last becomes new node last.next = newNode; return; } //display contents of linked list public void displayList() { Node pnode = head; while (pnode != null) { System.out.print(pnode.data+'-->'); pnode = pnode.next; } if(pnode == null) System.out.print('null'); } } //Main class to call linked list class functions and construct a linked list class Main{ public static void main(String[] args) { /* create an empty list */ LinkedList lList = new LinkedList(); // Insert 40. lList.append(40); // Insert 20 at the beginning. lList.push(20); // Insert 10 at the beginning. lList.push(10); // Insert 50 at the end. lList.append(50); // Insert 30, after 20. lList.insertAfter(lList.head.next, 30); System.out.println('
Final linked list: '); lList. displayList (); } }
Production:
afficher la liste chaînée c ++
Liste chaînée finale:
10–> 20–> 30–> 40–> 50–> null
Dans les deux programmes ci-dessus, C ++ ainsi que Java, nous avons des fonctions séparées pour ajouter un nœud devant la liste, la fin de la liste et entre les listes données dans un nœud. En fin de compte, nous imprimons le contenu de la liste créée en utilisant les trois méthodes.
# 2) Suppression
Tout comme l'insertion, la suppression d'un nœud d'une liste liée implique également différentes positions à partir desquelles le nœud peut être supprimé. Nous pouvons supprimer le premier nœud, le dernier nœud ou un kième nœud aléatoire de la liste chaînée. Après la suppression, nous devons ajuster le pointeur suivant et les autres pointeurs de la liste liée de manière appropriée afin de conserver la liste liée intacte.
Dans l'implémentation C ++ suivante, nous avons donné deux méthodes de suppression, à savoir la suppression du premier nœud de la liste et la suppression du dernier nœud de la liste. Nous créons d'abord une liste en ajoutant des nœuds à la tête. Ensuite, nous affichons le contenu de la liste après l'insertion et chaque suppression.
#include using namespace std; /* Link list node */ struct Node { int data; struct Node* next; }; //delete first node in the linked list Node* deleteFirstNode(struct Node* head) { if (head == NULL) return NULL; // Move the head pointer to the next node Node* tempNode = head; head = head->next; delete tempNode; return head; } //delete last node from linked list Node* removeLastNode(struct Node* head) { if (head == NULL) return NULL; if (head->next == NULL) { delete head; return NULL; } // first find second last node Node* second_last = head; while (second_last->next->next != NULL) second_last = second_last->next; // Delete the last node delete (second_last->next); // set next of second_last to null second_last->next = NULL; return head; } // create linked list by adding nodes at head void push(struct Node** head, int new_data) { struct Node* newNode = new Node; newNode->data = new_data; newNode->next = (*head); (*head) = newNode; } // main function int main() { /* Start with the empty list */ Node* head = NULL; // create linked list push(&head, 2); push(&head, 4); push(&head, 6); push(&head, 8); push(&head, 10); Node* temp; cout<<'Linked list created ' Production:
Liste liée créée
10–> 8–> 6–> 4–> 2–
> NULL
Liste liée après la suppression du nœud principal
8–> 6–> 4–> 2–
> NULL
Liste liée après suppression du dernier nœud
8–> 6–> 4–> NULL
Vient ensuite l'implémentation Java pour supprimer des nœuds de la liste liée. La logique d'implémentation est la même que celle utilisée dans le programme C ++. La seule différence est que la liste chaînée est déclarée en tant que classe.
class Main { // Linked list node / static class Node { int data; Node next; }; // delete first node of linked list static Node deleteFirstNode(Node head) { if (head == null) return null; // Move the head pointer to the next node Node temp = head; head = head.next; return head; } // Delete the last node in linked list static Node deleteLastNode(Node head) { if (head == null) return null; if (head.next == null) { return null; } // search for second last node Node second_last = head; while (second_last.next.next != null) second_last = second_last.next; // set next of second last to null second_last.next = null; return head; } // Add nodes to the head and create linked list static Node push(Node head, int new_data) { Node newNode = new Node(); newNode.data = new_data; newNode.next = (head); (head) = newNode; return head; } //main function public static void main(String args[]) { // Start with the empty list / Node head = null; //create linked list head = push(head, 1); head = push(head, 3); head = push(head, 5); head = push(head, 7); head = push(head, 9); Node temp; System.out.println('Linked list created :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); head = deleteFirstNode(head); System.out.println('Linked list after deleting head node :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); head = deleteLastNode(head); System.out.println('Linked list after deleting last node :'); for (temp = head; temp != null; temp = temp.next) System.out.print(temp.data + '-->'); if(temp == null) System.out.println('null'); } }
Production:
Liste liée créée:
9–> 7–> 5–> 3–> 1–
> nul
Liste liée après la suppression du nœud principal:
7–> 5–> 3–> 1–
> nul
Liste liée après la suppression du dernier nœud:
7–> 5–> 3–> null
Compter le nombre de nœuds
L'opération de comptage du nombre de nœuds peut être effectuée en parcourant la liste chaînée. Nous avons déjà vu dans l'implémentation ci-dessus que chaque fois que nous devons insérer / supprimer un nœud ou afficher le contenu de la liste liée, nous devons parcourir la liste liée depuis le début.
Garder un compteur et l'incrémenter au fur et à mesure que nous traversons chaque nœud nous donnera le décompte du nombre de nœuds présents dans la liste chaînée. Nous laisserons ce programme aux lecteurs pour qu'il l'implémente.
Tableaux et listes liées
Après avoir vu les opérations et la mise en œuvre de la liste chaînée, comparons comment les tableaux et la liste chaînée sont équitables les uns par rapport aux autres.
Tableaux Listes liées Les tableaux ont une taille fixe La taille de la liste liée est dynamique L'insertion d'un nouvel élément coûte cher L'insertion / suppression est plus facile L'accès aléatoire est autorisé Accès aléatoire impossible Les éléments sont à un emplacement contigu Les éléments ont un emplacement non contigu Aucun espace supplémentaire n'est requis pour le pointeur suivant Espace mémoire supplémentaire requis pour le pointeur suivant
Applications
Comme les tableaux et les listes liées sont tous deux utilisés pour stocker des éléments et sont des structures de données linéaires, ces deux structures peuvent être utilisées de manière similaire pour la plupart des applications.
Certaines des applications pour les listes liées sont les suivantes:
- Une liste chaînée peut être utilisée pour implémenter des piles et des files d'attente.
- Une liste chaînée peut également être utilisée pour implémenter des graphiques chaque fois que nous devons représenter des graphiques sous forme de listes de contiguïté.
- Un polynôme mathématique peut être stocké sous forme de liste chaînée.
- Dans le cas de la technique de hachage, les buckets utilisés dans le hachage sont implémentés à l'aide des listes liées.
- Chaque fois qu'un programme nécessite une allocation dynamique de mémoire, nous pouvons utiliser une liste chaînée car les listes liées fonctionnent plus efficacement dans ce cas.
Conclusion
Les listes liées sont les structures de données utilisées pour stocker les éléments de données de manière linéaire mais à des emplacements non contigus. Une liste liée est une collection de nœuds qui contiennent une partie de données et un pointeur suivant qui contient l'adresse mémoire de l'élément suivant dans la liste.
Le dernier élément de la liste a son pointeur suivant défini sur NULL, indiquant ainsi la fin de la liste. Le premier élément de la liste est appelé la tête. La liste liée prend en charge diverses opérations telles que l'insertion, la suppression, le parcours, etc. En cas d'allocation de mémoire dynamique, les listes liées sont préférées aux tableaux.
Les listes liées coûtent cher en ce qui concerne leur parcours car nous ne pouvons pas accéder aléatoirement aux éléments comme les tableaux. Cependant, les opérations d'insertion-suppression sont moins coûteuses par rapport aux tableaux.
Nous avons tout appris sur les listes chaînées linéaires dans ce didacticiel. Les listes liées peuvent également être circulaires ou doubles. Nous examinerons en profondeur ces listes dans nos prochains tutoriels.
=> Vérifiez ici pour une série complète de formations C ++.
lecture recommandée
- Structure de données de liste liée circulaire en C ++ avec illustration
- Structure de données de liste doublement liée en C ++ avec illustration
- Structure de données de file d'attente en C ++ avec illustration
- Empiler la structure de données en C ++ avec illustration
- Structure de données de file d'attente prioritaire en C ++ avec illustration
- Top 15 des meilleurs outils d'exploration de données gratuits: la liste la plus complète
- 15 meilleurs outils ETL en 2021 (une liste complète mise à jour)
- Introduction aux structures de données en C ++