Liste simplement chaînée

Note : lami20j est l'auteur d'origine de l'astuce.

LISTES SIMPLEMENT CHAINÉES

Requis

Les types de données
Les structures
L'utilisation de typedef
Les pointeurs
Les fonctions utilisateur

INTRODUCTION

Cette article a pour but la compréhension des listes simplement chaînées.
L'implémentation en fonction des besoins et des performances vous appartient.
Les listes chaînées peuvent être utilisées quand plusieurs opérations d'insertion/suppression d'éléments sont nécessaires.

Définition

Les listes chaînées sont des structures de données semblables aux tableaux sauf que l'accès à un élément ne se fait pas par index mais à l'aide d'un pointeur.
L'allocation de la mémoire est faite au moment de l'exécution.

Dans une liste les éléments sont contigus en ce qui concerne l'enchaînement.


En revanche, par rapport aux tableaux où les éléments sont contigus dans la mémoire, les éléments d'une liste sont éparpillés dans la mémoire.
La liaison entre les éléments se fait grâce à un pointeur.
En réalité, dans la mémoire la représentation est aléatoire en fonction de l'espace alloué.

Le pointeur suivant du dernier élément doit pointer vers NULL (la fin de la liste).

Pour accéder à un élément la liste est parcourue en commençant avec la tête, le pointeur suivant permettant le déplacement vers le prochain élément.
Le déplacement se fait dans une seule direction, du premier vers le dernier élément.
Si vous voulez vous déplacer dans les deux directions (en avant/en arrière) utilisez les listes doublement chaînées.

La construction du prototype d'un élément de la liste

Pour définir un élément de la liste le type struct sera utilisé.
L'élément de la liste contiendra un champ donnee et un pointeur suivant.
Le pointeur suivant doit être du même type que l'élément, sinon il ne pourra pas pointer vers l'élément.
Le pointeur "suivant" permettra l'accès vers le prochain élément.

typedef struct ElementListe {
  char                *donnee;
  struct ElementListe *suivant;
}Element;

Pour avoir le contrôle de la liste il est préférable de sauvegarder certains éléments :
le premier élément, le dernier élément, le nombre d'éléments.


Pour réaliser cela une autre structure sera utilisée (ce n'est pas obligatoire, des variables peuvent être utilisées).
Voici sa composition:

typedef struct ListeRepere {
  Element *debut;
  Element *fin;
  int taille;
}Liste;

Le pointeur debut contiendra l'adresse du premier élément de la liste.
Le pointeur fin contiendra l'adresse du dernier élément de la liste.
La variable taille contient le nombre d'éléments.

Quelque soit la position dans la liste, les pointeurs debut et fin pointent toujours respectivement vers le 1er et le dernier élément.
Le champ taille contiendra le nombre d'éléments de la liste quelque soit l'opération effectuée sur la liste.

Opérations sur les listes chaînées

Pour l'insertion ainsi que pour la suppression, une seule fonction est largement suffisante si elle est bien conçue en fonction des besoins.
Toutefois je vous rappelle que cet article est purement didactique.
C'est la raison pour laquelle j'ai écrit une fonction pour chaque opération d'insertion et de suppression.

Initialisation

Prototype de la fonction :

void initialisation (Liste *liste);

Cette opération doit être faite avant toute autre opération sur la liste.
Elle initialise le pointeur debut et le pointeur fin avec le pointeur NULL, et la taille avec la valeur 0.

La fonction

void initialisation (Liste *liste){
  liste->debut = NULL;
  liste->fin = NULL;
  taille = 0;
}

Insertion d'un élément dans la liste

Voici l'algorithme d'insertion et de sauvegarde des éléments :

• déclaration d'élément(s) à insérer
• allocation de la mémoire pour le nouvel élément
• remplir le contenu du champ de données
• mettre à jour les pointeurs vers le 1er et le dernier élément si nécessaire.
  • Cas particulier : dans une liste avec un seul élément, le 1er est en même temps le dernier.
  • mettre à jour la taille de la liste

Pour ajouter un élément dans la liste il y a plusieurs situations :

• 1. Insertion dans une liste vide
• 2. Insertion au début de la liste
• 3. Insertion à la fin de la liste
• 4. Insertion ailleurs dans la liste

Insertion dans une liste vide

Prototype de la fonction :

int ins_dans_liste_vide (Liste *liste, char *donnee);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.

Étapes :

• allocation de la mémoire pour le nouvel élément
• remplir le champ de données du nouvel élément
• le pointeur suivant du nouvel élément pointera vers NULL (vu que l'insertion est faite dans une liste vide on utilise l'adresse du pointeur debut qui vaut NULL)
• les pointeurs debut et fin pointeront vers le nouvel élément
• la taille est mise à jour

La fonction

/* insertion dans une liste vide */
int ins_dans_liste_vide (Liste * liste, char *donnee){
  Element *nouveau_element;
  if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL)
    return -1;
  if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char)))
      == NULL)
    return -1;
  strcpy (nouveau_element->donnee, donnee);

  nouveau_element->suivant = NULL;
  liste->debut = nouveau_element;
  liste->fin = nouveau_element;
  liste->taille++;
  return 0;
}

