Langage C - Les listes chaînées

---

La notion de structure autoréferrentielle

Une structure autoréferrentielle (parfois appelée structure récursive) correspond à une structure dont au moins un des champs contient un pointeur vers une structure de même type. De cette façon on crée des éléments (appelés parfois noeuds ou liens) contenant des données, mais, contrairement à un tableau, celles-ci peuvent être éparpillées en mémoire et reliées entre elles par des liens logiques (des pointeurs), c'est-à-dire un ou plusieurs champs dans chaque structure contenant l'adresse d'une ou plusieurs structures de même type.

• Lorsque la structure contient des données et un pointeur vers la structure suivante on parle de liste chaînée
• Lorsque la structure contient des données, un pointeur vers la structure suivante, et un pointeur vers la structure précédente on parle de liste chaînée double
• Lorsque la structure contient des données, un pointeur vers une première structure suivante, et un pointeur vers une seconde, on parle d'arbre binaire

Qu'est-ce qu'une liste chaînée ?

Une liste chaînée est une structure comportant des champs contenant des données et un pointeur vers une structure de même type. Ainsi, la structure correspondant à une liste chaînée contenant une chaîne de 15 caractères et un entier ressemble à ceci :

struct Nom_de_la_liste {
char Chaine[16];

int Entier;

struct Nom_de_la_liste * pSuivant;

};

On représente généralement cette structure de la manière suivante :

Chaîne

Entier

Pointeur vers suivant

Une liste chaînée se représente donc de la façon suivante :

En réalité la déclaration de la structure et la récursivité de celle-ci grâce à des pointeurs est nécessaire car cela crée une chaîne d'enregistrements liés par des liens logiques, mais cela n'est pas suffisant. En effet, il est nécessaire de conserver une « trace » du premier enregistrement afin de pouvoir accéder aux autres, c'est pourquoi un pointeur vers le premier élément de la liste est indispensable. Ce pointeur est appelé pointeur de tête. D'autre part, étant donné que le dernier enregistrement ne pointe vers rien, il est nécessaire de donner à son pointeur la valeur NULL :

Pour créer une liste chaînée en langage C, il s'agit dans un premier temps de définir la structure de données, ainsi qu'un pointeur vers une structure du type de celle définie précédemment, afin de pointer vers la tête de la liste, c'est-à-dire le premier enregistrement :

struct Liste {
char Chaine[16];

struct Liste * pSuivant;

};

struct Liste *Nouveau;

struct Liste *Tete;

Tete = NULL;

Ajout d'un premier élément

Une fois la structure et les pointeurs définis, il est possible d'ajouter un premier maillon à la liste chaînée, puis de l'affecter au pointeur Tete. Pour cela il est nécessaire :

• d'allouer la mémoire nécessaire au nouveau maillon grâce à la fonction malloc, selon la syntaxe suivante :

  Nouveau = (Liste*)malloc(sizeof(struct Liste));

• d'assigner au champ « pointeur » du nouveau maillon, la valeur du pointeur vers le maillon de tête :

  Nouveau->pSuivant = Tete;

• définir le nouveau maillon comme maillon de tête :

  Tete = Nouveau;

Il est conseillé de tester la valeur renvoyée en retour par la fonction malloc() afin de savoir si l'allocation dynamique de mémoire s'est déroulée correctement.

Ajout d'un élément en fin de liste

L'ajout d'un élément à la fin de la liste chaînée est similaire, à la différence près qu'il faut définir un pointeur (appelé généralement pointeur courant) afin de parcourir la liste jusqu'à atteindre le dernier maillon (celui dont le pointeur possède la valeur NULL). Les étapes à suivre sont donc :

• la définition d'un pointeur courant :

  struct Liste * pCourant;

• le parcours de la liste chaînée jusqu'au dernier noeud :

  if (Tete != NULL) {
  pCourant = Tete;
  
  while (pCourant->pSuivant != NULL) pCourant = pCourant->pSuivant;
  
  }

• l'allocation de mémoire pour le nouvel élément :

  Nouveau = (Liste*)malloc(sizeof(struct Liste));

• faire pointer le pointeur courant vers le nouveau noeud, et le nouveau noeud vers NULL :

  pCourant->pSuivant = Nouveau;
  
  Nouveau->pSuivant = NULL;

Qu'est-ce qu'une liste chaînée double ?

Une liste chaînée double est basée sur le même principe que la liste chaînée simple, à la différence près qu'elle contient non seulement un pointeur vers le maillon suivant mais aussi un pointeur vers le maillon précédent, permettant de cette façon le parcours de la liste dans les deux sens. Ainsi, la structure correspondant à une liste chaînée double contenant une chaîne de 15 caractères et un entier ressemble à ceci :

struct Liste {
char Chaine[16];

int Entier;

struct Liste * pSuivant;

struct Liste * pPrecedent
};

On représente généralement cette structure de la manière suivante :

Données

Pointeur vers suivant

Pointeur vers précédent

Une liste chaînée double se représente donc de la façon suivante :

Trucs & astuces pertinents trouvés dans la base de connaissances

10/01 11h10	Liste régulièrement mise à jour (Logiciels)
23/09 17h45	Suppression impossible : liste d'arguments trop longue (Bash)
14/01 20h35	Obtenir la liste des fichiers d'un dossier (Logiciels)
10/01 12h40	Démarrage : Oter les pseudos de la liste déroulante (MSN Messenger)
04/11 19h59	Liste des paquetages (packages) installés (Debian)
Plus d'astuces sur « C liste chainee »

Discussions pertinentes trouvées dans le forum

04/05 22h23	Création liste chainée en C	Développement	06/06 10h09->hayet	12
28/12 16h52	liste chainée en C !	Développement	29/11 16h20->lami20j	5
05/05 20h44	[VS C++ .Net] Liste chaînée (linked list)	Développement	06/05 17h06->ch_salim	1
31/10 09h20	enregistrement d'une liste chainee C++	Développement	11/01 07h54->Bravi	6
30/12 15h41	pb chaine de caractères ds liste chainée en C	Développement	30/12 17h03->maily	6
13/12 11h06	suppression dans une liste chainée	Développement	18/01 15h45->mister_dsg	5
14/01 14h22	Liste chainée en PHP?	Webmastering	15/01 20h33->ShaoShiva	5
15/11 00h45	Liste doublement chainée en C	Développement	16/11 01h34->de passage...	4
20/10 15h46	Probleme de liste chainée en C	Développement	20/10 23h55->mamiemando	4
17/10 15h41	liste châinée	Développement	17/10 18h00->hssissen	3
Discussion fermée Problème résolu		Plus de discussions sur « C liste chainee »

Ce document intitulé « Langage C - Les listes chaînées » issu de l'encyclopédie informatique Comment Ça Marche (www.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.