Les listes chaînées

Il y a beaucoup de choses indispensables à connaître pour coder sereinement en C. Mais parmi toutes, celle que je juge la plus indispensable est la notion de listes chaînées.

Avant de commencer ce tuto, je souhaite tout de même prévenir mes lecteur que ce tuto s'adresse principalement à des personnes ayant de bonnes bases en C surtout sur les pointeurs et les structures ainsi que l'allocation dynamique. Cependant si vous n'avez pas ces bases, ce tuto peut tout de même vous éclairer sur certains points concernant les pointeurs donc ne fuyez pas tout de suite (il sera toujours temps de le faire en plein milieu ).
Si vous codez plutôt en C , les listes chaînées vous seront plus qu'inutiles vue que les vecteurs, listes, queues et compagnie sont des listes chaînées en mieux :p.

Ceci étant dit, allons-y gaiement :

Les listes chaînées kesako?
Les listes chaînées sont utilisées en C pour créer des listes d'éléments (structures) chaînés entre eux (naaaaaaaaaan c vrai! ). Concrètement, cela permet d'ajouter et de retirer facilement des éléments à cette liste en se déplaçant dedans comme sur des maillons d'une chaîne. A partir de n'importe quel élément, on peut aller à l'élément suivant très facilement.

Et pourquoi pas utiliser un tableau statique alors?
Très bonnes question! Par rapport à un tableau statique, il sera impossible avec une liste chaînée d'aller sur un élément particulier sans avoir à parcourir toute la chaîne depuis l'élément de départ. Par contre, il sera extrêmement simple d'insérer un élément n'importe ou dans la chaîne ou d'en supprimer un (chose impossible avec un tableau statique).

On utilisera donc les liste chaînées principalement pour créer des systèmes de queues ou de files éventuellement bouclées
ex: pour un jeu de type jeu de cartes où les joueurs jouent en cercle à tour de rôle, on pourra facilement créer une structure "joueur" de type liste chaînée que l'on bouclera alors sur elle même.
Pour 4 joueurs on aura quelque chose de ce type:
joueur1->joueur2->joueur3->joueur4->joueur1 ...

Maintenant que vous êtes convaincus de l'utilité des listes chaînées, voyons comment ça se code:
Reprenons l'exemple de tout à l'heure:

Code:


typedef struct joueur joueur;//on redéfinit l'appellation "struct joueur" en "joueur"
struct joueur//on définit la structure joueur
{
  char nom[30];
  int nb_cartes;
  //autres données

 
  joueur *suivant;//le secret des listes chaînées : le pointeur sur l'élément suivant
};


Comme vous pouvez le voir, c'est une structure normale avec un pointeur du type de la structure en plus. Ce pointeur contiendra donc l'adresse de l'élément suivant.
Démonstration:

Code:


int main()
{
  joueur *nouveau=(joueur*)malloc(sizeof(joueur));//on créé un joueur dynamiquement

  //on remplit les champs:
  strcpy(nouveau->nom, "Maitre Akabane");//le nom
  nouveau->nb_cartes=16;
  //on remplit les autres champs

 
  nouveau->suivant=NULL;
 
  return 0;
}


