Insert new node at the beginning of Linked-List

Question

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 alphabetical 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;

Solution 1

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.

Solution 2

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.