Structure de données - Liste doublement chaînée
Une liste doublement chaînée (Doubly Linked List) est une extension d'une liste simplement chaînée. En plus de pointer vers le nœud suivant, chaque nœud stocke également un pointeur vers le nœud précédent, formant ainsi une structure en chaîne accessible dans les deux sens.
Structure et caractéristiques de la liste doublement chaînée
struct Node { int data; struct Node* prev; struct Node* next; };
prev pointe vers le nœud précédent | data stocke les données | next pointe vers le nœud suivant
Avantages principaux : vous pouvez supprimer directement n'importe quel nœud (pas besoin d'enregistrer le prédécesseur), et il prend en charge le parcours bidirectionnel
Comme le montre la figure ci-dessus, chaque nœud d'une liste doublement chaînée aprevetnextdeux pointeurs.
En langage C, la définition d'un nœud de liste doublement chaînée est la suivante :
Exemple
int data; /* Champ de données */
struct Node* prev; /* Pointeur vers le prédécesseur : pointe vers le nœud précédent */
struct Node* next; /* Pointeur vers le successeur : pointe vers le nœud suivant */
};
Comparé à une liste simplement chaînée, le plus grand avantage d'une liste doublement chaînée est que vous pouvez accéder directement à son prédécesseur et à son successeur depuis n'importe quel nœud, ce qui signifie que l'opération de suppression n'a plus besoin d'enregistrer une référence supplémentaire au nœud prédécesseur.
Dans une liste simplement chaînée, pour supprimer un nœud spécifié, vous devez connaître son nœud prédécesseur pour effectuer l'ajustement des pointeurs. Dans une liste doublement chaînée, comme chaque nœud stocke lui-même un pointeur prev, l'opération de suppression peut être effectuée directement.
Opérations de base
Opération d'insertion
L'insertion dans une liste doublement chaînée nécessite d'ajuster les pointeurs prev/next du nouveau nœud ainsi que les pointeurs de ses nœuds prédécesseur et successeur, ce qui implique un total de quatre ajustements de pointeurs.
Exemple
#include <stdlib.h>
struct Node {
int data;
struct Node* prev;
struct Node* next;
};
/* Créer un nouveau nœud */
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
/* Insérer un nœud en tête Étapes : le next du nouveau nœud pointe vers le nœud de tête d'origine, et le prev du nœud de tête d'origine pointe vers le nouveau nœud */
/* Le nouveau nœud devient le nouveau nœud de tête */
struct Node* insertAtHead(struct Node* head, int value) {
struct Node* newNode = createNode(value);
if (head != NULL) {
newNode->next = head;
head->prev = newNode;
}
return newNode; /* Insérer un nouveau nœud après un nœud spécifié Vous devez manipuler 4 pointeurs : 1-2 : le prev et le next du nouveau nœud 3 : le prev du nœud successeur (s'il existe) 4 : le next du nœud prédécesseur */
}
/* Le next du nouveau nœud pointe vers le successeur d'origine */
/* Le prev du nouveau nœud pointe vers le prédécesseur */
/* Le prev du successeur d'origine pointe vers le nouveau nœud */
/* Le next du prédécesseur pointe vers le nouveau nœud */
Opération de suppression
void insertAfter(struct Node* prevNode, int value) {
if (prevNode == NULL) return;
struct Node* newNode = createNode(value);
newNode->next = prevNode->next; Exemple
newNode->prev = prevNode; /* Supprimer un nœud spécifié (pas besoin de connaître le nœud prédécesseur ; c'est le plus grand avantage d'une liste doublement chaînée) Étapes : relier les nœuds précédent et suivant entre eux, sauter le nœud actuel, puis libérer le nœud actuel */
if (prevNode->next != NULL) {
prevNode->next->prev = newNode; /* Si le nœud de tête est supprimé, mettre à jour le pointeur de tête */
}
prevNode->next = newNode; /* Faire pointer le next du nœud prédécesseur vers le nœud successeur */
}
Opération de suppression
Exemple
Une liste doublement chaînée prend en charge deux méthodes de parcours : en avant et en arrière.
void deleteNode(struct Node** headRef, struct Node* del) {
if (*headRef == NULL || del == NULL) return;
Exemple
if (*headRef == del) {
*headRef = del->next;
}
/* Parcours avant : partir de la tête, avancer dans la direction next */
if (del->prev != NULL) {
del->prev->next = del->next;
}
"Parcours avant : "
if (del->next != NULL) {
del->next->prev = del->prev;
}
free(del); /* Parcours inverse : partir de la queue, avancer dans la direction prev Vous devez d'abord trouver le nœud de queue */
}
Opération de parcours (bidirectionnelle)
/* De la queue, revenir à la tête dans la direction prev */
Exemple
/* Parcours en avant : commencer depuis head, en suivant la direction next */
void traverseForward(struct Node* head) {
printf(Parcours en avant :);
struct Node* cur = head;
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}
/* Parcours inverse : depuis la queue, en suivant la direction prev
Il faut d'abord trouver le nœud de queue */
void traverseBackward(struct Node* head) {
if (head == NULL) return;
/* Se déplacer d'abord vers le dernier nœud (c'est-à-dire la queue) */
struct Node* cur = head;
while (cur->next != NULL) {
cur = cur->next;
}
/* Revenir de la queue vers la tête en suivant la direction prev */
printf("Parcours inverse : ");
while (cur != NULL) {
printf("%d ", cur->data);
cur = cur->prev;
}
printf("\n");
}
int main() {
struct Node* head = NULL;
/* Construire une liste chaînée : 10 <-> 20 <-> 30 */
head = insertAtHead(head, 30);
head = insertAtHead(head, 20);
head = insertAtHead(head, 10);
traverseForward(head); /* Sortie : parcours en avant : 10 20 30 */
traverseBackward(head); /* Sortie : parcours inverse : 30 20 10 */
return 0;
}
Liste doublement chaînée vs Liste simplement chaînée
| Critère de comparaison | Liste simplement chaînée | Liste doublement chaînée |
|---|---|---|
| Structure du nœud | data + next | data + prev + next |
| Mémoire supplémentaire par nœud | 8 octets (système 64 bits) | 16 octets (système 64 bits) |
| Parcours en avant | Pris en charge | Pris en charge |
| Parcours en arrière | Non pris en charge | Pris en charge |
| Supprimer le nœud | Il faut connaître le nœud prédécesseur | Aucun prédécesseur nécessaire, suppression directe possible |
| Opération d'insertion | Ajuster 1~2 pointeurs | Ajuster 4 pointeurs |