Insertion au début de la liste

Prototype de la fonction :

int ins_debut_liste (Liste *liste,char *donnee);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.


Étapes:

• allocation de la mémoire pour le nouvel élément
• remplir le champ de données du nouvel élément
• le pointeur suivant du nouvel élément pointe vers le 1er élément
• le pointeur debut pointe vers le nouvel élément
• le pointeur fin ne change pas
• la taille est incrémentée

La fonction

/* insertion au début de la liste */
int ins_debut_liste (Liste * liste, char *donnee){
  Element *nouveau_element;
  if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL)
    return -1;
  if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char)))
      == NULL)
    return -1;
  strcpy (nouveau_element->donnee, donnee);

  nouveau_element->suivant = liste->debut;
  liste->debut = nouveau_element;
  liste->taille++;
  return 0;
}

Insertion à la fin de la liste

Prototype de la fonction :

int ins_fin_liste (Liste *liste, Element *courant, char *donnee);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.

Étapes:

• allocation de la mémoire pour le nouvel élément
• remplir le champ de données du nouvel élément
• le pointeur suivant du dernier élément pointe vers le nouvel élément
• le pointeur fin pointe vers le nouvel élément
• le pointeur debut ne change pas
• la taille est incrémentée

La fonction

/*insertion à la fin de la liste */
int ins_fin_liste (Liste * liste, Element * courant, char *donnee){
  Element *nouveau_element;
  if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL)
    return -1;
  if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char)))
      == NULL)
    return -1;
  strcpy (nouveau_element->donnee, donnee);

  courant->suivant = nouveau_element;
  nouveau_element->suivant = NULL;

  liste->fin = nouveau_element;

  liste->taille++;
  return 0;
}

Insertion ailleurs dans la liste

Prototype de la fonction :

int ins_liste (Liste *liste, char *donnee,int pos);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.

L'insertion s'effectuera après une certaine position passée en argument à la fonction.
Si la position indiquée ne doit pas être le dernier élément. Dans ce cas il faut utiliser la fonction d'insertion à la fin de la liste.

Étapes:

• allocation de la mémoire pour le nouvel élément
• remplir le champ de données du nouvel élément
• choisir une position dans la liste (l'insertion se fera après la position choisie)
• le pointeur suivant du nouvel élément pointe vers l'adresse sur laquelle pointe le pointeur suivant d'élément courant. (cette explication est un peu tordue, mais l'image vous éclaira ;-)
• le pointeur suivant du l'élément courant pointe vers le nouvel élément
• les pointeurs debut et fin ne change pas
• la taille est incrémentée d'une unité

La fonction

/* insertion à la position demandée */
int ins_liste (Liste * liste, char *donnee, int pos){
  if (liste->taille < 2)
    return -1;
  if (pos < 1 || pos >= liste->taille)
    return -1;

  Element *courant;
  Element *nouveau_element;
  int i;

  if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL)
    return -1;
  if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char)))
      == NULL)
    return -1;

  courant = liste->debut;
  for (i = 1; i < pos; ++i)
    courant = courant->suivant;
  if (courant->suivant == NULL)
    return -1;
  strcpy (nouveau_element->donnee, donnee);

  nouveau_element->suivant = courant->suivant;
  courant->suivant = nouveau_element;
  liste->taille++;
  return 0;
}

