Menu

Structure de données de liste doublement liée en C ++ avec illustration

  • Principal
  • Autre
  • Structure de données de liste doublement liée en C ++ avec illustration

doubly linked list data structure c with illustration

Essayez Notre Instrument Pour Éliminer Les Problèmes

Un didacticiel approfondi sur la liste à double lien.

Une liste à double liaison est une variante de la liste à liaison unique. Nous sommes conscients que la liste liée individuellement est une collection de nœuds avec chaque nœud ayant une partie de données et un pointeur pointant vers le nœud suivant.

Une liste doublement liée est également une collection de nœuds. Chaque nœud se compose ici d'une partie de données et de deux pointeurs. Un pointeur pointe vers le nœud précédent tandis que le deuxième pointeur pointe vers le nœud suivant.

=> Consultez les didacticiels de formation approfondie sur le C ++ ici.

LISTE DOUBLE LIEN

Ce que vous apprendrez:

Doublement lié en C ++

Comme dans la liste chaînée simple, la liste doublement chaînée a également une tête et une queue. Le pointeur précédent de la tête est défini sur NULL car il s'agit du premier nœud. Le pointeur suivant du nœud de queue est défini sur NULL car il s'agit du dernier nœud.

Une présentation de base de la liste à double chaînage est présentée dans le diagramme ci-dessous.

Une présentation de base de la liste doublement chaînée

Dans la figure ci-dessus, nous voyons que chaque nœud a deux pointeurs, l'un pointant vers le nœud précédent et l'autre pointant vers le nœud suivant. Seul le premier nœud (tête) a son nœud précédent défini sur null et le dernier nœud (queue) a son pointeur suivant défini sur null.

Comme la liste doublement liée contient deux pointeurs, c'est-à-dire précédent et suivant, nous pouvons la parcourir dans les directions avant et arrière. C'est le principal avantage de la liste à double chaînette par rapport à la liste à liaison unique.

qu'est-ce que le test du système avec l'exemple

Déclaration

Dans la déclaration de style C, un nœud de la liste doublement chaînée est représenté comme suit:

struct node { struct node *prev; int data; struct node *next; };

Outre la déclaration ci-dessus, nous pouvons également représenter un nœud dans la liste doublement chaînée comme une classe en C ++. Une liste doublement liée est représentée comme une classe lorsque nous utilisons STL en C ++. Nous pouvons également implémenter une liste à double chaînage en utilisant une classe en Java.

Opérations de base

Voici quelques-unes des opérations que nous pouvons effectuer sur une liste doublement liée.

Insertion

L'opération d'insertion de la liste doublement liée insère un nouveau nœud dans la liste liée. Selon la position où le nouveau nœud doit être inséré, nous pouvons avoir les opérations d'insertion suivantes.

  • Insertion à l'avant - Insère un nouveau nœud comme premier nœud.
  • Insertion à la fin - Insère un nouveau nœud à la fin comme dernier nœud.
  • Insertion avant un nœud - Étant donné un nœud, insère un nouveau nœud avant ce nœud.
  • Insertion après un nœud - Étant donné un nœud, insère un nouveau nœud après ce nœud.

Effacement

L'opération de suppression supprime un nœud d'une position donnée dans la liste doublement liée.

  • Suppression du premier nœud - Supprime le premier nœud de la liste
  • Suppression du dernier nœud - Supprime le dernier nœud de la liste.
  • Suppression d'un nœud compte tenu des données - Compte tenu des données, l'opération met en correspondance les données avec les données du nœud dans la liste liée et supprime ce nœud.

Traversée

La traversée est une technique de visite de chaque nœud de la liste chaînée. Dans une liste doublement liée, nous avons deux types de parcours car nous avons deux pointeurs avec des directions différentes dans la liste doublement liée.

  • Traversée avant - La traversée est effectuée à l'aide du pointeur suivant qui est dans la direction avant.
  • Traversée arrière - La traversée est effectuée en utilisant le pointeur précédent qui est la direction arrière.

Sens inverse

Cette opération inverse les nœuds dans la liste doublement liée de sorte que le premier nœud devient le dernier nœud tandis que le dernier nœud devient le premier nœud.

Chercher

L'opération de recherche dans la liste à double liaison est utilisée pour rechercher un nœud particulier dans la liste liée. Pour cela, nous devons parcourir la liste jusqu'à ce qu'une donnée correspondante soit trouvée.

Insertion

Insérez un nœud à l'avant

Insérez un nœud à l