Voilà on a créé un joueur ! (Génial et alors ...)
Et bien il ne reste qu'à créer de la même façon les autres joueurs et les chaîner ensemble. Mais si je fais une pause ici, c'est pour insister sur un point très important:
"Il ne faut jamais perdre la tête!" ( C'est toi mon pauvre Akabane qui perd la tête !)
Je m'explique : le plus compliquer à faire est de créer le premier élément : la tête. En effet, il s'agit non seulement de créer l'élément mais également de garder en mémoire dans une variable ce pointeur avant de créer les élément suivants.

Je vous balance maintenant le code pour créer les 4 joueurs chaînés entre eux afin que vous compreniez.

Code:


int main()
{
  joueur *tete=(joueur*)malloc(sizeof(joueur));//on crée un joueur dynamiquement

  //on remplit les champs:
  strcpy(tete->nom, "Maitre Akabane");//le nom
  tete->nb_cartes=16;
  //on remplit les autres champs

 
  nouveau->suivant=NULL;
 
  int i;
  joueur *precedent=tete;//on crée un pointeur sur l'élément précédent du nouveau que l'on va créer dans le for

  for(i=0;i<3;i  )
  {
      joueur *nouveau=(joueur*)malloc(sizeof(joueur));//on crée un joueur dynamiquement

      //on remplit les champs:
      sprintf(nouveau->nom, "Joueur%d", i 1);//le nom
      nouveau->nb_cartes=16;
      //on remplit les autres champs

 
      nouveau->suivant=NULL;
 
      precedent->suivant=nouveau;//on liste le nouveau à l'élément précédent

      precedent=nouveau;//on place le nouveau précédent sur l'élément que l'on vient de créer avant d'en créer un nouveau
  }
 
  //et voilà la liste est créée
  //pour la bouclée, il ne reste plus qu'à faire :
  nouveau->suivant=tete;//on pointe le suivant du dernier élément créé sur la tête= premier élément de la liste

 
  return 0;
}


Mais comment ça marche ?
C'est très simple ; on crée d'abord le premier élément et on garde un pointeur nommé "tete" dessus. On crée ensuite un pointeur "precedent" qui pointera à chaque passage dans le for sur l'élément que l'on veut chaîner à celui que l'on créé. Pour cela, il suffit juste de faire:

precedent->suivant=nouveau;

Concrètement, cela revient simplement à mémoriser l'adresse du pointeur "nouveau" dans le champ "suivant" du pointeur "precedent", qui n'est autre que l'élément créé juste avant.

Comprendu?

On a donc au final une liste de joueurs chaînés entre eux où "tete" est le début de la liste. Dans notre cas on chaîne en plus le dernier élément créé à la "tete" afin d'avoir une chaîne circulaire.

Il est important de noter que nous avons ici pratiqué un chaînage par l'arrière.
C'est à dire que chaque nouvel élément est chaîné derrière l'élément précédemment créé. On peut également faire un chaînage par devant en gardant un pointeur sur l'élément suivant de celui que l'on créé et en chaînant simplement ce nouvel élément à ce suivant.
Dans ce cas, la tête de la chaîne sera le dernier élément créé (ce qui n'aura aucune importance si la liste est bouclée ).


Maintenant voyons comment se déplacer sur cette liste:
Une fois encore, ce n'est pas bien compliqué.

Code:


int main()
{
  joueur *tete=(joueur*)malloc(sizeof(joueur));//on crée un joueur dynamiquement

  //on remplit les champs:
  strcpy(tete->nom, "Maitre Akabane");//le nom
  tete->nb_cartes=16;
  //on remplit les autres champs

 
  nouveau->suivant=NULL;
 
  int i;
  joueur *precedent=tete;//on crée un pointeur sur l'élément précédent du nouveau que l'on va créer dans le for

  for(i=0;i<3;i  )
  {
      joueur *nouveau=(joueur*)malloc(sizeof(joueur));//on créé un joueur dynamiquement

      //on remplit les champs:
      sprintf(nouveau->nom, "Joueur%d", i 1);//le nom
      nouveau->nb_cartes=16;
      //on remplit les autres champs

 
      nouveau->suivant=NULL;
 
      precedent->suivant=nouveau;//on liste le nouveau à l'élément précédent

      precedent=nouveau;//on place le nouveau précédent sur l'élément que l'on vient de créer avant d'en créer un nouveau
  }
 
  //et voilà la liste est créée
  //pour la bouclée, il ne reste plus qu'à faire:
  nouveau->suivant=tete;//on pointe le suivant du dernier élément créé sur la tete= premier élément de la liste

 
 
  bool continuer=1;
  joueur *J=tete;//joueur dont ce sera le tour
 
  //maintenant on crée la boucle principale de jeu

  while(continuer)
  {
      //on effectue les actions à faire sur le joueur
      J->nb_cartes--;//par exemple le joueur pose une carte

 
      J=J->suivant;//on passe au joueur suivant
  }
 
  return 0;

}


Voici donc ce qui conclue ce tuto pour créer et utiliser une liste chaînée

Il est important de noter que nous avons ici fait un chaînage de type suivant. Il est bien entendu possible de faire un chaînage de type précédent ou même les deux en même temps. On appelle alors cela un double chaînage.

J'espère que vous avez apprécié ce tuto et surtout que vous avez tout compris.