Suppression d'un élément dans la liste

Voici l'algorithme de suppression d'un élément de la liste :

• utilisation d'un pointeur temporaire pour sauvegarder l'adresse d'éléments à supprimer
• l'élément à supprimer se trouve après l'élément courant

Faire pointer le pointeur suivant de l'élément courant vers l'adresse du pointeur suivant de l'élément à supprimer

• libérer la mémoire occupée par l'élément supprimé
• mettre à jour la taille de la liste

Pour supprimer un élément dans la liste il y a plusieurs situations :

• 1. Suppression au début de la liste
• 2. Suppression ailleurs dans la liste

Suppression au début de la liste

Prototype de la fonction:

int supp_debut (Liste *liste);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.


Étapes:

• le pointeur supp_elem contiendra l'adresse du 1er élément
• le pointeur debut pointera vers le 2ème élément
• la taille de la liste sera décrémentée d'un élément

La fonction

/* suppression au début de la liste */
int supp_debut (Liste * liste){
  if (liste->taille == 0)
    return -1;
  Element *supp_element;
  supp_element = liste->debut;
  liste->debut = liste->debut->suivant;
  if (liste->taille == 1)
    liste->fin = NULL;
  free (supp_element->donnee);
  free (supp_element);
  liste->taille--;
  return 0;
}

Suppression ailleurs dans la liste

Prototype de la fonction:

int supp_dans_liste (Liste *liste, int pos);

La fonction renvoie -1 en cas d'échec sinon elle renvoie 0.

Étapes:

• le pointeur supp_elem contiendra l'adresse vers laquelle pointe le pointeur suivant d'élément courant
• le pointeur suivant de l'élément courant pointera vers l'élément sur lequel pointe le pointeur suivant de l'élément qui suit l'élément courant dans la liste

Si l'élément courant est l'avant dernier élément, le pointeur fin doit être mis à jour

• la taille de la liste sera décrémentée d'un élément

La fonction

/* supprimer un element après la position demandée */
int supp_dans_liste (Liste * liste, int pos){
  if (liste->taille <= 1 || pos < 1 || pos >= liste->taille)
    return -1;
  int i;
  Element *courant;
  Element *supp_element;
  courant = liste->debut;

  for (i = 1; i < pos; ++i)
    courant = courant->suivant;

  supp_element = courant->suivant;
  courant->suivant = courant->suivant->suivant;
  if(courant->suivant == NULL)
          liste->fin = courant;
  free (supp_element->donnee);
  free (supp_element);
  liste->taille--;
  return 0;
}

Affichage de la liste

Pour afficher la liste entière il faut se positionner au début de la liste (le pointeur debut le permettra).
Ensuite en utilisant le pointeur suivant de chaque élément la liste est parcourue du 1er vers le dernier élément.
La condition d'arrêt est donnée par le pointeur suivant du dernier élément qui vaut NULL.

La fonction

