Liste doublement chaînée : C++, Python (Code Exemple)

Qu'est-ce qu'une liste doublement chaînée ?

Dans une liste doublement chaînée, chaque nœud est lié au nœud précédent et au nœud suivant. Chaque nœud est composé de trois éléments : un élément contenant les données, et deux pointeurs vers le nœud suivant et le nœud précédent. Ces pointeurs permettent de naviguer dans la liste.

Voici la structure de base d'une liste doublement chaînée.

Structure d'une liste doublement liée

Chaque liste chaînée possède un nœud de tête et un nœud de queue. Le nœud de tête n'a pas de nœud de queue. actu (pointeur précédent) nœud, et le nœud de queue n'en a pas next nœud.

Voici quelques termes importants concernant une liste doublement chaînée :

• Précédent: Chaque nœud est lié à son nœud précédent. Il est utilisé comme pointeur ou lien.
• Next: Chaque nœud est lié à son nœud suivant. Il est utilisé comme pointeur ou lien.
• Dates: Ceci sert à stocker des données dans un nœud. Les données peuvent contenir d'autres Structures de données À l'intérieur, par exemple, des chaînes de caractères, des dictionnaires, des ensembles, des tables de hachage et d'autres structures peuvent être stockées dans le champ de données.

Voici la structure de base d'un nœud unique dans une liste doublement chaînée :

Structure d'un nœud dans une liste doublement chaînée

Operation de liste doublement chaînée

Les opérations sur une liste doublement chaînée comprennent l'ajout, la suppression, l'insertion et le retrait de nœuds, ainsi que le parcours de la liste de haut en bas ou de bas en haut.

Voici la liste des opérations qui peuvent être implémentées sur une liste doublement chaînée :

• Insertion devant
• Insertion au niveau de la queue ou du dernier nœud
• Insertion après un nœud
• Insertion avant un nœud
• Suppression du recto
• Suppression de la queue
• Rechercher et supprimer un nœud
• Traverser tête-bêche
• Traverser la queue vers la tête

L'implémentation et le pseudo-code de chacune de ces opérations sont présentés ci-dessous.

Insertion en tête d'une liste doublement chaînée

L'insertion en tête consiste à créer un nœud dans la liste chaînée et à le placer au début de la liste.

Par exemple, il existe un nœud donné 15Il faut l'ajouter comme nœud principal.

Deux conditions importantes s'appliquent lors de l'exécution de cette opération :

1. Le nouveau nœud devient le nœud principal si la liste doublement chaînée est vide.
2. S'il existe déjà un nœud principal, le nœud principal précédent est remplacé par le nouveau nœud.

Voici le pseudo-code de cette opération :

function insertAtFront(ListHead, value):
  newNode = Node()
  newNode.value = value
  ListHead.prev = newNode
  newNode.next = ListHead
  newNode.prev = NULL
  return ListHead

Insertion dans le nœud avant

Insertion à la fin d'une liste doublement chaînée

L'insertion en fin de liste consiste à créer un nœud dans la liste chaînée et à le placer à la fin.

Deux méthodes permettent de réaliser cette opération :

• Méthode 1: Commencez à parcourir la liste doublement chaînée à partir de sa tête jusqu'à next devient nul. Ensuite, reliez le nouveau nœud au next aiguille.
• Méthode 2: Prenez le dernier nœud de la liste doublement chaînée. Ensuite, le next Le pointeur du dernier nœud pointe vers le nouveau nœud. Ce nouveau nœud devient le nœud de queue.

Voici le pseudo-code pour l'insertion au niveau du nœud terminal :

function insertAtTail(ListHead, value):
  newNode = Node()
  newNode.value = value
  newNode.next = NULL
  while ListHead.next is not NULL:
    ListHead = ListHead.next
  newNode.prev = ListHead
  ListHead.next = newNode
  return ListHead

Insertion en fin de liste chaînée

Insertion après un nœud

Considérons une liste doublement chaînée existante comme la suivante :

L'objectif est d'insérer un nœud donné qui sera lié après le nœud ayant la valeur 12.