L'insertion d'un nouveau nœud au début de la liste est illustrée ci-dessus. Comme on le voit, le nouveau nœud N précédent est défini sur null. Head pointe vers le nouveau nœud. Le pointeur suivant de N pointe maintenant vers N1 et le précédent de N1 qui pointait auparavant vers Null pointe maintenant vers N.

Insérer un nœud à la fin

Insérer un nœud à la fin

L'insertion du nœud à la fin de la liste doublement liée est réalisée en pointant le pointeur suivant du nouveau nœud N sur null. Le pointeur précédent de N est pointé sur N5. Le pointeur «Suivant» de N5 est pointé vers N.

Insérer un nœud avant / après un nœud donné

Insérer un nœud avant-après un nœud donné

Comme le montre le diagramme ci-dessus, lorsque nous devons ajouter un nœud avant ou après un nœud particulier, nous modifions les pointeurs précédent et suivant des nœuds avant et après afin de pointer de manière appropriée vers le nouveau nœud. En outre, les nouveaux pointeurs de nœud sont pointés de manière appropriée vers les nœuds existants.

Le programme C ++ suivant illustre toutes les méthodes ci-dessus pour insérer des nœuds dans la liste doublement liée.

#include using namespace std; // A doubly linked list node struct Node { int data; struct Node* next; struct Node* prev; }; //inserts node at the front of the list void insert_front(struct Node** head, int new_data) { //allocate memory for New node struct Node* newNode = new Node; //assign data to new node newNode->data = new_data; //new node is head and previous is null, since we are adding at the front newNode->next = (*head); newNode->prev = NULL; //previous of head is new node if ((*head) != NULL) (*head)->prev = newNode; //head points to new node (*head) = newNode; } /* Given a node as prev_node, insert a new node after the given node */ void insert_After(struct Node* prev_node, int new_data) { //check if prev node is null if (prev_node == NULL) { coutnext = prev_node->next; //set next of prev node to newnode prev_node->next = newNode; //now set prev of newnode to prev node newNode->prev = prev_node; //set prev of new node's next to newnode if (newNode->next != NULL) newNode->next->prev = newNode; } //insert a new node at the end of the list void insert_end(struct Node** head, int new_data) { //allocate memory for node struct Node* newNode = new Node; struct Node* last = *head; //set last node value to head //set data for new node newNode->data = new_data; //new node is the last node , so set next of new node to null newNode->next = NULL; //check if list is empty, if yes make new node the head of list if (*head == NULL) { newNode->prev = NULL; *head = newNode; return; } //otherwise traverse the list to go to last node while (last->next != NULL) last = last->next; //set next of last to new node last->next = newNode; //set last to prev of new node newNode->prev = last; return; } // This function prints contents of linked list starting from the given node void displayList(struct Node* node) { struct Node* last; while (node != NULL) { coutnext; } if(node == NULL) cout

Production:

La liste doublement liée est la suivante:

1020304050NULL

Le programme ci-dessus construit une liste doublement liée en insérant les nœuds à l'aide de trois méthodes d'insertion, c'est-à-dire en insérant le nœud à l'avant, en insérant le nœud à la fin et en insérant le nœud après le nœud donné.

Ensuite, nous démontrons la même opération qu'une implémentation Java.

// Java Class for Doubly Linked List class Doubly_linkedList { Node head; // list head /* Doubly Linked list Node*/ class Node { int data; Node prev; Node next; //create a new node using constructor Node(int d) { data = d; } } // insert a node at the front of the list public void insert_front(int new_data) { /* 1. allocate node * 2. put in the data */ Node new_Node = new Node(new_data); /* 3. Make next of new node as head and previous as NULL */ new_Node.next = head; new_Node.prev = null; /* 4. change prev of head node to new node */ if (head != null) head.prev = new_Node; /* 5. move the head to point to the new node */ head = new_Node; } //insert a node after the given prev node public void Insert_After(Node prev_Node, int new_data) { //check that prev node is not null if (prev_Node == null) { System.out.println('The previous node is required,it cannot be NULL '); return; } //allocate new node and set it to data Node newNode = new Node(new_data); //set next of newNode as next of prev node newNode.next = prev_Node.next; //set new node to next of prev node prev_Node.next = newNode; //set prev of newNode as prev node newNode.prev = prev_Node; //set prev of new node's next to newnode if (newNode.next != null) newNode.next.prev = newNode; } // Add a node at the end of the list void insert_end(int new_data) { //allocate the node and set the data Node newNode = new Node(new_data); Node last = head; //set last as the head //set next of new node to null since its the last node newNode.next = null; //set new node as head if the list is null if (head == null) { newNode.prev = null; head = newNode; return; } //if list is not null then traverse it till the last node and set last next to last while (last.next != null) last = last.next; last.next = newNode; //set last next to new node newNode.prev = last; //set last as prev of new node } // display the contents of linked list starting from the given node public void displaylist(Node node) { Node last = null; while (node != null) { System.out.print(node.data + ''); last = node; node = node.next; } if(node == null) System.out.print('null'); System.out.println(); } } class Main{ public static void main(String() args) { /* Start with the empty list */ Doubly_linkedList dll = new Doubly_linkedList(); // Insert 40. dll.insert_end(40); // Insert 20 at the beginning. dll.insert_front(20); // Insert 10 at the beginning. dll.insert_front(10); // Insert 50 at the end. dll.insert_end(50); // Insert 30, after 20. dll.Insert_After(dll.head.next, 30); System.out.println('Doubly linked list created is as follows: '); dll.displaylist(dll.head); } }

