insertAtTail is not adding node in linkedlist

Question

I am a newbie in the data structure. I am creating a linked list program. I have created the program. But don't understand why insertAtTail is not adding the node to linked list.

struct node {
    int data;
    struct node *next;
};

struct node *head=NULL;

int main( void ) {
    insertAtHead(3);
    insertAtHead(4);
    insertAtHead(5);
    insertAtHead(8);
    insertAtTail(2);
    display();

    return 0;
}

void insertAtHead( int data ){
    struct node *newNode;

    newNode = (struct node *)malloc( sizeof(struct node) );
    newNode->data = data;
    newNode->next = NULL;

    if( head == NULL ){
        head = newNode;
    } else {
        newNode->next = head;
        head = newNode;
    }
}

void insertAtTail(int data){
    struct node *newNode, *temp;

    newNode = (struct node *)malloc( sizeof(struct node) );
    newNode->data = data;
    newNode->next = NULL;

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

        temp = newNode;
    }

}

void display(){
    struct node *temp;

    temp = head;
    while ( temp != NULL)
    {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");   
}

Expect the output: 8 -> 5 -> 4 -> 3 -> 2 -> NULL

Actual Output: 8 -> 5 -> 4 -> 3 -> NULL

Answer 1

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

Reassigning temp here will do nothing. Instead, check if temp->next is null and use that:

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

This way, you're still altering head, rather than temp.

Answer 2

Change this:

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

temp = newNode;

to this:

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

since what you want to do is to go the old last node, and after doing do, specify that the next to the old last node, i.e. the new last node is the newNode.

Live demo (Notice how I moved the definitions of your methods before the main method, so that it can compile - alternatively, you could declare the prototypes before main, and still leave the definitions as you have them now).

PS: Do I cast the result of malloc? No.

Answer 3

The variable temp is a local variable of the function that occupies a different memory then the nodes of the list.

After this loop

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

the variable temp is set to NULL. Then in this statement

    temp = newNode;

you are changing the memory occupied by the variable itself. Nodes of the list were not changed.

Change the loop the following way

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

    temp->next = newNode;

Also pay attention two that all functions that are used in main shall be declared before their usage.

For example

void insertAtHead( int data );

//...

int main( void )
{
    //...
}

Also it is not a good idea that the functions deal with a global variable head. You should rewrite the functions such a way that a head to a list would be passed as an argument to the functions.

For example in this case the function insertAtHead can be defined the folloing way

int insertAtHead( struct node **head, int data )
{
    struct node *newNode = malloc( sizeof(struct node) );

    int success = newNode != NULL;

    if ( success )
    {
       newNode->data = data;
       newNode->next = *head;
       *head = newNode;
    }

    return success;
}

As result in one program you can have several lists by declaring locally in main their heads.

Here is a demonstrative program

#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    struct node *next;
};

int insertAtHead( struct node **head, int data )
{
    struct node *newNode = malloc( sizeof(struct node) );

    int success = newNode != NULL;

    if ( success )
    {
       newNode->data = data;
       newNode->next = *head;
       *head = newNode;
    }

    return success;
}

int insertAtTail( struct node **head, int data )
{
    struct node *newNode = malloc( sizeof(struct node) );
    int success = newNode != NULL;

    if ( success )
    {
        newNode->data = data;
        newNode->next = NULL;

        while ( *head != NULL ) head = &( *head )->next;

        *head = newNode;
    }

    return success;
}

void display( struct node *head )
{
    for ( struct node *current = head; current != NULL; current = current->next )
    {
        printf("%d -> ", current->data);
    }

    puts( "NULL" );   
}

int main(void) 
{
    struct node *head = NULL;

    insertAtHead( &head, 3 );
    insertAtHead( &head, 4 );
    insertAtHead( &head, 5 );
    insertAtHead( &head, 8 );
    insertAtTail( &head, 2 );

    display( head );

    return 0;
}

Its output is

8 -> 5 -> 4 -> 3 -> 2 -> NULL