Étape 1) Parcourez le chemin depuis le nœud de tête jusqu'au dernier nœud. Vérifiez quel nœud possède la valeur. 12.

Étape 2) Créez un nouveau nœud et assignez-le comme pointeur suivant du nœud 12L’ next Le numéro du nouveau nœud sera 15.

Voici le pseudo-code pour insérer un nœud après un nœud dans une liste doublement chaînée :

function insertAfter(ListHead, searchItem, value):
  List = ListHead
  newNode = Node()
  newNode.value = value
  while List.value is not equal searchItem:
    List = List.next
  newNode.next = List.next
  newNode.prev = List
  List.next = newNode

Insertion après un nœud

Insertion avant un nœud

Cette opération est similaire à une insertion après un nœud. On recherche la valeur d'un nœud spécifique, puis on crée un nouveau nœud et on l'insère avant le nœud recherché.

Pour insérer un nœud donné 15 avant le nœud 12, Suivez ces étapes:

Étape 1) Parcourez la liste chaînée du nœud principal au nœud final.

Étape 2) Vérifiez si le pointeur suivant du nœud actuel a la valeur 12.

Étape 3) Insérez le nouveau nœud comme next nœud du nœud actuel.

Voici le pseudo-code pour insérer un nœud avant un autre nœud dans une liste doublement chaînée :

function insertBefore(ListHead, searchItem, value):
  List = ListHead
  newNode = Node()
  newNode.value = value
  while List.next.value is not equal searchItem:
    List = List.next
  newNode.next = List.next
  newNode.prev = List
  List.next = newNode

Insérer un nœud avant un nœud

Supprimer la tête de la liste doublement chaînée

Le nœud de tête d'une liste doublement chaînée n'a aucun nœud précédent. next Lorsque le nœud de tête actuel est supprimé, le pointeur devient le nouveau nœud de tête. Il est également nécessaire de libérer la mémoire occupée par un nœud supprimé.

Voici les étapes pour supprimer le nœud principal :

Étape 1) Attribuez une variable au nœud principal actuel.

Étape 2) Rendez-vous sur next nœud du nœud principal actuel et faites le actu Pointeur NULL. Cela déconnecte le deuxième nœud du premier nœud.

Étape 3) Libérez la mémoire occupée par le nœud principal précédent.

Voici le pseudo-code pour supprimer la tête d'une liste doublement chaînée :

function deleteHead(ListHead):
  PrevHead = ListHead
  ListHead = ListHead.next
  ListHead.prev = NULL
  PrevHead.next = NULL
  free memory(PrevHead)
  return ListHead

Suppression du nœud principal

Il est impératif de libérer la mémoire allouée après toute suppression. À défaut, la mémoire correspondant au bloc supprimé reste occupée pendant toute la durée d'exécution du programme, et aucune autre application ne peut utiliser ce segment de mémoire.

Supprimer la queue de la liste doublement chaînée

Cette opération est similaire à la suppression de la tête. Au lieu de la tête, c'est la queue qui est supprimée. Pour identifier un nœud comme étant la queue, vérifiez si le pointeur suivant est nul. Après la suppression de la queue, la mémoire doit être libérée.

Cette opération est également connue sous le nom de suppression par l'arrière.

Voici les étapes pour ce faire:

Étape 1) Parcourir la liste doublement chaînée jusqu'au dernier nœud.

Étape 2) Attribuez une variable ou un pointeur au nœud de queue.

Étape 3) Mettez le next pointeur vers NULL et libérer la mémoire du nœud de queue.

Voici le pseudo-code pour supprimer le nœud terminal :

function deleteTail(ListHead):
  head = ListHead
  while ListHead.next is not NULL:
    ListHead = ListHead.next
  Tail = ListHead
  ListHead.prev.next = NULL
  free memory(Tail)
  return head

Rechercher et supprimer un nœud d'une liste doublement chaînée

Cette opération recherche la valeur d'un nœud spécifique et supprime ce nœud. Une recherche linéaire est nécessaire car la liste chaînée est une structure de données linéaire. Après la suppression, la mémoire doit être libérée.

