![CDATA[
Ce guide détaille l'implémetnation d'une liste chaînée simple en langage C, couvrent diverses opérations fondamentales.
- Structure de base
La définition d'une liste chaînée commence par la création d'une structure pour les nœuds, chaque nœud contenant des données et un pointeur vers le nœud suivant.
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef int DataType; // Définition du type de données pour les éléments de la liste.
typedef struct Node {
DataType value; // Stocke la valeur de l'élément.
struct Node *nextPtr; // Pointeur vers le nœud suivant.
} Node, *LinkedList;
</stdlib.h></string.h></stdio.h>
- Initialisation de la liste
L'initialisation crée un nœud de tête (sentinelle) qui simplifie de nombreuses opérations. La fonction retourne un pointeur vers ce nœud de tête.
// Initialise une nouvelle liste et retourne un pointeur vers le nœud de tête.
// Retourne NULL en cas d'échec d'allocation mémoire.
LinkedList initializeList() {
Node *head = (Node *)malloc(sizeof(Node));
if (head == NULL) {
return NULL; // Échec d'allocation mémoire.
}
head->nextPtr = NULL; // Le nœud de tête pointe initialement vers NULL.
return head;
}
int main() {
LinkedList myList = initializeList();
if (myList != NULL) {
printf("Liste initialisée avec succès. Adresse de la tête : %p\\n", (void*)myList);
} else {
printf("Échec de l'initialisation de la liste.\\n");
}
// ... autres opérations ...
return 0;
}
- Insertion d'un élément à une position spécifiée
Cette fonction insère un nouvel élément à la index-ième position de la liste (en considérant la position 1 comme le premier élément après la tête).
// Insère une donnée à la position 'index' dans la liste 'list'.
// Retourne 1 en cas de succès, 0 en cas d'échec.
int insertAtIndex(LinkedList list, unsigned int index, DataType *data) {
if (list == NULL || data == NULL) {
printf("Erreur : Liste ou données invalides.\\n");
return 0;
}
if (index < 1) {
printf("Erreur : L'index d'insertion (%u) doit être supérieur ou égal à 1.\\n", index);
return 0;
}
Node *current = list;
unsigned int currentIndex = 0;
// Navigue jusqu'au nœud précédent la position d'insertion.
while (current != NULL && currentIndex < index - 1) {
current = current->nextPtr;
currentIndex++;
}
if (current == NULL) {
printf("Erreur : L'index %u est hors limites.\\n", index);
return 0;
}
Node *newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL) {
return 0; // Échec d'allocation mémoire.
}
memcpy(&newNode->value, data, sizeof(DataType)); // Copie des données.
// Réajuste les pointeurs pour l'insertion.
newNode->nextPtr = current->nextPtr;
current->nextPtr = newNode;
return 1;
}
- Affichage de la liste
Parcourt la liste à partir du premier élément (après la tête) et affiche la valeur de chaque nœud.
// Affiche tous les éléments de la liste.
void printList(LinkedList list) {
if (list == NULL) {
printf("La liste n'existe pas.\\n");
return;
}
Node *current = list->nextPtr; // Commence à partir du premier élément réel.
while (current != NULL) {
printf("%-3d", current->value); // Formatage pour un affichage aligné.
current = current->nextPtr;
}
printf("\\n");
}
- Ajout d'un élément à la fin
Cette fonction ajoute un nouvel élément à la fin de la liste chaînée.
// Ajoute une donnée à la fin de la liste 'list'.
// Retourne 1 en cas de succès, 0 en cas d'échec.
int pushBack(LinkedList list, DataType *data) {
if (list == NULL || data == NULL) {
printf("Erreur : Liste ou données invalides.\\n");
return 0;
}
Node *current = list;
// Navigue jusqu'au dernier nœud.
while (current->nextPtr != NULL) {
current = current->nextPtr;
}
Node *newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL) {
return 0; // Échec d'allocation mémoire.
}
memcpy(&newNode->value, data, sizeof(DataType));
newNode->nextPtr = NULL; // Le nouveau nœud est maintenant le dernier.
current->nextPtr = newNode;
return 1;
}
- Suppression d'un nœud à une position spécifiée
Supprime le nœud situé à la index-ième position dans la liste.
// Supprime le nœud à la position 'index' dans la liste 'list'.
// Retourne 1 en cas de succès, 0 en cas d'échec.
int deleteNodeAtIndex(LinkedList list, unsigned int index) {
if (list == NULL) {
printf("Erreur : Liste invalide.\\n");
return 0;
}
if (index < 1) {
printf("Erreur : L'index de suppression (%u) doit être supérieur ou égal à 1.\\n", index);
return 0;
}
Node *current = list;
unsigned int currentIndex = 0;
// Navigue jusqu'au nœud précédant celui à supprimer.
while (current != NULL && currentIndex < index - 1) {
current = current->nextPtr;
currentIndex++;
}
if (current == NULL || current->nextPtr == NULL) {
printf("Erreur : L'index %u est hors limites ou la liste est trop courte.\\n", index);
return 0;
}
Node *nodeToDelete = current->nextPtr;
current->nextPtr = nodeToDelete->nextPtr; // Contourne le nœud à supprimer.
free(nodeToDelete); // Libère la mémoire du nœud supprimé.
return 1;
}
- Suppression du dernier élément
Supprime le dernier élément de la liste chaînée.
// Supprime le dernier nœud de la liste 'list'.
// Retourne 1 en cas de succès, 0 en cas d'échec.
int popBack(LinkedList list) {
if (list == NULL) {
printf("Erreur : Liste invalide.\\n");
return 0;
}
if (list->nextPtr == NULL) {
printf("Erreur : La liste est vide, impossible de supprimer le dernier élément.\\n");
return 0;
}
Node *current = list;
// Navigue jusqu'à l'avant-dernier nœud.
while (current->nextPtr->nextPtr != NULL) {
current = current->nextPtr;
}
free(current->nextPtr); // Libère le dernier nœud.
current->nextPtr = NULL; // Met à jour le pointeur de l'avant-dernier nœud.
return 1;
}
- Localisation d'un nœud par index
Retourne un pointeur vers le nœud situé à la index-ième position. L'index 0 correspond au nœud de tête.
// Retourne un pointeur vers le nœud à la position 'index'.
// Retourne NULL si l'index est invalide ou si la liste est NULL.
// L'index 0 représente le nœud de tête.
Node *locateNodeByIndex(LinkedList list, unsigned int index) {
if (list == NULL) {
printf("Erreur : Liste invalide.\\n");
return NULL;
}
Node *current = list;
unsigned int currentIndex = 0;
while (current != NULL && currentIndex < index) {
current = current->nextPtr;
currentIndex++;
}
if (current == NULL) {
printf("Erreur : Index %u hors limites.\\n", index);
}
return current;
}
- Recherche d'un nœud par sa valeur
Retourne un pointeur vers le premier nœud dont la valeur correspond à celle recherchée.
// Cherche un nœud contenant la valeur 'dataToFind'.
// Retourne un pointeur vers le nœud trouvé, ou NULL s'il n'est pas trouvé.
Node *locateNodeByValue(LinkedList list, DataType *dataToFind) {
if (list == NULL || dataToFind == NULL) {
return NULL;
}
Node *current = list->nextPtr; // Commence après le nœud de tête.
while (current != NULL) {
if (current->value == *dataToFind) {
return current; // Trouvé.
}
current = current->nextPtr;
}
return NULL; // Non trouvé.
}
- Calcul de la longueur de la liste
Compte le nombre d'éléments réels dans la liste (sans compter le nœud de tête).
// Calcule et retourne le nombre d'éléments dans la liste.
int getListLength(LinkedList list) {
if (list == NULL) {
return 0; // La liste n'existe pas.
}
Node *current = list->nextPtr; // Commence après le nœud de tête.
int length = 0;
while (current != NULL) {
length++;
current = current->nextPtr;
}
return length;
}
- Insertion après un nœud spécifié
Insère un nouveeau nœud après un nœud existant prevNode.
// Insère une donnée après le nœud 'prevNode'.
// Retourne 1 en cas de succès, 0 en cas d'échec.
int insertAfterNode(Node *prevNode, DataType *data) {
if (prevNode == NULL || data == NULL) {
printf("Erreur : Nœud précédent ou données invalides.\\n");
return 0;
}
Node *newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL) {
return 0; // Échec d'allocation mémoire.
}
memcpy(&newNode->value, data, sizeof(DataType));
newNode->nextPtr = prevNode->nextPtr;
prevNode->nextPtr = newNode;
return 1;
}
- Insertion avant un nœud spécifié
Insère un nouveau nœud avant un nœud existant currentNode. Cette opération est plus complexe car elle nécessite de trouver le nœud précédent.
// Insère une donnée avant le nœud 'currentNode'.
// Retourne 1 en cas de succès, 0 en cas d'échec.
int insertBeforeNode(LinkedList list, Node *currentNode, DataType *data) {
if (list == NULL || currentNode == NULL || data == NULL) {
printf("Erreur : Liste, nœud actuel ou données invalides.\\n");
return 0;
}
if (currentNode == list) { // Cas spécial : insertion avant le nœud de tête (virtuellement, c'est avant le premier élément réel).
return insertAtIndex(list, 1, data);
}
Node *prevNode = list;
while (prevNode != NULL && prevNode->nextPtr != currentNode) {
prevNode = prevNode->nextPtr;
}
if (prevNode == NULL) {
printf("Erreur : Le nœud actuel n'appartient pas à cette liste.\\n");
return 0;
}
// Utilise la logique d'insertion après le nœud précédent trouvé.
return insertAfterNode(prevNode, data);
}
- Destruction de la liste
Libère la mémoire allouée pour tous les nœuds de la liste, y compris le nœud de tête.
// Libère toute la mémoire allouée pour la liste.
void destroyList(LinkedList list) {
Node *current = list;
Node *nextNode;
while (current != NULL) {
nextNode = current->nextPtr;
free(current);
current = nextNode;
}
// Important : après avoir détruit la liste, le pointeur original devrait être mis à NULL pour éviter les pointeurs sauvages.
// Ceci est généralement géré par l'appelant en passant l'adresse du pointeur.
}
// Variante pour destruction qui met aussi à NULL le pointeur passé par adresse.
void destroyListAndNullify(LinkedList *listPtr) {
if (listPtr == NULL) return;
destroyList(*listPtr);
*listPtr = NULL;
}
- Fusion de deux listes
Fusionne deux listes chaînées triées listA et listB en une nouvelle liste triée mergedList.
// Fusionne deux listes triées 'listA' et 'listB' en une nouvelle liste triée 'mergedList'.
// Suppose que listA et listB sont triées par ordre croissant.
int mergeSortedLists(LinkedList listA, LinkedList listB, LinkedList mergedList) {
if (listA == NULL || listB == NULL || mergedList == NULL) {
printf("Erreur : Une ou plusieurs listes sont invalides pour la fusion.\\n");
return 0;
}
Node *ptrA = listA->nextPtr; // Commence après la tête de listA.
Node *ptrB = listB->nextPtr; // Commence après la tête de listB.
Node *currentMerged = mergedList; // Commence à la tête de la liste fusionnée.
while (ptrA != NULL && ptrB != NULL) {
Node *newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL) return 0; // Échec d'allocation.
if (ptrA->value <= ptrB->value) {
memcpy(&newNode->value, &ptrA->value, sizeof(DataType));
ptrA = ptrA->nextPtr;
} else {
memcpy(&newNode->value, &ptrB->value, sizeof(DataType));
ptrB = ptrB->nextPtr;
}
newNode->nextPtr = NULL;
currentMerged->nextPtr = newNode;
currentMerged = newNode;
}
// Ajoute les éléments restants de listA, s'il y en a.
while (ptrA != NULL) {
Node *newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL) return 0;
memcpy(&newNode->value, &ptrA->value, sizeof(DataType));
newNode->nextPtr = NULL;
currentMerged->nextPtr = newNode;
currentMerged = newNode;
ptrA = ptrA->nextPtr;
}
// Ajoute les éléments restants de listB, s'il y en a.
while (ptrB != NULL) {
Node *newNode = (Node *)malloc(sizeof(Node));
if (newNode == NULL) return 0;
memcpy(&newNode->value, &ptrB->value, sizeof(DataType));
newNode->nextPtr = NULL;
currentMerged->nextPtr = newNode;
currentMerged = newNode;
ptrB = ptrB->nextPtr;
}
return 1;
}
- Inversion de la liste
Inverse l'ordre des nœuds de la liste chaînée de manière itérative.
// Inverse la liste chaînée 'list' de manière itérative.
// Modifie la liste en place.
void reverseList(LinkedList list) {
if (list == NULL || list->nextPtr == NULL) {
return; // Rien à inverser pour une liste vide ou avec un seul élément.
}
Node *previous = NULL;
Node *current = list->nextPtr; // Commence à partir du premier élément réel.
Node *nextTemp = NULL;
while (current != NULL) {
nextTemp = current->nextPtr; // Sauvegarde le prochain nœud.
current->nextPtr = previous; // Inverse le pointeur du nœud courant.
previous = current; // Avance 'previous'.
current = nextTemp; // Avance 'current'.
}
list->nextPtr = previous; // Le nouveau premier élément est celui qui était le dernier.
}
]]>