Structure de données - Liste chaînée

Une liste chaînée (Linked List) est une structure de données linéaire composée de plusieurs nœuds connectés séquentiellement par des pointeurs.

Contrairement aux tableaux, les éléments d'une liste chaînée n'ont pas besoin d'être stockés de manière contiguë en mémoire.


Concepts de base des listes chaînées et de la structure des nœuds

Chaque nœud d'une liste chaînée contient deux parties :Champ de données (data)Stocke les données réelles ;Champ pointeur (next)Pointe vers le nœud suivant.

链表节点结构与内存中的链式关系

La figure ci-dessus montre l'apparence réelle d'une liste chaînée en mémoire. Chaque nœud estmallocalloué indépendamment sur le tas, ils peuvent donc être non contigus en mémoire. Les nœuds sont connectés vianextpointeurs, et le pointeur next du dernier nœud pointe vers NULL pour indiquer la fin de la liste chaînée.

En C, les nœuds de liste chaînée sont définis à l'aide d'une structure :

Exemple

#include <stdio.h>
#include <stdlib.h> /* malloc, free */

/* Structure de nœud de liste chaînée
data : champ de données, stocke des données entières
next : champ pointeur, pointe vers le nœud suivant du même type */

struct Node {
    int data;
    struct Node* next;
};

/* Créer un nouveau nœud
Paramètre value : la valeur de données du nœud
Valeur de retour : pointeur vers le nouveau nœud, renvoie NULL si l'allocation échoue */

struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    if (newNode == NULL) {
        printf("Échec de l'allocation mémoire\n");
        return NULL;
    }
    newNode->data = value;   /* Définir les données */
    newNode->next = NULL;    /* Initialiser le champ next du nouveau nœud à NULL */
    return newNode;
}

struct Node* nextest une structure auto-référentielle, c'est-à-dire que la structure contient un pointeur vers une structure du même type. C'est la technique fondamentale pour construire toutes les structures de données chaînées (listes chaînées, arbres, graphes).


Opérations de base d'une liste simplement chaînée

Création d'une liste chaînée et parcours

Exemple

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

struct Node {
    int data;
    struct Node* next;
};

/* Parcourir et afficher tous les nœuds de la liste chaînée
Partir du nœud de tête et visiter chaque nœud en suivant les pointeurs next jusqu'à NULL */

void traverse(struct Node* head) {
    struct Node* current = head;  /* Partir de la tête */
    printf("Contenu de la liste chaînée : ");
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;  /* Passer au nœud suivant */
    }
    printf("NULL\n");
}

/* Créer une liste chaînée contenant n nœuds (1, 2, 3, ..., n) */
struct Node* createList(int n) {
    if (n <= 0) return NULL;

    struct Node* head = (struct Node*)malloc(sizeof(struct Node));
    head->data = 1;
    head->next = NULL;

    struct Node* tail = head;  /* tail pointe toujours vers le dernier nœud */
    for (int i = 2; i <= n; i++) {
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = i;
        newNode->next = NULL;
        tail->next = newNode;  /* Connecter le nouveau nœud à la fin de la liste chaînée */
        tail = newNode;           /* Mettre à jour le pointeur tail */
    }
    return head;
}

int main() {
    struct Node* head = createList(5);
    traverse(head);
    /* Sortie : Contenu de la liste chaînée : 1 -> 2 -> 3 -> 4 -> 5 -> NULL */
    return 0;
}

Opération d'insertion

链表插入与删除操作的指针调整过程

La figure ci-dessus montre le processus complet des changements de pointeurs lors de l'insertion et de la suppression dans une liste chaînée. Comprendre l'ordre des ajustements de pointeurs est crucial : si l'ordre est incorrect, cela provoquera la rupture de la liste chaînée ou entraînera des fuites de mémoire.

Exemple

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

struct Node {
    int data;
    struct Node* next;
};

/* Insérer un nouveau nœud en tête de la liste chaînée (insertion en tête)
Complexité temporelle : O(1)
Valeur de retour : pointeur vers le nouveau nœud de tête */

struct Node* insertAtHead(struct Node* head, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = head;  /* Le nouveau nœud pointe vers le nœud de tête d'origine */
    return newNode;         /* Le nouveau nœud devient le nouveau nœud de tête */
}

/* Insérer un nouveau nœud à la queue de la liste chaînée (insertion en queue)
Complexité temporelle : O(n), nécessite un parcours jusqu'à la queue */

struct Node* insertAtTail(struct Node* head, int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;

    if (head == NULL) {
        return newNode;  /* Liste chaînée vide, le nouveau nœud devient le nœud de tête */
    }

    struct Node* current = head;
    while (current->next != NULL) {
        current = current->next;  /* Parcourir jusqu'au dernier nœud */
    }
    current->next = newNode;  /* Le nœud de queue pointe vers le nouveau nœud */
    return head;
}

/* Insérer un nouveau nœud après la position spécifiée
Complexité temporelle : O(n), nécessite d'abord de trouver prevNode */