Voici les étapes pour rechercher et supprimer un nœud dans une liste doublement chaînée :

Étape 1) Parcourez la liste chaînée à partir de la tête jusqu'à ce que la valeur du nœud soit égale à l'élément recherché.

Étape 2) Attribuer une variable supprimerNode au nœud correspondant.

Étape 3) Liez le nœud précédent du supprimerNode à son nœud suivant, et définir le nœud suivant actu pointeur vers le nœud précédent.

Étape 4) Libérez la mémoire de supprimerNode.

Voici le pseudo-code pour rechercher et supprimer un nœud dans une liste chaînée :

function searchAndDelete(ListHead, searchItem):
  head = ListHead
  while head.value not equals searchItem:
    head = head.next
  deleteNode = head
  head.prev.next = head.next
  if head.next is not NULL:
    head.next.prev = head.prev
  free memory(deleteNode)
  return ListHead

Opération de recherche et de suppression

Parcourir une liste doublement chaînée de l'avant vers l'arrière

Le parcours à partir du nœud de tête itère sur le nœud suivant jusqu'à rencontrer la valeur NULL. La valeur de chaque nœud peut être affichée lors du parcours. Voici les étapes du parcours dans le sens direct :

Étape 1) Attribuez un pointeur ou une variable au nœud principal actuel.

Étape 2) Passez au nœud suivant de la tête jusqu'à obtenir NULL.

Étape 3) Afficher les données du nœud à chaque itération.

Étape 4) Renvoie le nœud principal.

Voici le pseudo-code pour parcourir une liste doublement chaînée en partant du début :

function traverseFromFront(ListHead):
  head = ListHead
  while head not equals NULL:
    print head.data
    head = head.next
  return ListHead

Le retour n'est pas obligatoire. Cependant, il est recommandé de retourner le nœud principal après les opérations.

Parcourir une liste doublement chaînée de l'arrière vers l'arrière

Cette opération est l'inverse du parcours depuis l'avant. L'approche est la même à une petite différence près : atteindre d'abord le nœud final, puis revenir en arrière jusqu'au point de départ en utilisant le actu aiguille.

Voici les étapes pour parcourir une liste doublement chaînée en partant de la fin :

Étape 1) Parcourez le trajet jusqu'à atteindre le nœud terminal.

Étape 2) À partir du nœud terminal, parcourez en utilisant actu jusqu'à ce que le nœud précédent soit NULL. actu Le pointeur est nul pour le nœud principal.

Étape 3) À chaque itération, imprimer les données du nœud.

Voici le pseudo-code pour parcourir le chemin depuis l'arrière :

function traverseFromBack(ListHead):
  head = ListHead
  while head.next is not NULL:
    head = head.next
  tail = head
  while tail is not NULL:
    print tail.value
    tail = tail.prev
  return ListHead

Différence entre une liste simplement chaînée et une liste doublement chaînée

La principale différence entre une liste simplement chaînée et une liste doublement chaînée réside dans le nombre de liens que chaque nœud contient.

Voici la différence entre les nœuds d'une liste simplement chaînée et ceux d'une liste doublement chaînée :

Liste doublement liée dans C++

Vous trouverez ci-dessous une liste complète C++ Implémentation d'une liste doublement chaînée avec opérations d'insertion, de suppression, de recherche et de parcours.

