0Pricing
C Academy · Leçon

Listes doublement chaînées

Liens dans les deux sens

Listes doublement chaînées est une leçon C Academy gratuite sur CoddyKit. Ceci est la leçon 4 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage C Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours C Academy comprend 4 leçons au total.

Des liens dans les deux sens

Une liste doublement chaînée donne à chaque nœud deux pointeurs : l’un vers le nœud next et l’autre vers le nœud prev (précédent).

Vous pouvez ainsi parcourir la liste dans les deux directions et simplifier les suppressions.

#include <stdio.h>

struct Node {
    int value;
    struct Node *prev;
    struct Node *next;
};

int main(void) {
    printf("Each node links forward and backward\n");
    return 0;
}

Définir le nœud

La structure ajoute un pointeur prev à côté de next. Les deux valent NULL aux extrémités de la liste.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };

int main(void) {
    struct Node *n = malloc(sizeof(struct Node));
    n->value = 1; n->prev = NULL; n->next = NULL;
    printf("%d\n", n->value);
    free(n);
    return 0;
}

Un outil de création

Comme précédemment, une fonction auxiliaire centralise l’allocation. Elle définit prev et next sur NULL.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };

struct Node *make(int v) {
    struct Node *n = malloc(sizeof(struct Node));
    n->value = v; n->prev = NULL; n->next = NULL;
    return n;
}

int main(void) {
    struct Node *n = make(42);
    printf("%d\n", n->value);
    free(n);
    return 0;
}

Relier les nœuds dans les deux sens

Lorsque vous reliez deux nœuds, vous devez mettre à jour les deux directions : le next du premier nœud et le prev du second.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *a = make(1), *b = make(2);
    a->next = b;
    b->prev = a;
    printf("forward %d, back %d\n", a->next->value, b->prev->value);
    free(a); free(b);
    return 0;
}

Insérer au début

Pour insérer au début : le next du nouveau nœud désigne l’ancienne tête, le prev de l’ancienne tête désigne le nouveau nœud, puis la tête devient le nouveau nœud.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

void push(struct Node **head, int v) {
    struct Node *n = make(v);
    n->next = *head;
    if (*head) (*head)->prev = n;
    *head = n;
}

int main(void) {
    struct Node *head = NULL;
    push(&head, 2); push(&head, 1);
    printf("%d %d\n", head->value, head->next->value);
    return 0;
}

Parcours vers l’avant

Le parcours vers l’avant est identique à celui d’une liste simplement chaînée : suivez next jusqu’à NULL.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *a = make(1), *b = make(2);
    a->next = b; b->prev = a;
    for (struct Node *p = a; p; p = p->next) printf("%d ", p->value);
    printf("\n");
    free(a); free(b);
    return 0;
}

Parcours vers l’arrière

Le principal avantage est que, depuis n’importe quel nœud, vous pouvez parcourir la liste vers l’arrière en suivant les pointeurs prev jusqu’à atteindre la tête.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *a = make(1), *b = make(2), *c = make(3);
    a->next = b; b->prev = a; b->next = c; c->prev = b;
    for (struct Node *p = c; p; p = p->prev) printf("%d ", p->value);
    printf("\n");
    free(a); free(b); free(c);
    return 0;
}

La suppression est plus simple

Comme chaque nœud connaît son prédécesseur, vous pouvez le supprimer sans rechercher le nœud précédent.

Reliez simplement node->prev à node->next dans les deux sens.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

void del(struct Node **head, struct Node *n) {
    if (n->prev) n->prev->next = n->next; else *head = n->next;
    if (n->next) n->next->prev = n->prev;
    free(n);
}

int main(void) {
    struct Node *a = make(1), *b = make(2), *c = make(3);
    a->next=b; b->prev=a; b->next=c; c->prev=b;
    struct Node *head = a;
    del(&head, b);
    printf("%d %d\n", head->value, head->next->value);
    return 0;
}

Mettre à jour les deux voisins

Lors de la suppression d’un nœud, corrigez toujours le next du nœud précédent et le prev du nœud suivant.

Vérifiez la présence de NULL à chaque extrémité afin de ne pas déréférencer un voisin absent.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *a = make(1), *b = make(2);
    a->next = b; b->prev = a;
    a->next = NULL;
    free(b);
    printf("now only %d remains\n", a->value);
    free(a);
    return 0;
}

Conserver un pointeur de queue

De nombreuses listes doublement chaînées stockent également un pointeur de queue vers le dernier nœud, ce qui permet des ajouts en O(1) et un parcours vers l’arrière depuis la fin.

#include <stdio.h>
#include <stdlib.h>

struct Node { int value; struct Node *prev; struct Node *next; };
struct Node *make(int v){struct Node*n=malloc(sizeof*n);n->value=v;n->prev=NULL;n->next=NULL;return n;}

int main(void) {
    struct Node *head = make(1), *tail = head;
    struct Node *n = make(2);
    tail->next = n; n->prev = tail; tail = n;
    printf("tail = %d\n", tail->value);
    free(head); free(n);
    return 0;
}

Compromis

Les listes doublement chaînées consomment davantage de mémoire (un pointeur supplémentaire par nœud) et nécessitent la mise à jour de deux liens à chaque modification.

En contrepartie, elles offrent un parcours bidirectionnel et la suppression en O(1) d’un nœud connu. Faites votre choix selon vos besoins.

#include <stdio.h>

int main(void) {
    printf("Singly: less memory, one-way\n");
    printf("Doubly: more memory, two-way + easy delete\n");
    return 0;
}

Vérification rapide

Vérifiez votre compréhension des listes doublement chaînées.

Récapitulatif

Vous avez appris le fonctionnement des listes doublement chaînées :

  • Chaque nœud possède les pointeurs prev et next.
  • La liaison nécessite de mettre à jour les deux directions.
  • Vous pouvez parcourir la liste vers l’avant et vers l’arrière, et supprimer un nœud connu en O(1).
  • Le coût est une mémoire supplémentaire et davantage de mises à jour de pointeurs ; un pointeur de queue permet des ajouts en O(1).

Questions Fréquemment Posées

La leçon « Listes doublement chaînées » est-elle gratuite ?

Oui — le texte complet de « Listes doublement chaînées » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours C Academy, passe à CoddyKit PRO. Le cours C Academy comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Listes doublement chaînées » ?

Liens dans les deux sens Tu pratiques C Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer C Academy ?

Aucune expérience préalable n'est requise. C Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 4 sur 4.

Combien de temps prend la leçon « Listes doublement chaînées » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon C Academy ?

Oui. Chaque leçon C Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

  1. Listes simplement chaînées
  2. Insertion et suppression
  3. Parcours et recherche
  4. Listes doublement chaînées
← Retour à C Academy