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;

schnaader · Accepted Answer · 2011-03-07T01:12:44.323

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.

score 1 · Answer 2 · answered Mar 07 '11 at 01:14

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.

Insert new node at the beginning of Linked-List

2 Answers2

Linked