Les tableaux dynamiques (listes séquentielles) sont des structures de données fondamentales, mais ils présentent certaines limites :
- L'insertion ou la suppression en tête ou au milieu nécessite un décalage des éléments, ce qui donne une complexité temporelle de O(N).
- Le redimensionnement implique l'allocation d'un nouvel espace, la copie des données existantes et la libération de l'ancienne mémoire, ce qui est coûteux en performances.
- Le redimensionnement suit généralement une croissance géométrique (par exemple, un doublement), ce qui peut entraîner un gaspillage d'espace mémoire important si la capacité allouée n'est pas entièrement utilisée.
Pour pallier ces inconvénients, les listes chaînées offrent une alternative où les insertions et suppressions en tête s'effectuent en temps constant O(1) sans nécessiter de réallocation globale de la mémoire.
- Principes des listes chaînées
1.1 Concept et strcuture
Une liste chaînée est une structure de stockage non contiguë en mémoire physique. L'ordre logique des éléments est maintenu par des pointeurs reliant les différents blocs de mémoire. On peut comparer cette structure à un train : chaque wagon est indépendant et peut être attaché ou détaché sans affecter les autres, tant que les liens sont correctement mis à jour.
1.2 Le nœud
Contrairement aux tableaux, chaque élément d'une liste chaînée est alloué dynamiquement. Cet élément est appelé "nœud". Un nœud standard se compose de deux champs : un champ de données pour stocker l'information utile, et un champ pointeur qui mémorise l'adresse du nœud suivant. Le pointeur principal (souvent appelé "tête") référence le premier nœud de la liste.
1.3 Caractéristiques
- La structure est logiquement séquentielle, mais physiquement dispersée.
- Les nœuds sont alloués dynamiquement sur le tas (heap).
- L'allocateur de mémoire ne garantit pas que les nœuds successifs seront adjacents en mémoire.
- Implémentation d'une liste chaînée simple
2.1 Définition de la structure
Nous définissons un type personnalisé pour les données et une structure représentant un nœud de la liste.
typedef int ElementType;
typedef struct LinkedListNode {
ElementType value;
struct LinkedListNode* next;
} Node;
2.2 Initialisation
Contrairement aux tableaux dynamiques qui nécessitent une initialisation de leur capacité et de leurs compteurs, une liste chaînée vide est simplement représentée par un pointeur de tête initialisé à NULL. Aucune fonction d'initialisation complexe n'est requise.
2.3 Création d'un nœud
Avant d'effectuer des insertions, il est nécessaire d'allouer de la mémoire pour chaque nouveau nœud. Cette opération est centralisée dans une fonction utilitaire.
#include <stdlib.h>
#include <stdio.h>
Node* create_node(ElementType val) {
Node* new_node = (Node*)malloc(sizeof(Node));
if (new_node == NULL) {
perror("Échec de l'allocation mémoire");
exit(EXIT_FAILURE);
}
new_node->value = val;
new_node->next = NULL;
return new_node;
}
2.4 Affichage de la liste
Pour vérifier le contenu, nous parcourons la liste depuis la tête jusqu'à rencontrer un pointeur nul.
void print_list(const Node* head) {
const Node* current = head;
while (current != NULL) {
printf("%d -> ", current->value);
current = current->next;
}
printf("NULL\n");
}
2.5 Insertion en fin de liste (Tail Append)
L'ajout en fin de liste nécessite de parcourir la structure jusqu'au dernier nœud pour y attacher le nouveau. L'utilisation d'un pointeur de pointeur (pointeur sur le pointeur de tête) est obligatoire pour gérer le cas où la liste est initialement vide.
#include <assert.h>
void list_append(Node** head_ref, ElementType val) {
assert(head_ref != NULL);
Node* new_node = create_node(val);
if (*head_ref == NULL) {
*head_ref = new_node;
return;
}
Node* tail = *head_ref;
while (tail->next != NULL) {
tail = tail->next;
}
tail->next = new_node;
}
2.6 Insertion en tête de liste (Head Prepend)
L'insertion au début est une opération en temps constant O(1). Le nouveau nœud pointe vers l'ancienne tête, puis devient la nouvelle tête.
void list_prepend(Node** head_ref, ElementType val) {
assert(head_ref != NULL);
Node* new_node = create_node(val);
new_node->next = *head_ref;
*head_ref = new_node;
}
2.7 Suppression en fin de liste
Retirer le dernier élément implique de trouver l'avant-dernier nœud pour mettre son pointeur next à NULL, puis de libérer la mémoire de l'ancien dernier nœud.
void list_pop_back(Node** head_ref) {
assert(head_ref != NULL && *head_ref != NULL);
if ((*head_ref)->next == NULL) {
free(*head_ref);
*head_ref = NULL;
return;
}
Node* current = *head_ref;
Node* previous = NULL;
while (current->next != NULL) {
previous = current;
current = current->next;
}
previous->next = NULL;
free(current);
}
2.8 Suppression en tête de liste
On sauvegarde l'adresse du deuxième nœud, on libère la tête actuelle, et on met à jour le pointeur de tête.
void list_pop_front(Node** head_ref) {
assert(head_ref != NULL && *head_ref != NULL);
Node* temp = *head_ref;
*head_ref = temp->next;
free(temp);
}
2.9 Recherche d'un élément
La recherche s'effectue par un parcours linéaire. Si la valeur est trouvée, le pointeur vers le nœud est retourné.
Node* list_search(Node* head, ElementType target) {
Node* current = head;
while (current != NULL) {
if (current->value == target) {
return current;
}
current = current->next;
}
return NULL;
}
2.10 Insertion avant une position donnée
Pour insérer avant un nœud spécifique (pos), il faut trouver son prédécesseur. Si pos est la tête, l'opération équivaut à une insertion en tête.
void list_insert_before(Node** head_ref, Node* pos, ElementType val) {
assert(head_ref != NULL && pos != NULL);
if (pos == *head_ref) {
list_prepend(head_ref, val);
return;
}
Node* previous = *head_ref;
while (previous->next != pos) {
previous = previous->next;
}
Node* new_node = create_node(val);
new_node->next = pos;
previous->next = new_node;
}
2.11 Insertion après une position donnée
Cette opération est plus directe car elle ne nécessite pas de connaître la tête de la liste. Le pointeur next du nouveau nœud est relié au successeur de pos.
void list_insert_after(Node* pos, ElementType val) {
assert(pos != NULL);
Node* new_node = create_node(val);
new_node->next = pos->next;
pos->next = new_node;
}
2.12 Suppression d'un nœud spécifique
Il faut identifier le prédécesseur du nœud à supprimer pour reconnecter la chaîne. Le cas où le nœud cible est la tête doit être traité séparément.
void list_remove_node(Node** head_ref, Node* pos) {
assert(head_ref != NULL && *head_ref != NULL && pos != NULL);
if (pos == *head_ref) {
list_pop_front(head_ref);
return;
}
Node* previous = *head_ref;
while (previous->next != pos) {
previous = previous->next;
}
previous->next = pos->next;
free(pos);
}
2.13 Suppression du nœud suivant une position
Puisque l'accès au successeur est direct via le champ next, on peut le supprimer sans parcourir la liste depuis la tête.
void list_remove_after(Node* pos) {
assert(pos != NULL && pos->next != NULL);
Node* target = pos->next;
pos->next = target->next;
free(target);
}
2.14 Destruction de la liste
Pour éviter les fuites de mémoire, tous les nœuds doivent être libérés. On parcourt la liste tout en sauvegardant le pointeur vers le nœud suivant avant de libérer le nœud courant.
void list_destroy(Node** head_ref) {
assert(head_ref != NULL);
Node* current = *head_ref;
while (current != NULL) {
Node* next_node = current->next;
free(current);
current = next_node;
}
*head_ref = NULL;
}