void insertAfter(struct Node* prevNode, int value) {
    if (prevNode == NULL) {
        printf("Le nœud prédécesseur ne peut pas être nul\n");
        return;
    }
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    /* Important : faire d'abord pointer le nouveau nœud vers son successeur, puis faire pointer le prédécesseur vers le nouveau nœud */
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

void printList(struct Node* head) {
    struct Node* cur = head;
    while (cur != NULL) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

int main() {
    struct Node* head = NULL;

    head = insertAtHead(head, 30);  /* Liste chaînée : 30 */
    head = insertAtHead(head, 20);  /* Liste chaînée : 20 -> 30 */
    head = insertAtHead(head, 10);  /* Liste chaînée : 10 -> 20 -> 30 */

    printf("Après insertion en tête : "); printList(head);  /* Sortie : 10 20 30 */

    head = insertAtTail(head, 40);  /* Liste chaînée : 10 -> 20 -> 30 -> 40 */
    printf("Après insertion en queue : "); printList(head);  /* Sortie : 10 20 30 40 */

    insertAfter(head->next, 25);    /* Insérer 25 après 20 */
    printf("Après insertion au milieu : "); printList(head);
    /* Sortie : 10 20 25 30 40 */
    return 0;
}

Opération de suppression

Exemple

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

struct Node {
    int data;
    struct Node* next;
};

/* Supprimer le nœud de tête de la liste chaînée
Complexité temporelle : O(1)
Valeur de retour : pointeur vers le nouveau nœud de tête */

struct Node* deleteHead(struct Node* head) {
    if (head == NULL) return NULL;

    struct Node* temp = head;   /* Enregistrer l'ancien nœud de tête */
    head = head->next;          /* Déplacer le pointeur de tête vers le nœud suivant */
    free(temp);                 /* Libérer la mémoire de l'ancien nœud de tête */
    return head;
}

/* Supprimer le premier nœud de la liste chaînée avec la valeur target
Complexité temporelle : O(n), nécessite un parcours pour trouver le nœud cible */

struct Node* deleteByValue(struct Node* head, int target) {
    if (head == NULL) return NULL;

    /* Cas particulier : la valeur cible se trouve au nœud de tête */
    if (head->data == target) {
        struct Node* temp = head;
        head = head->next;
        free(temp);
        return head;
    }

    /* Parcourir pour trouver le nœud prédécesseur du nœud cible */
    struct Node* current = head;
    while (current->next != NULL && current->next->data != target) {
        current = current->next;
    }

    /* Trouver le nœud cible et le supprimer */
    if (current->next != NULL) {
        struct Node* temp = current->next;
        current->next = current->next->next;  /* Sauter le nœud cible */
        free(temp);  /* Libérer la mémoire du nœud cible */
    }
    return head;
}

void printList(struct Node* head) {
    struct Node* cur = head;
    while (cur != NULL) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

int main() {
    /* Construire la liste chaînée : 10 -> 20 -> 30 -> 40 */
    struct Node* head = NULL;
    int vals[] = {10, 20, 30, 40};
    for (int i = 3; i >= 0; i--) {
        struct Node* n = (struct Node*)malloc(sizeof(struct Node));
        n->data = vals[i];
        n->next = head;
        head = n;
    }
    printf("Liste chaînée originale : "); printList(head);  /* Sortie : 10 20 30 40 */

    head = deleteHead(head);
    printf("Après suppression de la tête : "); printList(head);  /* Sortie : 20 30 40 */

    head = deleteByValue(head, 30);
    printf("Après suppression de 30 : "); printList(head);  /* Sortie : 20 40 */
    return 0;
}

Dans l'opération de suppression d'une liste chaînée,free()est crucial. Si vous ne faites qu'ajuster les pointeurs sans libérer la mémoire du nœud supprimé, cela provoquera une fuite de mémoire. En langage C, chaquemallocdoit avoir un correspondantfree。


Comparaison entre liste chaînée et tableau

数组与链表全方位对比

Critère de comparaisonTableauListe chaînée
Disposition de la mémoireStockage contiguStockage dispersé, relié par des pointeurs
Accès aléatoireO(1)O(n)
Insertion/suppression en têteO(n)O(1)
Insertion/suppression en queueO(1)O(1) (avec pointeur de queue) / O(n) (sans pointeur de queue)
Insertion/suppression au milieuO(n)O(1)(position connue)
Surcoût d'espaceDonnées uniquementDonnées + pointeur (8 octets supplémentaires par nœud (64 bits))
Affinité avec le cacheÉlevée(localité spatiale)Faible(nœuds dispersés)
CapacitéFixe (tableau statique)Croissance dynamique

Comprendre ce compromis est l'une des compétences essentielles dans la sélection des structures de données.

Si la taille des données est connue avant l'exécution et ne change pas fréquemment, et qu'un accès aléatoire fréquent est nécessaire, un tableau est un meilleur choix.

Si la taille des données change fréquemment et que son échelle est incertaine, les structures dynamiques telles que les listes chaînées sont plus flexibles.

Autres extensions