/* affichage de la liste */
void affiche (Liste * liste){
  Element *courant;
  courant = liste->debut;
  while (courant != NULL){
      printf ("%p - %s
", courant, courant->donnee);
      courant = courant->suivant;
  }
}

Destruction de la liste

Pour détruire la liste entière, j'ai utilisé la suppression au début de la liste tant que la taille est plus grande que zéro.

La fonction

/* détruire la liste */
void detruire (Liste * liste){
  while (liste->taille > 0)
    supp_debut (liste);
}

Exemple complet

liste.h

/* ---------- liste.h ----------- */
typedef struct ElementListe
{
    char *donnee;
    struct ElementListe *suivant;
} Element;

typedef struct ListeRepere
{
    Element *debut;
    Element *fin;
    int taille;
} Liste;

/* initialisation de la liste */
void initialisation (Liste * liste);


/* INSERTION */

/* insertion dans une liste vide */
int ins_dans_liste_vide (Liste * liste, char *donnee);

/* insertion au début de la liste */
int ins_debut_liste (Liste * liste, char *donnee);

/* insertion à a fin de la liste */
int ins_fin_liste (Liste * liste, Element * courant, char *donnee);

/* insertition ailleurs */
int ins_liste (Liste * liste, char *donnee, int pos);


/* SUPPRESSION */

int supp_debut (Liste * liste);
int supp_dans_liste (Liste * liste, int pos);


int menu (Liste *liste,int *k);
void affiche (Liste * liste);
void detruire (Liste * liste);
/* -------- FIN liste.h --------- */

liste_function.h

/***************************
 *     liste_function.h      *
 ***************************/

void initialisation (Liste * liste) {
 liste->debut = NULL;
 liste->fin = NULL;
 liste->taille = 0;
}

/* insertion dans une liste vide */
int ins_dans_liste_vide (Liste * liste, char *donnee){
 Element *nouveau_element;
 if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL)
  return -1;
 if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char)))
   == NULL)
  return -1;
 strcpy (nouveau_element->donnee, donnee);
 nouveau_element->suivant = NULL;
 liste->debut = nouveau_element;
 liste->fin = nouveau_element;
 liste->taille++;
 return 0;
}

/* insertion au début de la liste */
int ins_debut_liste (Liste * liste, char *donnee){
 Element *nouveau_element;
 if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL)
  return -1;
 if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char)))
   == NULL)
  return -1;
 strcpy (nouveau_element->donnee, donnee);
 nouveau_element->suivant = liste->debut;
 liste->debut = nouveau_element;
 liste->taille++;
 return 0;
}

/*insertion à la fin de la liste */
int ins_fin_liste (Liste * liste, Element * courant, char *donnee){
 Element *nouveau_element;
 if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL)
  return -1;
 if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char)))
   == NULL)
  return -1;
 strcpy (nouveau_element->donnee, donnee);
 courant->suivant = nouveau_element;
 nouveau_element->suivant = NULL;
 liste->fin = nouveau_element;
 liste->taille++;
 return 0;
}

/* insertion à la position demandée */
int ins_liste (Liste * liste, char *donnee, int pos){
 if (liste->taille < 2)
  return -1;
 if (pos < 1 || pos >= liste->taille)
  return -1;
 Element *courant;
 Element *nouveau_element;
 int i;
 if ((nouveau_element = (Element *) malloc (sizeof (Element))) == NULL)
  return -1;
 if ((nouveau_element->donnee = (char *) malloc (50 * sizeof (char)))
   == NULL)
  return -1;
 courant = liste->debut;
 for (i = 1; i < pos; ++i)
  courant = courant->suivant;
 if (courant->suivant == NULL)
  return -1;
 strcpy (nouveau_element->donnee, donnee);
 nouveau_element->suivant = courant->suivant;
 courant->suivant = nouveau_element;
 liste->taille++;
 return 0;
}

/* suppression au début de la liste */
int supp_debut (Liste * liste){
 if (liste->taille == 0)
  return -1;
 Element *supp_element;
 supp_element = liste->debut;
 liste->debut = liste->debut->suivant;
 if (liste->taille == 1)
  liste->fin = NULL;
 free (supp_element->donnee);
 free (supp_element);
 liste->taille--;
 return 0;
}
/* supprimer un element après la position demandée */
int supp_dans_liste (Liste * liste, int pos){
 if (liste->taille <= 1 || pos < 1 || pos >= liste->taille)
  return -1;
 int i;
 Element *courant;
 Element *supp_element;
 courant = liste->debut;
 for (i = 1; i < pos; ++i)
  courant = courant->suivant;
 supp_element = courant->suivant;
 courant->suivant = courant->suivant->suivant;
 if(courant->suivant == NULL)
  liste->fin = courant;
 free (supp_element->donnee);
 free (supp_element);
 liste->taille--;
 return 0;
}

