Inserting at the end of a linked list

Question

I wrote a function for inserting a node at the end of a linked list. When I run the program, and when I call this function, the program just stops working.

Here is the function:

void insert(node **head, int x) {
    node *new = malloc(sizeof(node));
    new->data = x;
    new->next = NULL;

    node *temp = *head;

    while (temp != NULL) {
        temp = temp->next;
    }
    temp->next = new;
}

Can anyone tell where did it go wrong?

Answer 1

1. When while loop terminates temp is NULL. So temp -> next will generate Segmentation Fault.

   Instead of while(temp!=NULL) you should use while(temp->next!=NULL).

2. What if head is NULL? (Empty linked list)
   For that check whether head is NULL or not.

3. Also what if malloc failed?

So the solution will be:

node *insert(node **head, int x)
{
    node *new = (node *) malloc(sizeof(node));        
    if (new == NULL) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    new->data = x;
    new->next = NULL;

    node *temp = *head;
    if (temp == NULL) {
        *head = new;
    }
    else {
        while (temp->next != NULL)
            temp = temp->next;
        temp->next = new;
    }

    return new;
}

Answer 2

There are two problems with your code:

• The temp pointer is pushed to the end of the list until it becomes NULL, by then it is too late to store the new pointer to its next member, and attempting that invokes undefined behavior (Segmentation fault on your system).
• If the list is empty, you cannot store the new item this way even if you stopped the loop when temp->next == NULL.

It is also desirable to avoid using C++ keywords to name variables in C code as it would make it more difficult to migrate the code to C++, should the need arise to do so.

Also it would be more correct to test if malloc failed and return the pointer to the new node or NULL on failure.

Here is a corrected version:

node *insert(node **head, int x) {
    node *new_node = malloc(sizeof(node));
    if (new_node != NULL) {
        new_node->data = x;
        new_node->next = NULL;

        node *temp = *head;
        if (temp == NULL) {
            *head = new_node;
        } else {
            while (temp->next != NULL) {
                temp = temp->next;
            }
            temp->next = new_node;
        }
    }
    return new_node;
}

You can also use a pointer to pointer to iterate over the list: it is slightly more sophisticated but shorter as you have only one test to find the location to store the new pointer:

node *insert(node **head, int x) {
    node *new_node = malloc(sizeof(node));
    if (new_node != NULL) {
        new_node->data = x;
        new_node->next = NULL;

        node **np = head;
        while (*np) {
            np = &(*np)->next;
        }
        *np = new_node;
    }
    return new_node;
}

Answer 3

Use node** to iterate. So it doesn't matter, if the list is empty or not. Iterate until you find a node whose next is NULL. You can allocate the memory right on target.

void insert( node **head, int x){

    node **ptr_new = head;
    while( *ptr_new != NULL ){
        ptr_new = &((*ptr_new)->next);
    }

    // now temp refers either to head or to next of the last node.
    *ptr_new = malloc( sizeof(node) );
    if ( *ptr_new != NULL )
    {
        (*ptr_new)->next = NULL;
        (*ptr_new)->data = x;
    }
}

In contrast to your original code you have a pointer to pointer in which the address of the new node is stored. In your original you iterated while temp was not NULL.

while (temp != NULL) {
    temp = temp->next;
}

After this while loop temp==NULL, because this is the termination condition of your loop. Because of that your program stops working here temp->next = new;