La liste chaînée est une structure de données fondamentale, tout comme les tableaux, elle peut servir de base à la construction d'autres structures de données.
Structure d'une Liste Chaînée
Une liste chaînée est généralement composée de deux parties :
- Une partie contenant les données à stocker.
- Une partie servant de pointeur vers le nœud suivant.
En modifiant le nombre de pointeurs et leur utilisation, on peut transformer une liste chaînée en d'autres structures de données, comme des arbres (par exemple, un arbre binaire) ou des graphes.
Types de Listes Chaînées
Il existe principalement deux types de listes chaînées : les listes chaînées statiques et les listes chaînées dynamiques (ou par pointeurs).
Listes Chaînées Dynamiques (par Pointeur)
Ce type de liste est généralement le premier rencontré lors de l'apprentissage des listes chaînées. Sa caractéristique principale est la création de nœuds par allocation dynamique de mémoire. L'avantage est l'optimisation de l'espace de stockage : il n'y a pas de nœuds superflus. Le revers de la médaille est la nécessité d'une gestion manuelle de la mémoire pour éviter les fuites. De plus, la création de nœuds via des fonctions d'allocation mémoire peut légèrement ralentir le processus.
Exemple de définition typique d'une liste chaînée dynamique :
typedef struct NodeElement {
int valeur;
struct NodeElement *prochain;
} NodeElement;
typedef struct ListeChainee {
NodeElement *debut;
int longueur;
} ListeChainee;
Dans cette implémentation, les nœuds sont intégrés dans la structure de la liste, ce qui peut simplifier l'usage des fonctions associées en réduisant le nombre de pointeurs à manipuler explicitement.
Opérations sur les Listes Chaînées Dynamiques :
Création d'un nœud :
(N'oubliez pas d'inclure les bibliothèques nécessaires pour malloc lors de l'allocation mémoire.)
NodeElement* creerElement(int valeur) {
NodeElement *nouvelElement = (NodeElement*)malloc(sizeof(NodeElement));
if (nouvelElement == NULL) {
// Gérer l'erreur d'allocation mémoire
return NULL;
}
nouvelElement->valeur = valeur;
nouvelElement->prochain = NULL;
return nouvelElement;
}
Initialisation de la liste :
(Il est courant d'utiliser un nœud sentinelle (ou tête factice) qui ne contient pas de données utiles, simplifiant certaines opérations.)
void initialiserListe(ListeChainee *liste) {
liste->debut = creerElement(0); // Nœud sentinelle
if (liste->debut == NULL) {
// Gérer l'erreur
return;
}
liste->longueur = 0;
}
Insertion d'un nœud :
void insererElement(ListeChainee* liste, NodeElement* nouvelElement, int position) {
if (nouvelElement == NULL) return;
NodeElement *elementCourant = liste->debut;
// Parcourir jusqu'à la position d'insertion (avant l'élément à la position 'position')
for (int i = 0; i < position; ++i) {
if (elementCourant->prochain == NULL) {
// La position est hors limites, insérer à la fin
elementCourant = elementCourant->prochain; // Sera NULL
break;
}
elementCourant = elementCourant->prochain;
}
if (elementCourant == NULL && position > 0) {
// Position hors limites et pas au début
// Gérer l'erreur ou insérer à la fin si applicable
return;
}
nouvelElement->prochain = elementCourant->prochain;
elementCourant->prochain = nouvelElement;
liste->longueur++;
}
Suppression d'un nœud :
void supprimerElement(ListeChainee *liste, int position) {
if (position < 0 || position >= liste->longueur) {
// Position invalide
return;
}
NodeElement *elementCourant = liste->debut;
// Parcourir jusqu'à l'élément PRÉCÉDANT celui à supprimer
for (int i = 0; i < position; ++i) {
elementCourant = elementCourant->prochain;
}
NodeElement *aSupprimer = elementCourant->prochain;
elementCourant->prochain = aSupprimer->prochain;
free(aSupprimer);
liste->longueur--;
}
Listes Chaînées Statiques
Ce type de liste est parfois rencontré dans des contextes de programmation compétitive. Il simule une liste chaînée en utilisant un tableau et des indices pour représenter les pointeurs. La mémoire est allouée en bloc au démarrage du programme, évitant les allocations dynamiques lors de l'exécution, ce qui améliore la vitesse et simplifie la gestion de la mémoire. C'est une solution avantageuse pour ceux qui préfèrent éviter la gestion manuelle de la mémoire et le débogage associé.
La structure d'une liste chaînée statique vue sous l'angle d'un tableau :
Bien que cela puisse sembler désordonné, en identifiant le début et la fin, on peut visualiser une structure ordonnée. En essence, les pointeurs sont remplacés par des indices de tableau.
Exemple d'implémentation :
#define TAILLE_MAX_NOEUDS 110
struct ElementNoeud {
int valeur;
int indexProchain; // Utilise un indice au lieu d'un pointeur
} elements[TAILLE_MAX_NOEUDS];
Comme il n'y a pas de pointeurs, des variables supplémentaires sont nécessaires pour gérer l'état de la liste :
int indexTete = -1; // Index du premier élément de la liste
int compteurElementsUtilises = 0; // Nombre d'éléments déjà utilisés
Opérations sur les Listes Chaînées Statiques :
Initialisation :
void initialiserListeStatique(void) {
// Initialiser le tableau pour indiquer que les éléments sont libres
// Ici, on utilise -1 pour tous les index, indiquant qu'ils ne sont pas liés.
// Une initialisation plus robuste pourrait marquer les éléments comme libres.
for(int i = 0; i < TAILLE_MAX_NOEUDS; ++i) {
elements[i].indexProchain = -1;
elements[i].valeur = 0; // Valeur par défaut
}
indexTete = -1;
compteurElementsUtilises = 0;
}
Insertion en tête :
(Cette fonction insère un nouvel élément au début de la liste.)
void insererEnTete(int valeur) {
if (compteurElementsUtilises >= TAILLE_MAX_NOEUDS) {
// Gérer le cas où le tableau est plein
return;
}
elements[compteurElementsUtilises].valeur = valeur;
elements[compteurElementsUtilises].indexProchain = indexTete;
indexTete = compteurElementsUtilises;
compteurElementsUtilises++;
return;
}
Insertion générale :
void insererElementParIndex(int valeur, int position) {
if (position < 0) {
// Position invalide
return;
}
if (compteurElementsUtilises >= TAILLE_MAX_NOEUDS) {
// Tableau plein
return;
}
if (position == 0) {
insererEnTete(valeur);
return;
}
int indexCourant = indexTete;
// Trouver l'élément AVANT la position d'insertion
for (int i = 0; i < position - 1; ++i) {
if (indexCourant == -1 || elements[indexCourant].indexProchain == -1) {
// Position hors limites
// On pourrait insérer à la fin si indexCourant != -1
return;
}
indexCourant = elements[indexCourant].indexProchain;
}
if (indexCourant == -1) return; // Ne devrait pas arriver si position > 0 et liste non vide
elements[compteurElementsUtilises].valeur = valeur;
elements[compteurElementsUtilises].indexProchain = elements[indexCourant].indexProchain;
elements[indexCourant].indexProchain = compteurElementsUtilises;
compteurElementsUtilises++;
return;
}
Suppression d'un élément :
void supprimerElementParIndex(int position) {
if (position < 0 || indexTete == -1) {
// Position invalide ou liste vide
return;
}
if (position == 0) {
indexTete = elements[indexTete].indexProchain;
// L'élément supprimé n'est pas explicitement libéré ici, il devient inutilisé.
// On pourrait marquer `elements[ancien_index_tete].indexProchain = -1;`
return;
}
int indexCourant = indexTete;
// Trouver l'élément AVANT celui à supprimer
for (int i = 0; i < position - 1; ++i) {
if (indexCourant == -1 || elements[indexCourant].indexProchain == -1) {
// Position hors limites
return;
}
indexCourant = elements[indexCourant].indexProchain;
}
if (indexCourant == -1 || elements[indexCourant].indexProchain == -1) return; // Position invalide
int indexASupprimer = elements[indexCourant].indexProchain;
elements[indexCourant].indexProchain = elements[indexASupprimer].indexProchain;
// L'élément supprimé n'est pas explicitement libéré ici.
// On pourrait marquer `elements[indexASupprimer].indexProchain = -1;` pour le réutiliser.
return;
}
Un inconvénient des listes chaînées statiques est qu'elles ne disposent pas d'un mécanisme de récupération explicite des éléments du tableau une fois supprimés. Après de nombreuses insertions et suppressions, il est possible de se retrouver dans une situation où il y a peu d'éléments actifs dans la liste, mais plus d'espace disponible dans le tableau. Par conséquent, lors de l'utilisation de listes statiques, il faut considérer la fréquence des opérations de modification, en particulier les suppressions. Dans les contextes de programmation compétitive, ces listes sont souvent utilisées pour stocker les arêtes d'un graphe, où les suppressions sont rares.
Conclusion
- Les listes chaînées dynamiques offrent une grande flexibilité et une structure plus intuitive. Une bonne compréhension de leurs concepts facilite l'appréhension des listes statiques. Cependant, elles exigent une gestion attentive de la mémoire.
- Les listes chaînées statiques sont plus rapides et plus sûres en termes de gestion de la mémoire, mais elles sont moins adaptées aux opérations de modification fréquentes.
- L'utilisation d'un nœud sentinelle (tête factice) peut simplifier l'implémentation de nombreuses opérations.