/* affichage de la liste */
void affiche (Liste * liste){
 Element *courant;
 courant = liste->debut;
 while (courant != NULL){
  printf ("%p - %s
", courant, courant->donnee);
  courant = courant->suivant;
 }
}

/* detruire la liste */
void detruire (Liste * liste){
 while (liste->taille > 0)
  supp_debut (liste);
}

int menu (Liste *liste,int *k){
 int choix;
 printf("********** MENU **********
");
 if (liste->taille == 0){
  printf ("1. Ajout du 1er element
");
  printf ("2. Quitter
");
 } else if(liste->taille == 1 || *k == 1){
  printf ("1. Ajout au debut de la liste
");
  printf ("2. Ajout a la fin de la liste
");
  printf ("4. Suppression au debut de la liste
");
  printf ("6. Detruire la liste
");
  printf ("7. Quitter
");
 }else {
  printf ("1. Ajout au debut de la liste
");
  printf ("2. Ajout a la fin de la liste
");
  printf ("3. Ajout apres la position specifie
");
  printf ("4. Suppression au debut de la liste
");
  printf ("5. Suppression apres la position specifie
");
  printf ("6. Detruire la liste
");
  printf ("7. Quitter
");
 }
 printf ("

Faites votre choix : ");
 scanf ("%d", &choix);
 getchar();
 if (liste->taille == 0 && choix == 2)
  choix = 7;
 return choix;
}

/* -------- FIN liste_function.h --------- */

liste.c

/**********************
 *     liste.c          *
 **********************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "liste.h"
#include "liste_function.h"

int main (void) {
 char choix;
 char *nom;
 Liste *liste;
 Element *courant;
 if ((liste = (Liste *) malloc (sizeof (Liste))) == NULL)
  return -1;
 if ((nom = (char *) malloc (50)) == NULL)
  return -1;
 courant = NULL;
 choix = 'o';
 initialisation (liste);
 int pos, k;
 while (choix != 7){
  choix = menu (liste, &k);
  switch (choix){
   case 1:
    printf ("Entrez un element : ");
    scanf ("%s", nom);
    getchar ();
    if (liste->taille == 0)
     ins_dans_liste_vide (liste, nom);
    else
     ins_debut_liste (liste, nom);
    printf ("%d elements:deb=%s,fin=%s
", liste->taille,
      liste->debut->donnee, liste->fin->donnee);
    affiche (liste);
    break;
   case 2:
    printf ("Entrez un element : ");
    scanf ("%s", nom);
    getchar ();
    ins_fin_liste (liste, liste->fin, nom);
    printf ("%d elements:deb=%s,fin=%s
", liste->taille,
      liste->debut->donnee, liste->fin->donnee);
    affiche (liste);
    break;
   case 3:
    printf ("Entrez un element : ");
    scanf ("%s", nom);
    getchar ();
    do{
     printf ("Entrez la position : ");
     scanf ("%d", &pos);
    }
    while (pos < 1 || pos > liste->taille);
    getchar ();
    if (liste->taille == 1 || pos == liste->taille){
     k = 1;
     printf("-----------------------------------------------
");
     printf(" Insertion echouée.Utilisez le menu {1|2}  \n");
     printf("-----------------------------------------------
");
     break;
    }
    ins_liste (liste, nom, pos);
    printf ("%d elements:deb=%s,fin=%s
", liste->taille,
      liste->debut->donnee, liste->fin->donnee);
    affiche (liste);
    break;
   case 4:
    supp_debut (liste);
    if (liste->taille != 0)
     printf ("%d elements:deb=%s,fin=%s
", liste->taille,
       liste->debut->donnee, liste->fin->donnee);
    else
     printf ("liste vide
");
    affiche (liste);
    break;
   case 5:
    do{
     printf ("Entrez la position : ");
     scanf ("%d", &pos);
    }
    while (pos < 1 || pos > liste->taille);
    getchar ();
    supp_dans_liste (liste, pos);
    if (liste->taille != 0)
     printf ("%d elements:deb=%s,fin=%s
", liste->taille,
       liste->debut->donnee, liste->fin->donnee);
    else
     printf ("liste vide
");
    affiche (liste);
    break;
   case 6:
    detruire (liste);
    printf ("la liste a ete detruite : %d elements
", liste->taille);
    break;
  }
 }
 return 0;
} 

Voir aussi

• les listes doublement chaînées
• les listes circulaires
• les piles
• les files