Insérer un nouveau noeud au début de la liste liée

Dans une implémentation simple de la liste liée sur le C, je ne pouvais pas trouver une ligne de fonction nommée insert (). Il faut un caractère et append à la liste liée dans l’ordre alphabétique. La ligne concerne la création d’un nouveau noeud lorsque la liste est vide. Et comme il n’y aura qu’un seul nœud sur la liste, la ligne devrait être comme je l’ai commentée, est-ce que je me trompe?

/****************************************************/ void insert( ListNodePtr *sPtr, char value ){ ListNodePtr newPtr; ListNodePtr previousPtr; ListNodePtr currentPtr; newPtr = malloc( sizeof( ListNode) ); if( newPtr != NULL ){ //is space available newPtr->data = value; //place value in node newPtr->nextPtr = NULL; //node does not link to another node previousPtr = NULL; currentPtr = *sPtr; //indirection to startPtr while( currentPtr != NULL && value > currentPtr->data ){ previousPtr = currentPtr; //walk to ... currentPtr = currentPtr->nextPtr; //... next node } //insert new node at the beginning of the list if( previousPtr == NULL ){ newPtr->nextPtr = *sPtr; /////////////////////////////////////////////// newPtr->nextPtr = NULL ??? *sPtr = newPtr; } else{ //insert new node between previousPtr and currentPtr previousPtr->nextPtr = newPtr; newPtr->nextPtr = currentPtr; } } else printf( "%c not inserted. No memory available.\n", value); }//end-of insert /*******************************************************/ 

les instructions typedef dans main () sont;

 typedef struct listNode ListNode; typedef ListNode* ListNodePtr; 

et la fonction insert () est appelée dans main () comme ceci;

 insert( &startPtr, item); 

initialisation de startPointer dans main ();

 ListNodePtr startPtr = NULL; 

Je pense que vous avez oublié un cas. La ligne que vous avez marquée sera appelée si

  • la liste est vide
  • le caractère est plus petit que tous les autres caractères de la liste et doit être inséré au début de la liste

Pour comprendre le second cas, jetez un œil au code avant:

 while( currentPtr != NULL && value > currentPtr->data ){ previousPtr = currentPtr; //walk to ... currentPtr = currentPtr->nextPtr; //... next node } 

La value > currentPtr->data condition value > currentPtr->data est vraie dans le second cas, vous arriverez donc à la ligne avec previousPtr == NULL et *sPtr != NULL (contenant sa valeur initiale, le pointeur sur le premier noeud de la liste).

Dans le premier cas, *sPtr vaut bien NULL , dans le second cas, vous *sPtr manière incorrecte la liste entière lorsque vous utilisiez NULL et vous retrouveriez avec un seul caractère dans la liste et une fuite de mémoire.

Vous passez un * sPtr à la fonction. Si * sPtr pointe sur un nœud dans une liste non vide, vous perdrez votre référence à la liste si vous utilisez NULL au lieu de * sPtr. Si * sPtr est NULL, le comportement est le même.

Vous suggérez:

 if( previousPtr == NULL ){ newPtr->nextPtr = NULL; *sPtr = newPtr; } 

mais si * sPtr = Node1 et la liste est:

 Node1->Node2->Node3 

si vous voulez insérer avant Node1 et que vous utilisez votre implémentation

vous allez faire pointer votre newPtr-> vers NULL puis définir votre * sPtr = newPtr et perdre votre liste d’origine

l’autre implémentation ajoute votre nouveau noeud à l’ancienne liste.