====== Implémentation d'une liste chaînée en C ======

Une liste chaînée est une collection d'items formées par des maillons liés les uns aux autres. Chaque maillon correspond à un emplacement mémoire contenant un item et un lien vers le maillon suivant. Comme le type de l'item est connu et que le lien est une adresse vers la case mémoire du maillon suivant, l'occupation mémoire du maillon est connue et peut être réservée.

=== Pointeurs ===

On a besoin de pointer sur un maillon, il s'agit donc d'une adresse.

Le type défini pour les maillons étant ''%%Maillon%%'', l'adresse d'un tel élément sera en C de type ''%%Maillon *%%''. L'étoile sert à indiquer que l'on veut un [[nsi:langages:c:pointeurs|pointeur]] sur l'élément.

=== Type Maillon ===

On définit le type ''%%Maillon%%'' contenant un entier et un pointeur vers le maillon suivant. Pour cela on utilise une [[nsi:langages:c:structures|structure]]:

<Code:c linenums:6>
struct Maillon;
typedef struct Maillon
{
  struct Maillon *next;
  int data; /*!< Contenu de l'élément */
} Maillon;
</Code>

La création d'un tel maillon nécessite de demander une allocation en mémoire. Il faut utiliser [[nsi:langages:c:malloc|malloc]]. Il se peut que l'allocation échoue, on prévoit donc la levée d'une erreur.

<Code:c linenums:108>
  Maillon *new_maillon = NULL;
  new_maillon = malloc(Maillon);
  if (new_maillon == NULL)
  {
    fprintf(stderr, "INSERER -> erreur malloc.\n");
    exit(EXIT_FAILURE);
  }
</Code>

Et il faut penser à libérer la mémoire des maillons supprimés :
<Code:c linenums:171>
  free(m_to_delete);
</Code>

=== Code complet ===

<Code:c linenums>
// Exemple d'une liste d'entiers

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

struct Maillon;
typedef struct Maillon
{
  struct Maillon *next;
  int data; /*!< Contenu de l'élément */
} Maillon;

struct List;
typedef struct List
{
  struct Maillon *head; /*!< premier item de la liste */
} List;

List *CREER_LISTE_VIDE()
{
  List *L = NULL;
  L = malloc(sizeof(*pl));
  if (L == NULL)
  {
    fprintf(stderr, "CREER_LISTE_VIDE -> erreur malloc.\n");
    exit(EXIT_FAILURE);
  }
  L->head = NULL;
  return L;
}

int LONGUEUR(List *L)
{
  if (L == NULL)
  {
    fprintf(stderr, "LONGUEUR -> NULL List\n");
    exit(EXIT_FAILURE);
  }
  int c = 0;
  Maillon *m = L->head;
  while(m != NULL)
  {
    c++;
    m = m->next;
  }
  return c;
}

int LIRE(List *L, int i)
{
  // il faudrait vérifier i > 0
  if (L == NULL)
  {
    fprintf(stderr, "LIRE -> NULL List\n");
    exit(EXIT_FAILURE);
  }
  if (i < 0)
  {
    fprintf(stderr, "LIRE -> indice doit être positif\n");
    exit(EXIT_FAILURE);
  }
  Maillon *m = L->head
  while ((i > 0) && (m != NULL))
  {
    i--;
    m = m->next;
  }
  if (m == NULL)
  {
    fprintf(stderr, "LIRE -> indice trop grand.\n");
    exit(EXIT_FAILURE);
  }
  return m->data;
}

int RECHERCHER(List *L, int e)
{
  if (L == NULL)
  {
    fprintf(stderr, "RECHERCHER -> NULL List\n");
    exit(EXIT_FAILURE);
  }
  Maillon *m = L->head;
  int i = 0;
  while(m != NULL)
  {
    if (m->data == e)
    {
      return i;
    }
    i++;
    m = m->next;
  }
  return -1;
}

void INSERER(List *L, int e, int i):
  if (L == NULL)
  {
    fprintf(stderr, "INSERER -> NULL List\n");
    exit(EXIT_FAILURE);
  }
  if (i < 0)
  {
    fprintf(stderr, "INSERER -> indice doit être positif\n");
    exit(EXIT_FAILURE);
  }
  Maillon *new_maillon = NULL;
  new_maillon = malloc(Maillon);
  if (new_maillon == NULL)
  {
    fprintf(stderr, "INSERER -> erreur malloc.\n");
    exit(EXIT_FAILURE);
  }
  new_maillon->data = e;
  if (i==0) {
    new_maillon->next = L->head;
    L->head = new_maillon;
    return;
  }
  Maillon *m = L->head;
  while ((m != NULL) && (i > 1))
  {
    i--;
    m = m->next;
  }
  if (m == NULL)
  {
    fprintf(stderr, "INSERER -> indice trop grand.\n");
    free(new_maillon);
    exit(EXIT_FAILURE);
  }
  new_maillon->next = m->next;
  m->next = new_maillon;
}

void SUPPRIMER(List *L, int i):
  if (L == NULL)
  {
    fprintf(stderr, "SUPPRIMER -> NULL List\n");
    exit(EXIT_FAILURE);
  }
  if (L->head == NULL)
  {
    fprintf(stderr, "SUPPRIMER -> empty List\n");
    exit(EXIT_FAILURE);
  }
  if (i < 0)
  {
    fprintf(stderr, "SUPPRIMER -> indice doit être positif\n");
    exit(EXIT_FAILURE);
  }
  Maillon *m = L->head;
  if (i==0) {
    L->head = m->next;
    free(m);
    return;
  }
  while ((m != NULL) && (i > 1))
  {
    i--;
    m = m->next;
  }
  if ((m == NULL)||(m->next == NULL))
  {
    fprintf(stderr, "INSERER -> indice trop grand.\n");
    exit(EXIT_FAILURE);
  }
  Maillon *m_to_delete = m->next;
  m->next = m_to_delete->next;
  free(m_to_delete);
 
void MODIFIER(List *L, int e, int i):
  if (L == NULL)
  {
    fprintf(stderr, "MODIFIER -> NULL List\n");
    exit(EXIT_FAILURE);
  }
  if (i < 0)
  {
    fprintf(stderr, "MODIFIER -> indice doit être positif\n");
    exit(EXIT_FAILURE);
  }
  Maillon *m = L->head;
  while ((m != NULL) && (i > 0))
  {
    i--;
    m = m->next;
  }
  if (m == NULL)
  {
    fprintf(stderr, "MODIFIER -> indice trop grand.\n");
    exit(EXIT_FAILURE);
  }
  m->data = e;
}

// Exemple de fonction principale
int main()
{
  Liste *L = CREER_LISTE_VIDE();
  INSERER(L, 45, 0);
  INSERER(L, 17, 0);
  INSERER(L, 19, 0);
  INSERER(L, 50, 1);
  int x = LIRE(L, 1);
  printf("%d\n", x);
  SUPPRIMER(L, 1);
  x = LIRE(L,0);
  printf("%d\n", x);
  int l = LONGUEUR(L);
  printf("%d\n", l);
  return 0;
}
</Code>