Production:

La liste doublement liée créée est la suivante:

application de carte de temps pour iphone et android

1020304050null

Effacement

Un nœud peut être supprimé d'une liste doublement liée à partir de n'importe quelle position comme à partir de l'avant, de l'extrémité ou de toute autre position donnée ou données données.

Lors de la suppression d'un nœud de la liste doublement liée, nous repositionnons d'abord le pointeur pointant vers ce nœud particulier afin que les nœuds précédents et suivants n'aient aucune connexion avec le nœud à supprimer. On peut alors facilement supprimer le nœud.

Considérons la liste doublement chaînée suivante à trois nœuds A, B, C. Considérons que nous devons supprimer le nœud B.

liste doublement chaînée à trois nœuds A, B, C

Comme le montre la série ci-dessus du diagramme, nous avons démontré la suppression du nœud B de la liste chaînée donnée. La séquence d'opération reste la même même si le nœud est le premier ou le dernier. Le seul soin à prendre en compte est que si le premier nœud est supprimé, le pointeur précédent du deuxième nœud sera défini sur null.

De même, lorsque le dernier nœud est supprimé, le pointeur suivant du nœud précédent sera défini sur null. Si entre les nœuds sont supprimés, la séquence sera comme ci-dessus.

Nous quittons le programme pour supprimer un nœud d'une liste doublement liée. Notez que l'implémentation sera sur les lignes de l'implémentation d'insertion.

Liste inversée doublement liée

Inverser une liste doublement chaînée est une opération importante. En cela, nous échangeons simplement les pointeurs précédent et suivant de tous les nœuds et nous échangeons également les pointeurs de tête et de queue.

Ci-dessous, une liste doublement liée:

Inverser la liste double chaînée

L'implémentation C ++ suivante montre la liste inversée à double liaison.

#include using namespace std; //node declaration for doubly linked list struct Node { int data; struct Node *prev, *next; }; Node* newNode(int val) { Node* temp = new Node; temp->data = val; temp->prev = temp->next = nullptr; return temp; } void displayList(Node* head) { while (head->next != nullptr) { cout next; } cout next = *head; (*head)->prev = temp; (*head) = temp; } // reverse the doubly linked list void reverseList(Node** head) { Node* left = *head, * right = *head; // traverse entire list and set right next to right while (right->next != nullptr) right = right->next; //swap left and right data by moving them towards each other till they meet or cross while (left != right && left->prev != right) { // Swap left and right pointer data swap(left->data, right->data); // Advance left pointer left = left->next; // Advance right pointer right = right->prev; } } int main() { Node* headNode = newNode(5); insert(&headNode, 4); insert(&headNode, 3); insert(&headNode, 2); insert(&headNode, 1); cout << 'Original doubly linked list: ' << endl; displayList(headNode); cout << 'Reverse doubly linked list: ' << endl; reverseList(&headNode); displayList(headNode); return 0; }

Production:

Liste d'origine double chaînée:

1 2 3 4 5

Inverser la liste double chaînée:

5 4 3 2 1

Ici, nous échangeons les pointeurs gauche et droit et les déplaçons l'un vers l'autre jusqu'à ce qu'ils se rencontrent ou se croisent. Ensuite, les premier et dernier nœuds sont permutés.

Le programme suivant est l'implémentation Java pour inverser une liste doublement liée. Dans ce programme, nous utilisons également la permutation des nœuds gauche et droit comme nous l'avons fait dans notre programme précédent.

