Liste doublement chaînée : C++, Python (Exemple de code)
Sarah Chen
Qu'est-ce qu'une liste doublement chaînée ?
Dans une liste doublement chaînée, chaque nœud possède des liens vers le nœud précédent et suivant. Chaque nœud se compose de trois éléments : l'un contient les données et deux autres sont les pointeurs du nœud suivant et précédent. Ces deux pointeurs nous aident à avancer ou à reculer à partir d'un nœud particulier.
Voici la structure de base de la liste doublement chaînée.
Chaque liste chaînée a un nœud de tête et de queue. Le nœud principal n’a pas de nœud « précédent » (pointeur précédent) et le nœud de queue n’a pas de nœud « suivant ».
Voici quelques termes importants pour 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 est utilisé pour stocker des données dans un nœud. Les « données » peuvent contenir d’autres Structures de données à l'intérieur. Par exemple, une chaîne, un dictionnaire, un ensemble, un hashmap, etc. peuvent être stockés dans les « Données ».
Voici la structure de base d'un nœud unique dans la liste doublement chaînée :
Operation de liste doublement chaînée
Les opérations d'une liste doublement chaînée incluent l'ajout et la suppression de nœuds, l'insertion et la suppression de nœuds et le parcours de la liste chaînée de haut en bas.
Voici la liste des opérations que nous pouvons implémenter à l'aide de la liste doublement chaînée :
- Insertion devant
- Insertion dans la queue ou le 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
Nous verrons l'implémentation et le pseudocode de toutes les opérations ci-dessus.
Insertion devant une liste doublement chaînée
L'insertion devant signifie que nous devons créer un nœud dans la liste chaînée et le placer au début de la liste chaînée.
Par exemple, il y a un nœud donné « 15 ». Nous devons l'ajouter au nœud principal.
Voici deux conditions importantes lors de cette opération :
- Le nouveau nœud sera le nœud principal s'il n'y a pas de nœud dans la liste doublement liée.
- S'il existe déjà un nœud principal, le nœud principal précédent sera 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 à la fin de la liste doublement chaînée
« Insertion à la fin » signifie que nous allons créer un nœud dans la liste chaînée et le placer à la fin.
Pour réaliser cela, nous pouvons utiliser deux méthodes :
- Méthode 1: Commencez à parcourir à partir de la tête de la liste doublement chaînée jusqu'à ce que le « suivant » devienne nul. Liez ensuite le nouveau nœud au « suivant ».
- Méthode 2: Prenez le dernier nœud de la liste doublement liée. Ensuite, le nœud « suivant » du dernier nœud sera lié au nouveau nœud. Désormais, le nouveau nœud sera le nœud de queue.
Voici le pseudo-code à insérer au niveau du nœud de queue :
function insertAtTail(ListHead, value): newNode = Node() newNode.value = value newNode.next = NULL while ListHead.next is not NULL: then ListHead = ListHead.next newNode.prev = ListHead ListHead.next = newNode return ListHead
Insertion après un nœud
Disons que nous avons une liste doublement chaînée existante comme la suivante :
Nous voulons insérer un nœud donné qui sera lié après le nœud qui a la valeur « 12 ».
Voici les étapes à suivre :
Étape 1) Traversez de la tête au dernier nœud. Vérifiez quel nœud a la valeur « 12 ».
Étape 2) Créez un nouveau nœud et attribuez-le comme prochain pointeur du nœud « 12 ». Le nœud « suivant » 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 then List = ListHead.next List = List.next NewNode.next = List.next NewNode.prev = List List.next = NewNode
Insertion avant un nœud
Cette opération s’apparente davantage à « l’insertion après un nœud ». Nous devons rechercher la valeur d'un nœud spécifique pour effectuer cela. Ensuite, nous allons créer un nouveau nœud et l'insérer avant le nœud recherché.
Disons que nous voulons insérer un nœud donné « 15 » avant le nœud « 12 ». Alors voici les étapes pour le faire :
É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 » ou non.
Étape 3) Insérez le nouveau nœud comme nœud « suivant » du nœud actuel.
Voici le pseudo-code pour insérer un nœud avant un 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 then List = ListHead.next NewNode.next = List.next NewNode.prev = List List.next = NewNode
Supprimer l'en-tête de la liste doublement chaînée
Le nœud principal dans la liste doublement chaînée qui n’a aucun nœud précédent. Ainsi, le pointeur suivant sera le nouveau nœud principal si nous voulons supprimer le nœud principal. Nous devons également libérer la mémoire occupée par un nœud lors de la suppression d'un nœud.
Voici les étapes à suivre pour supprimer le nœud principal :
Étape 1) Attribuez une variable au nœud principal actuel.
Étape 2) Visitez le nœud « suivant » du nœud principal actuel et définissez le nœud « précédent » (pointeur précédent) comme « NULL ». Cela signifie que nous déconnectons 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
Il est nécessaire de supprimer la mémoire allouée après avoir effectué tout type d'opération de suppression. Sinon, pendant toute la durée d'exécution du programme, la mémoire du bloc supprimé restera occupée. Aucune autre application ne peut utiliser ce segment de mémoire.
Supprimez la queue de la liste doublement chaînée.
Cette opération est un peu la même que la suppression de la tête. Ici, au lieu de la tête, nous devons supprimer la queue. Pour identifier un nœud comme nœud de queue, nous devons vérifier si le pointeur suivant ou le nœud suivant est nul ou non. Après avoir supprimé la queue, nous devons libérer la mémoire.
Cette opération est également connue sous le nom de « suppression par l’arrière ».
Voici les étapes pour ce faire :
Étape 1) Traversez jusqu'au nœud de queue de la liste doublement chaînée.
Étape 2) Attribuez une variable ou un pointeur au nœud de queue.
Étape 3) Définissez le nœud « suivant » comme NULL et libérez la mémoire du nœud de queue.
Voici le pseudo-code pour supprimer le nœud de queue :
function DeleteTail( ListHead ): head = ListHead while ListHead.next is not NULL: ListHead = ListHead.next Tail = ListHead.next ListHead.next = NULL free memory( Tail ) return head
Rechercher et supprimer un nœud de la liste doublement liée
Cette opération nous permet de rechercher des données de nœud spécifiques et de supprimer ce nœud. Nous devons effectuer une recherche linéaire car la liste chaînée est une structure de données linéaire. Après la suppression, nous devons également libérer la mémoire.
Voici les étapes pour rechercher et supprimer un nœud dans la liste doublement chaînée :
Étape 1) Parcourez la liste chaînée depuis la tête jusqu'à ce que la valeur du nœud soit égale à l'élément de recherche.
Étape 2) Attribuez une variable « deleteNode » au nœud correspondant.
Étape 3) Attribuez le nœud précédent du « deleteNode » au nœud suivant.
Étape 4) Libérez la mémoire du « deleteNode »
Voici le pseudocode pour rechercher et supprimer un nœud d'une liste chaînée :
function SearchAndDelete(ListHead, searchItem): head = ListHead while ListHead.next.value not equals searchItem: head = head.next deleteNode = head.next head.next = head.next.next head.next.prev = head deleteNode.next, deleteNode.next = NULL free memory(deleteNode) return ListHead
Parcourez une liste doublement chaînée depuis l'avant
Traverser à partir du nœud principal et parcourir le nœud suivant jusqu'à ce que nous trouvions « NULL ». En parcourant chaque nœud, nous pouvons imprimer la valeur du nœud. Voici les étapes à suivre pour traverser depuis l’avant (vers l’avant) :
Étape 1) Attribuez un pointeur ou une variable au nœud principal actuel.
Étape 2) Itérer jusqu'au nœud suivant de la tête jusqu'à obtenir « NULL »
Étape 3) Imprimez 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 depuis le devant :
function traverseFromFront(ListHead): head = ListHead while head not equals to NULL: print head.data head = head.next return ListHead
Ici, le retour n'est pas obligatoire. Mais c'est une bonne pratique de renvoyer le nœud principal après les opérations.
Parcourez une liste doublement chaînée depuis l’arrière
Cette opération est l'inverse de la traversée par l'avant. L'approche est la même avec une petite différence. Nous devons traverser jusqu'au nœud final, puis traverser du nœud final au nœud avant.
Voici les étapes pour parcourir une liste doublement chaînée depuis l’arrière :
Étape 1) Traversez jusqu’à atteindre le nœud de queue.
Étape 2) À partir du nœud de queue, nous traverserons jusqu'à ce que nous obtenions le nœud précédent comme « NULL ». Le « prev » (pointeur précédent) sera nul pour le nœud principal
Étape 3) A chaque itération, nous imprimerons les données du nœud.
Voici le pseudo-code pour traverser depuis l'arrière :
function traverseFromBack(ListHead): head = ListHead while head not equals NULL: head = head.next tail = head while tail not equal to NULL: print tail.value tail = tail.prev return ListHead
Différence entre les listes chaînées simple et double
La principale différence entre la liste Singly et la liste Doublement liée est le nombre de liens.
Voici la différence entre les nœuds d'une liste à lien unique et la structure des nœuds d'une liste à double lien :
| Champ | Liste liée individuellement | Liste doublement liée |
|---|---|---|
| Structure | Liste liée individuellement a un champ de données et un lien vers le nœud suivant. | La liste doublement liée comporte un champ de données et deux liens. Un pour le nœud précédent et un autre pour le nœud suivant. |
| Traversée | Il ne peut se déplacer que de la tête à la queue. | Il peut avancer et reculer. |
| Mémoire | Occupe moins de mémoire. | Elle occupe plus de mémoire qu’une liste à chaînage unique. |
| Accessibilité | Les listes à lien unique sont moins efficaces car elles n'utilisent qu'un seul lien vers le nœud suivant. Il n'y a aucun lien pour le nœud précédent. | Les listes doublement liées sont plus efficaces que les listes simplement liées. |
Liste doublement liée dans C++
#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);
}
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 = new 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 = new node();
head = listHead;
cout<<"Traversal from head:\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 = new node();
head = (*listHead);
while(head->next!=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;
return;
}
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 Aded 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 head: 10 9 11 5 20 6 7 Deleted Node 7 Traversal from head: 6 20 5 11 9 10 Traversal from head: 10 9 11 5 20 6
Liste doublement liée dans Python
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.insertFront(val)
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:
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 is not 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 is not 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.next is not None and temp.data is not searchItem:
temp = temp.next
if self.head is None or temp is None:
return
if self.head.data is 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))
return
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
Généralement, la complexité temporelle est divisée en trois types.
Ils sont les suivants:
- Meilleur cas
- Cas moyen
- Pire cas
Complexité temporelle dans le meilleur des cas pour une liste doublement chaînée :
- L'insertion en tête ou en queue coûtera O(1). Parce que nous n'avons pas besoin de parcourir l'intérieur de la liste chaînée. Le pointeur de tête et de queue peut nous donner accès aux nœuds de tête et de queue avec une complexité temporelle O(1).
- La suppression en tête ou en queue coûtera O (1).
- La recherche d'un nœud aura la complexité temporelle de O(1). Parce que le nœud cible peut être le nœud principal.
Complexité temporelle dans le cas moyen d'une liste doublement chaînée :
- L'insertion en tête ou en queue aura la complexité temporelle du coût O(1).
- La suppression en tête ou en queue aura la complexité temporelle du coût O(1).
- La recherche d'un nœud aura la complexité temporelle de O(n). Parce que l’élément de recherche peut résider n’importe où entre la liste chaînée. Ici, « n » est le nœud total présent dans la liste chaînée.
La complexité temporelle dans le pire des cas de la liste doublement chaînée sera 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 » est le nombre total de nœuds. Lors de l'implémentation de la liste chaînée, nous devons libérer la mémoire que nous avons utilisée. Sinon, pour une liste chaînée plus grande, cela entraînera des fuites de mémoire.
Résumé
- Une liste chaînée est une sorte de structure de données linéaire, une collection de données représentées de manière linéaire.
- Une liste doublement chaînée est un type de liste chaînée dans laquelle un nœud a des liens avec le nœud précédent et suivant.
- La liste doublement chaînée contient toutes les opérations telles que l'ajout d'un nœud, la suppression d'un nœud, l'insertion d'un nœud après ou avant un autre nœud et la traversée de la liste chaînée de la tête à la queue.
- La liste doublement liée comporte un champ de données et deux liens. Un pour le nœud précédent et un autre pour le nœud suivant.
- Complexité de la liste doublement chaînée Meilleur cas, cas moyen
- Et dans le pire des cas.
