In a simple Linked List implementation on C, I couldn’t figure out a line of function named insert(). It takes a char and add to the linked list in alphabe开发者_C百科tical order. The line is about creating a new node when the list is empty. And since there will be only one node on the list, the line should be like I’ve commented, am I wrong?
/****************************************************/
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
/*******************************************************/
the typedef instructions in main() are;
typedef struct listNode ListNode;
typedef ListNode* ListNodePtr;
and the function insert() is called in main() like this;
insert( &startPtr, item);
initialization of startPointer in main();
ListNodePtr startPtr = NULL;
I think you forgot a case. The line you marked will be called if
- the list is empty
- the character is smaller than all other characters in the list and has to be inserted at the beginning of the list
To understand the second case, have a look at the code before:
while( currentPtr != NULL && value > currentPtr->data ){
previousPtr = currentPtr; //walk to ...
currentPtr = currentPtr->nextPtr; //... next node
}
The condition value > currentPtr->data
is true in the second case, so you will arrive at the line with previousPtr == NULL
and *sPtr != NULL
(containing its initial value, the pointer to the first node of the list).
In the first case, *sPtr
is NULL
indeed, in the second case, you would incorrectly throw away the whole list when using NULL
and end up with only one character in the list and a memory leak.
You are passing in a *sPtr to the function. If *sPtr points to a Node in a non-empty list, you will lose your reference to the list if you use NULL instead of *sPtr. If *sPtr is NULL the behavior is the same.
You are suggesting:
if( previousPtr == NULL ){
newPtr->nextPtr = NULL;
*sPtr = newPtr;
}
but if *sPtr = Node1 and the list is:
Node1->Node2->Node3
if you want to insert before Node1 and you use your implementation
you will make your newPtr-> point to NULL and then set your *sPtr = newPtr and lose your original list
the other implementation prepends your new node to the old list.
精彩评论