Structure de données - Liste doublement liée

La liste double liée est une variante de la liste liée dans laquelle la navigation est possible dans les deux sens, en avant et en arrière facilement par rapport à la liste liée unique. Voici les termes importants pour comprendre le concept de liste à double chaînage.

  • Link - Chaque lien d'une liste liée peut stocker une donnée appelée élément.

  • Next - Chaque lien d'une liste liée contient un lien vers le lien suivant appelé Suivant.

  • Prev - Chaque lien d'une liste liée contient un lien vers le lien précédent appelé Prev.

  • LinkedList - Une liste liée contient le lien de connexion vers le premier lien appelé Premier et vers le dernier lien appelé Dernier.

Représentation de liste doublement liée

Conformément à l'illustration ci-dessus, voici les points importants à considérer.

  • La liste doublement liée contient un élément de lien appelé premier et dernier.

  • Chaque lien porte un (des) champ (s) de données et deux champs de lien appelés next et prev.

  • Chaque lien est lié à son lien suivant en utilisant son lien suivant.

  • Chaque lien est lié à son lien précédent en utilisant son lien précédent.

  • Le dernier lien porte un lien nul pour marquer la fin de la liste.

Opérations de base

Voici les opérations de base prises en charge par une liste.

  • Insertion - Ajoute un élément au début de la liste.

  • Deletion - Supprime un élément au début de la liste.

  • Insert Last - Ajoute un élément à la fin de la liste.

  • Delete Last - Supprime un élément de la fin de la liste.

  • Insert After - Ajoute un élément après un élément de la liste.

  • Delete - Supprime un élément de la liste à l'aide de la touche.

  • Display forward - Affiche la liste complète d'une manière avant.

  • Display backward - Affiche la liste complète à l'envers.

Opération d'insertion

Le code suivant illustre l'opération d'insertion au début d'une liste doublement liée.

Exemple

//insert link at the first location
void insertFirst(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //update first prev link
      head->prev = link;
   }

   //point it to old first link
   link->next = head;
	
   //point first to new first link
   head = link;
}

Opération de suppression

Le code suivant illustre l'opération de suppression au début d'une liste doublement liée.

Exemple

//delete first item
struct node* deleteFirst() {

   //save reference to first link
   struct node *tempLink = head;
	
   //if only one link
   if(head->next == NULL) {
      last = NULL;
   } else {
      head->next->prev = NULL;
   }
	
   head = head->next;
	
   //return the deleted link
   return tempLink;
}

Insertion à la fin d'une opération

Le code suivant illustre l'opération d'insertion à la dernière position d'une liste doublement liée.

Exemple

//insert link at the last location
void insertLast(int key, int data) {

   //create a link
   struct node *link = (struct node*) malloc(sizeof(struct node));
   link->key = key;
   link->data = data;
	
   if(isEmpty()) {
      //make it the last link
      last = link;
   } else {
      //make link a new last link
      last->next = link;     
      
      //mark old last node as prev of new link
      link->prev = last;
   }

   //point last to new last node
   last = link;
}

Pour voir l'implémentation en langage de programmation C, veuillez cliquer ici .