Une liste chainée est simplement une liste d'objet de même type dans laquelle chaque élément contient :

• Des informations relatives au fonctionnement de l'application, par exemple des noms et prénoms de personnes avec adresses et numéros de téléphone pour un carnet d'adresse.
• L'adresse de l'élément suivant ou une marque de fin s'il n'y a pas de suivant. C'est ce lien via l'adresse de l'élément suivant contenue dans l'élément précédent qui fait la "chaine" et permet de retrouver chaque élément de la liste.

L'adresse de l'objet suivant peut être :

• une adresse mémoire récupérée avec un pointeur (chainage dynamique).
• un indice de tableau récupéré avec un entier
• une position dans un fichier. C'est le numéro d'ordre de l'objet dans le fichier multipliée par la taille en octet du type de l'objet. Elle est récupérée avec un entier.

Que la liste chainée soit bâtie avec des pointeurs ou des entiers, c'est toujours le terme de pointeur qui est utilisé : chaque élément "pointe" sur l'élément suivant, c'est à dire possède le moyen d'y accéder et une liste chainée peut se représenter ainsi :

Chaque carré correspond à un maillon de la chaine. Le petit carré noir en haut à gauche correspond à l'adresse en mémoire de l'élément. Le petit rond en bas à droite correspond au pointeur qui "pointe" sur le suivant, c'est à dire qui contient l'adresse de l'élément suivant. Au départ il y a le pointeur de tête qui contient l'adresse du premier élément c'est à dire l'adresse de la chaine.

Exercices de manipulations de listes chaînées :

1. Créez une liste avec les n premiers entiers dans l’ordre décroissant.
2. Calculez la moyenne d’une liste.
3. Retournez la liste des carrés d’une autre liste passée en paramètre.
4. Retirez le premier élément d’une liste.
5. Insérer un élément à la fin d’une liste.

#include <stdio.h>
#include <stdlib.h>

typedef struct element * Pelement;
typedef struct liste * FListe;
typedef struct element{
       int x;
       Pelement suivant;
}Element;

typedef struct liste{
       Pelement premier;
       Pelement courant;
       Pelement dernier;
}Liste;

void initListe(FListe L){
       L = (FListe) malloc ( sizeof(Liste));
       L->premier = (Pelement) malloc ( sizeof(Element));
       L->courant = (Pelement) malloc ( sizeof(Element));
       L->dernier = (Pelement) malloc ( sizeof(Element));
       L->premier = NULL;
       L->courant = NULL;
       L->dernier = NULL;
}

void insereUnElemt(FListe L, Pelement nouveau){
       nouveau->suivant = L->premier;
       L->premier = nouveau;
       if( L->dernier ==NULL )
              L->dernier = nouveau;
}

void creeListeDecroissante(FListe L, int n){
       printf("***** creeListeDecroissante() *****\n");
       int i;
       Pelement Pel;
       for(i=1; i<=n; i++){
              Pel = (Pelement)malloc( sizeof (Element));
              Pel->x = i;
              insereUnElemt(L, Pel);
       }
}

void afficheListe(FListe L){
       L->courant = L->premier;
       while (L->courant != NULL){
              printf("%d, ", L->courant->x);
              L->courant = L->courant->suivant;
       }
}

float moyenne(FListe L){
       int som = 0, cpt = 0;
       L->courant = L->premier;
       while (L->courant != NULL){
              cpt++;
              som += L->courant->x;
              L->courant = L->courant->suivant;
       }
       return (som/cpt);
}

Liste l;maListe = &l;
int main(){
       initListe(maListe);
       creeListeDecroissante(maListe, 5);
       printf("** afficheListe() ** \n[ ");
       afficheListe(maListe);

       printf(" ]\n");

       printf("Moyenne(Liste) = %.2f\n", moyenne(maListe));
       return 0;
}

void carres(FListe L, FListe Lc){
      Pelement el;
      initListe(Lc);
      L->courant = L->premier;
      while (L->courant != NULL){
            el = (Pelement) malloc(sizeof(Element));
            el->x = pow(L->courant->x, 2);
            inserFinListe(Lc, el);
            L->courant = L->courant->suivant;
      }
}

void supprimePremier(FListe L){
      Pelement el = L->premier;
      L->premier = L->premier->suivant;
      free(el);
      el=NULL;
}

void inserFinListe(FListe L, Pelement nouveau){
      if (L->dernier ==NULL){
            insereUnElemt(L, nouveau);
      }else{
            nouveau->suivant = L->dernier->suivant;
            L->dernier->suivant = nouveau;
            L->dernier = nouveau;
      }
}