C'est peut-être un peu bourrin de commencer directement par une liste doublement chainée (même si c'est ce que j'avais fait en cours de système).
Enfin, l'avantage, c'est qu'on peut faire n'importe quelle manipulation à peu près n'importe où, une fois que lss fonctions sont définies.
Voici un petit exemple, avec des
typedef en prime parce que je trouve que ça simpifie:
typedef struct elementDbl ST_ELEMENTDBL, *PT_ELEMENTDBL;
struct elementDbl {
PT_ELEMENTDBL pt_prev;
PT_ELEMENTDBL pt_next;
float fMyData; //Histoire de mettre quelque chose dans la liste
};
//Pour créer un nouvel élément
PT_ELEMENTDBL NewElement(float fData) {
PT_ELEMENTDBL pt_returnVal;
//Attention, on alloue bien la taille de la structure et non du pointeur
pt_returnVal = (PT_ELEMENTDBL)malloc(sizeof(ST_ELEMENTDBL));
if(pt_returnVal) {
pt_returnVal->pt_prev = NULL;
pt_returnVal->pt_next = NULL;
pt_returnVal->fMyData = fData;
}
return pt_returnVal;
}
//Pour insérer un élément à gauche d'un élément existant
//(Retourne pt_newElement si OK, NULL si erreur (par exemple, pt_newElement non-orphelin)
PT_ELEMENTDBL InsertLeft(PT_ELEMENTDBL pt_list, PT_ELEMENTDBL pt_newElement) {
//Erreur si pt_newElement n'est pas orphelin
if(pt_newElement==NULL || pt_newElement->pt_prev!=NULL || pt_newElement->pt_next!=NULL) {
return NULL;
}
pt_newElement->pt_prev = pt_list;
pt_newElement->pt_next = pt_list->pt_next;
pt_list->pt_next = pt_newElement;
if(pt_newElement->pt_next) {
pt_newElement->pt_next->pt_prev = pt_newElement;
}
return pt_newElement;
}
//Pour insérer un élément à droite d'un élément existant
PT_ELEMENTDBL InsertRight(PT_ELEMENTDBL pt_list, PT_ELEMENTDBL pt_newElement) {
//Erreur si pt_newElement n'est pas orphelin
if(pt_newElement==NULL || pt_newElement->pt_prev!=NULL || pt_newElement->pt_next!=NULL) {
return NULL;
}
pt_newElement->pt_prev = pt_list->pt_prev;
pt_newElement->pt_next = pt_list;
pt_list->pt_prev = pt_newElement;
if(pt_newElement->pt_prev) {
pt_newElement->pt_prev->pt_next = pt_newElement;
}
return pt_newElement;
}
//Petites fonctions pour obtenir la tête et la queue d'une liste
PT_ELEMENTDBL GetFirstElement(PT_ELEMENTDBL pt_list) {
if(pt_list==NULL) {
return NULL;
}
while(pt_list->pt_prev != NULL) {
pt_list = pt_list->pt_prev;
}
return pt_list;
}
PT_ELEMENTDBL GetLastElement(PT_ELEMENTDBL pt_list) {
if(pt_list==NULL) {
return NULL;
}
while(pt_list->pt_next != NULL) {
pt_list = pt_list->pt_next;
}
return pt_list;
}
A ce moment-là, tu n'as même pas besoin de retenir le pointeur Nouveau, car tu peux directement ajouter à la liste avec
InsertRight(pt_dernierElement, NewElement(fMesDonnees));
pt_dernierElement = GetLastElement(pt_dernierElement);
Tu vois, en gérant bien les listes chaînées, tu n'as besoin que d'un seul pointeur.
En fait, avec ces fonctions de base, tu peux à peu près tout faire au niveau élément. Pour concaténer deux listes, c'est pas bien compliqué non plus (il faut toucher aux pointeurs de la tête d'une liste et la queue de l'autre).
PS: mettre un nom spécial aux variables pointeurs, ça aide.