#include<iostream>
using namespace std;
struct node{
  int data;
  struct node *next;
  struct node *prev;
};
void insertFront(node* &listHead, int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  if(listHead != NULL){
    listHead->prev = newNode;
    newNode->next = listHead;
  }
  listHead = newNode;
  cout<<"Added "<<value<<" at the front"<<endl;
}
void insertEnd(node* &listHead, int value){
  if(listHead == NULL){
    insertFront(listHead, value);
    return;
  }
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  node *head = listHead;
  while(head->next != NULL){
    head = head->next;
  }
  head->next = newNode;
  newNode->prev = head;
  cout<<"Added "<<value<<" at the end"<<endl;
}
void insertAfter(node* &listHead, int searchValue, int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  node *head = listHead;
  while(head->next != NULL && head->data != searchValue){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  newNode->prev = head;
  if(newNode->next != NULL){
    newNode->next->prev = newNode;
  }
  cout<<"Inserted "<<value<<" after node "<<searchValue<<endl;
}
void insertBefore(node* &listHead, int searchValue, int value){
  node* newNode = new node();
  newNode->data = value;
  newNode->prev = NULL;
  newNode->next = NULL;
  node *head = listHead;
  while(head->next != NULL && head->next->data != searchValue){
    head = head->next;
  }
  newNode->next = head->next;
  head->next = newNode;
  newNode->prev = head;
  if(newNode->next != NULL){
    newNode->next->prev = newNode;
  }
  cout<<"Inserted "<<value<<" before node "<<searchValue<<endl;
}
void traverseFromFront(node *listHead){
  node* head = listHead;
  cout<<"Traversal from head:\t";
  while(head != NULL){
    cout<<head->data<<"\t";
    head = head->next;
  }
  cout<<endl;
}
void traverseFromEnd(node *listHead){
  node* head = listHead;
  cout<<"Traversal from tail:\t";
  while(head->next != NULL){
    head = head->next;
  }
  node *tail = head;
  while(tail != NULL){
    cout<<tail->data<<"\t";
    tail = tail->prev;
  }
  cout<<endl;
}
void searchAndDelete(node **listHead, int searchItem){
  node* head = (*listHead);
  while(head != NULL && head->data != searchItem){
    head = head->next;
  }
  if(*listHead == NULL || head == NULL) return;
  if((*listHead)->data == head->data){
    *listHead = head->next;
  }
  if(head->next != NULL){
    head->next->prev = head->prev;
  }
  if(head->prev != NULL){
    head->prev->next = head->next;
  }
  free(head);
  cout<<"Deleted Node\t"<<searchItem<<endl;
}
int main(){
  node *head = NULL;
  insertFront(head, 5);
  insertFront(head, 6);
  insertFront(head, 7);
  insertEnd(head, 9);
  insertEnd(head, 10);
  insertAfter(head, 5, 11);
  insertBefore(head, 5, 20);
  traverseFromFront(head);
  traverseFromEnd(head);
  searchAndDelete(&head, 7);
  traverseFromFront(head);
  traverseFromEnd(head);
}

Sortie

Added 5 at the front
Added 6 at the front
Added 7 at the front
Added 9 at the end
Added 10 at the end
Inserted 11 after node 5
Inserted 20 before node 5
Traversal from head:    7  6  20  5  11  9  10
Traversal from tail:    10  9  11  5  20  6  7
Deleted Node    7
Traversal from head:    6  20  5  11  9  10
Traversal from tail:    10  9  11  5  20  6

Liste doublement liée dans Python

Vous trouverez ci-dessous une liste complète Python Implémentation d'une liste doublement chaînée utilisant des classes pour les nœuds et la liste elle-même.

class Node:
  def __init__(self, data=None, prev=None, next=None):
    self.data = data
    self.next = next
    self.prev = prev
class DoublyLinkedList:
  def __init__(self):
    self.head = None
  def insertFront(self, val):
    newNode = Node(data=val)
    newNode.next = self.head
    if self.head is not None:
      self.head.prev = newNode
    self.head = newNode
    print("Added {} at the front".format(val))
  def insertEnd(self, val):
    newNode = Node(data=val)
    if self.head is None:
      self.head = newNode
      print("Added {} at the end".format(val))
      return
    temp = self.head
    while temp.next is not None:
      temp = temp.next
    temp.next = newNode
    newNode.prev = temp
    print("Added {} at the end".format(val))
  def traverseFromFront(self):
    temp = self.head
    print("Traversing from head:\t", end="")
    while temp is not None:
      print("{}\t".format(temp.data), end="")
      temp = temp.next
    print()
  def traverseFromEnd(self):
    temp = self.head
    print("Traversing from tail:\t", end="")
    while temp.next is not None:
      temp = temp.next
    tail = temp
    while tail is not None:
      print("{}\t".format(tail.data), end="")
      tail = tail.prev
    print()
  def insertAfter(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    newNode.prev = temp
    if newNode.next is not None:
      newNode.next.prev = newNode
    print("Inserted {} after node {}".format(value, searchItem))
  def insertBefore(self, searchItem, value):
    newNode = Node(data=value)
    temp = self.head
    while temp.next is not None and temp.next.data != searchItem:
      temp = temp.next
    newNode.next = temp.next
    temp.next = newNode
    newNode.prev = temp
    if newNode.next is not None:
      newNode.next.prev = newNode
    print("Inserted {} before node {}".format(value, searchItem))
  def searchAndDelete(self, searchItem):
    temp = self.head
    while temp is not None and temp.data != searchItem:
      temp = temp.next
    if self.head is None or temp is None:
      return
    if self.head.data == temp.data:
      self.head = temp.next
    if temp.next is not None:
      temp.next.prev = temp.prev
    if temp.prev is not None:
      temp.prev.next = temp.next
    print("Deleted Node\t{}".format(searchItem))
doublyLinkedList = DoublyLinkedList()
doublyLinkedList.insertFront(5)
doublyLinkedList.insertFront(6)
doublyLinkedList.insertFront(7)
doublyLinkedList.insertEnd(9)
doublyLinkedList.insertEnd(10)
doublyLinkedList.insertAfter(5, 11)
doublyLinkedList.insertBefore(5, 20)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()
doublyLinkedList.searchAndDelete(7)
doublyLinkedList.traverseFromFront()
doublyLinkedList.traverseFromEnd()

Sortie

Added 5 at the front
Added 6 at the front
Added 7 at the front
Added 9 at the end
Added 10 at the end
Inserted 11 after node 5
Inserted 20 before node 5
Traversing from head:   7  6  20  5  11  9  10
Traversing from tail:   10  9  11  5  20  6  7
Deleted Node    7
Traversing from head:   6  20  5  11  9  10
Traversing from tail:   10  9  11  5  20  6

Complexité de la liste doublement chaînée

La complexité temporelle est généralement divisée en trois types : cas optimal, cas moyen et cas le plus défavorable.

Complexité temporelle dans le meilleur des cas pour une liste doublement chaînée :

1. L'insertion en tête ou en queue de liste a un coût O(1) car aucun parcours de la liste chaînée n'est nécessaire. Les pointeurs de tête et de queue permettent d'accéder directement aux nœuds de tête et de queue.
2. La suppression en tête ou en queue coûte O(1).
3. La recherche d'un nœud coûte O(1) lorsque le nœud cible est le nœud principal.

Complexité temporelle dans le cas moyen d'une liste doublement chaînée :

1. L'insertion à la tête ou à la queue coûte O(1).
2. La suppression en tête ou en queue coûte O(1).
3. La recherche d'un nœud coûte O(n), car la cible peut se trouver n'importe où dans la liste. Ici, n est le nombre total de nœuds.

La complexité temporelle dans le pire des cas d'une liste doublement chaînée est la même que dans le cas moyen.

Complexité de la mémoire de la liste doublement chaînée

La complexité de la mémoire est O(n), où n Il s'agit du nombre total de nœuds. Lors de l'implémentation de la liste chaînée, la mémoire doit être libérée. Autrement, les listes chaînées volumineuses entraînent des fuites de mémoire.

Applications des listes doublement chaînées

Les listes doublement chaînées sont à la base de plusieurs structures de données du monde réel, car le parcours bidirectionnel simplifie de nombreuses opérations courantes.

• Cache LRU : Les caches Least-Recently-Used utilisent une liste doublement chaînée avec une table de hachage pour le déplacement vers le devant et l'éviction O(1).
• Historique du navigateur: La navigation avant/arrière permet de parcourir la liste chaînée dans les deux sens.
• Piles d'annulation et de rétablissement : Éditeurs et environnements de développement intégrés track versions de document avec des pointeurs précédent et suivant.
• Déque : DoubleLes files d'attente à -extrémités empilent et extraient des deux extrémités en temps O(1).
• Listes de lecture musicales : Précédent et suivant tracLes boutons k utilisent des pointeurs de retour et d'avance.

FAQ