Les listes doublement chaînées en C

Pour obtenir la structure de base d'une liste doublement chaînée, il suffit d'ajouter un pointeur sur l'élément précedent à la structure item_s vue dans l'article précédent. Comme la sentinelle est devenue inutile, il n'est plus nécessaire de créer une structure d'encapsidation de la liste.

stypedef struct dll
{
   struct dll *prev;
   struct dll *next;
   void *data;
} dll_s;

L'initialisation de la liste est devenue inutile, cependant la fonction est conservée pour être sûr que le pointeur est mis à NULL :

dll_s *dll_new (void)
{
   return (NULL);
}

Le principe est identique à celui des listes simplement chaînée, il ne faut pas oublier de mettre à jour le pointeur sur l'élément précédent.

1. Voici l'état de la liste avant l'appel de la fonction
2. Le pointeur p_p représente l'argument de la fonction, c'est donc après lui qu'il faut insérer un maillon
3. p_n pointe sur l'élément qui suit
4. Création d'un nouvel élément pointé par p_l
5. On commence par faire pointer le nouvel élément sur le maillon qui suit p_p (donc p_n) sans oublier de faire pointer ce dernier vers notre nouvel élément puisque maintenant la liste va dans les deux sens
6. Puis l'on modifie p_p pour que l'élément qui le suit soit celui nouvellement créé et réciproquement
7. Etat de la liste après l'appel de la fonction

Le code est légèrement différent du fait de l'absence de la structure d'encapsulation.

void dll_insert (dll_s ** pp_dll, void *data)
{
   if (pp_dll != NULL)
   {
/* (2) */
      dll_s *p_p = *pp_dll;
      dll_s *p_l = NULL;
      dll_s *p_n = NULL;

/* (3) */
      if (p_p != NULL)
         p_n = p_p->next;
/* (4) */
      p_l = malloc (sizeof (*p_l));
      if (p_l != NULL)
      {
         p_l->data = data;
/* (5) */
         p_l->next = p_n;
         if (p_n != NULL)
            p_n->prev = p_l;
/* (6) */
         p_l->prev = p_p;
         if (p_p != NULL)
            p_p->next = p_l;
         *pp_dll = p_l;
      }
      else
      {
         fprintf (stderr, "Memoire insuffisante\n");
         exit (EXIT_FAILURE);
      }
   }
}

Voici la fonction qui va subir le plus de modifications, elle va ainsi pouvoir supprimer l'élément passer en paramètre.

1. Voici l'état de la liste avant l'appel de la fonction
2. Le pointeur p_l représente l'argument de la fonction et donc l'élément à supprimer
3. Sauvegarde de l'élément précédent celui à supprimer grâce au pointeur p_p
4. Sauvegarde de l'élément suivant celui à supprimer grâce au pointeur p_n
5. Modification des pointeurs de telle manière que le maillon à supprimer ne soit plus référencé
6. Libération de la mémoire
7. État de la liste après l'appel de la fonction

void dll_remove (dll_s ** pp_dll)
{
   if (pp_dll != NULL && *pp_dll != NULL)
   {
/* (2) */
      dll_s *p_l = *pp_dll;
/* (3) */
      dll_s *p_p = p_l->prev;
/* (4) */
      dll_s *p_n = p_l->next;

/* (5) */
      if (p_p != NULL)
         p_p->next = p_n;
      if (p_n != NULL)
         p_n->prev = p_p;
/* (6) */
      free (p_l);
      p_l = NULL;
      if (p_n != NULL)
         *pp_dll = p_n;
      else
         *pp_dll = p_p;
   }
}

Cette fonction se contente de déplacer le pointeur sur l'élément qui précédent, en faisant tout de même attention à la valeur de pp_dll :

void dll_prev (dll_s ** pp_dll)
{
   if (pp_dll != NULL && *pp_dll != NULL)
      *pp_dll = (*pp_dll)->prev;
}

Avec l'apparition du pointeur sur l'élément précèdent, la sentinelle qui repérait le premier élément de la liste n'existe plus, ce qui a permis de simplifier certaines fonctions, cependant il faut retrouver ce premier élément de la même manière que le dernier élément.

void dll_first (dll_s ** pp_dll)
{
   if (pp_dll != NULL && *pp_dll != NULL)
   {
      while ((*pp_dll)->prev != NULL)
         dll_prev (pp_dll);
   }
}

Comme la fonction de suppression des éléments a été modifiée, il est logique qu'il en soit de même pour la destruction de la liste.

void dll_delete (dll_s ** pp_dll)
{
   if (pp_dll != NULL && *pp_dll != NULL)
   {
      dll_first (pp_dll);
      while (*pp_dll != NULL)
         dll_remove (pp_dll);
   }
}