// Java Program to Reverse a doubly linked List using Data Swapping class Main{ static class Node { int data; Node prev, next; }; static Node newNode(int new_data) { Node temp = new Node(); temp.data = new_data; temp.prev = temp.next = null; return temp; } static void displayList(Node head) { while (head.next != null) { System.out.print(head.data+ ' '); head = head.next; } System.out.println( head.data ); } // Insert a new node at the head of the list static Node insert(Node head, int new_data) { Node temp = newNode(new_data); temp.next = head; (head).prev = temp; (head) = temp; return head; } // Function to reverse the list static Node reverseList(Node head) { Node left = head, right = head; // traverse the list, set right pointer to end of list while (right.next != null) right = right.next; // move left and right pointers and swap their data till they meet or cross each other while (left != right && left.prev != right) { // Swap data of left and right pointer int t = left.data; left.data = right.data; right.data = t; left = left.next; // Advance left pointer right = right.prev; // Advance right pointer } return head; } public static void main(String args()) { Node headNode = newNode(5); headNode = insert(headNode, 4); headNode = insert(headNode, 3); headNode = insert(headNode, 2); headNode = insert(headNode, 1); System.out.println('Original doubly linked list:'); displayList(headNode); System.out.println('Reversed doubly linked list:'); headNode=reverseList(headNode); displayList(headNode); } }

Production:

Liste d'origine double chaînée:

1 2 3 4 5

Liste double chaînée inversée:

5 4 3 2 1

Avantages / inconvénients par rapport à une seule liste liée

Laissez-nous discuter de certains des avantages et des inconvénients de la liste à double chaînage par rapport à la liste à liaison unique.

Avantages:

  • La liste doublement liée peut être parcourue dans les sens avant comme dans le sens arrière, contrairement à la liste à liaison unique qui ne peut être parcourue que dans le sens avant.
  • L'opération de suppression dans une liste à double lien est plus efficace par rapport à une seule liste lorsqu'un nœud donné est donné. Dans une liste à lien unique, comme nous avons besoin d'un nœud précédent pour supprimer le nœud donné, nous devons parfois parcourir la liste pour trouver le nœud précédent. Cela frappe la performance.
  • L'opération d'insertion peut être effectuée facilement dans une liste doublement liée par rapport à la liste liée individuellement.

Désavantages:

  • Comme la liste doublement liée contient un autre pointeur supplémentaire, c'est-à-dire précédent, l'espace mémoire occupé par la liste doublement liée est plus grand par rapport à la liste liée individuellement.
  • Étant donné que deux pointeurs sont présents, c'est-à-dire précédent et suivant, toutes les opérations effectuées sur la liste doublement liée doivent prendre soin de ces pointeurs et les maintenir, ce qui entraîne un goulot d'étranglement des performances.

Applications de la liste doublement liée

Une liste doublement liée peut être appliquée dans divers scénarios et applications réels, comme indiqué ci-dessous.

  • Un jeu de cartes dans un jeu est un exemple classique d'une liste doublement liée. Etant donné que chaque carte dans un jeu de cartes a la carte précédente et la carte suivante disposées séquentiellement, ce jeu de cartes peut être facilement représenté en utilisant une liste doublement liée.
  • Historique / cache du navigateur - Le cache du navigateur a une collection d'URL et peut être parcouru à l'aide des boutons avant et arrière est un autre bon exemple qui peut être représenté sous la forme d'une liste doublement liée.
  • Le plus récemment utilisé (MRU) peut également être représenté sous la forme d'une liste à double chaînage.
  • D'autres structures de données comme Stacks, table de hachage, l'arbre binaire peuvent également être construits ou programmés à l'aide d'une liste doublement chaînée.

Conclusion

Une liste à double liaison est une variante de la liste à liaison unique. Elle diffère de la liste liée à un seul lien en ce que chaque nœud contient un pointeur supplémentaire vers le nœud précédent avec le pointeur suivant.

Cette présence d'un pointeur supplémentaire facilite les opérations d'insertion et de suppression sur la liste doublement liée mais nécessite en même temps une mémoire supplémentaire pour stocker ces pointeurs supplémentaires.

Comme discuté déjà, la liste doublement liée a diverses utilisations dans des scénarios en temps réel comme le cache du navigateur, les MRU, etc. Nous pouvons également représenter d'autres structures de données comme des arbres, des tables de hachage, etc. en utilisant une liste doublement liée.

Dans notre prochain didacticiel, nous en apprendrons davantage sur la liste liée circulaire.

=> Lisez la série de formations populaires C ++ ici.

lecture recommandée

^