On voit souvent que l'avantage d'une liste doublement chaînée c'est de pouvoir
ajouter un élément neo avant un élément de la liste e. En fait c'est
également possible de le faire avec une liste simplement chaînée, même si on ne
dispose pas d'un pointeur sur l'élément qui précède.
La théorie c'est bien
Pour que ce soit viable, on a besoin d'une fonction "swap" qui échange le contenu de deux éléments de la liste et qui soit raisonnablement rapide en terme de performances.
Si on veut insérer l'élément neo avant l'élément e de la liste, on va
échanger le contenu des deux éléments puis insérer neo après l'élément
e de la liste (opération facile avec une liste simplement chaînée). En dessin
ça donne ça pour avoir les données a avant les données b:
neo[a] ... -> e[b] -> ... // on swap neo[b] ... -> e[a] -> ... // on insère e après neo ... -> e[a] -> neo[b] -> ... // et c'est fini!
La pratique saymieux
Pour la route, un exemple dans le langage de l'amour et du bien.
#include <stdio.h> struct entry { void *data; struct entry *next; }; struct list { struct entry *head; }; void swap_data(struct entry *a, struct entry *b) { void *tmp; tmp = a->data; a->data = b->data; b->data = tmp; } /* insert neo after e */ void insert_after(struct entry *e, struct entry *neo) { neo->next = e->next; e->next = neo; } /* insert neo before e */ void insert_before(struct entry *e, struct entry *neo) { /* swap content of e and neo */ swap_data(e, neo); /* do the insert */ insert_after(e, neo); } int main(int argc, char *argv[]) { struct entry a, b; struct entry *e; struct list l; /* initialize data */ a.data = "foo"; b.data = "bar"; /* set b as head of the list l */ l.head = &b; b.next = NULL; /* do the magic */ insert_before(&b, &a); /* print the list l */ e = l.head; for (e = l.head; e != NULL; e = e->next) (void)printf("%s\n", e->data); return (0); }
