Linked list traversal skips first element

Question

I have a C program to insert elements at the beginning of a linked list but when I try to print the elements it always skips the first element. Can someone please point out what I am doing wrong in my program.

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


void PrintElements();
void InsertElement(int x);

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

struct node* HEAD;
struct node* temp;
struct node* temp1;


void PrintElements()
{
    temp1=HEAD;
    while(temp1->next!=NULL)
    {
        printf("\n\r Data %d\n\r",temp1->data);
        printf("\n\r Address %x\n\r",temp1->next);
        temp1=temp1->next;
    }
}

void InsertElement(int x)
{
    struct node* temp=(struct node*)malloc(sizeof(struct node));
    temp->data=x;
    temp->next=HEAD;
    HEAD=temp;

}

int main()
{

    int i, x;
    int n;   //n stores the number of elements to be added to the linked list
    HEAD=NULL; //Assigning HEAD to null when there are no elements in the list
    printf("Enter the number of elements\n");
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        printf("\n\rEnter the number");
        scanf("%d",&x);
        InsertElement(x);
        PrintElements();
    }

    return 0;
}

When I changed the following line

while(temp1->next!=NULL)

to

while(temp1!=NULL)

the program works correctly but I am still not able to understand why.

Answer 1

The problem that you describe can be fixed by changing the controlling expression in your PrintElements() function to temp1 != NULL. This way, if temp1 points to a node, the data and next fields are printed, and the loop continues until there are no more nodes. When iterating over a linked list, it usually seems to confuse things when you look at the next node to decide what you will do with the current node. But there are other problems with this code.

First, it would be much better to declare the struct pointers in main() and pass them to the functions, instead of declaring them as global variables. You should check the return values of the functions that you call whenever possible. You should check scanf() to make sure that the input is as expected; this also provides a way to control the input loop, removing the need for the user to explicitly enter a count before inputting data. You should also check the value returned by calls to malloc() to catch allocation errors. Such an allocation error in your code would lead to undefined behavior when temp is dereferenced in the very next line.

You should free all memory allocations, one free() for each call to malloc(). When you print the address of the next node in the list in the function PrintElements(), you invoke undefined behavior. To print the value of a pointer, you should use the %p format specifier, and you must cast the pointer to (void *). Finally, there is no need to #include <malloc.h>; stdlib.h takes care of what you need.

Here is a modified version of your code that implements the suggested changes. Note that in the event of an allocation error, a message is printed to stderr, and the program exits. The call to malloc() has been simplified: there is no reason to cast the result of malloc() in C, and it is better to use the name of the pointer to which you are assigning the memory in place of an explicit type in the argument given to malloc(). The new_node is returned to the calling function, where the pointer to the head of the list is reassigned to point to the new_node.

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

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

void print_elements(struct node *start);
struct node * insert_element(int x, struct node *head);


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

    /* Read data into linked list */
    printf("Enter the first integer (q to quit): ");
    while (scanf("%d", &x) == 1) {
        head = insert_element(x, head);
        print_elements(head);
        printf("Enter another integer (q to quit): ");
    }

    /* Free allocated memory */
    while (head) {
        curr = head;
        head = curr->next;
        free(curr);
    }

    return 0;
}

void print_elements(struct node *curr)
{
    while(curr) {
        printf("   Data: %d\n",curr->data);
        printf("Address: %p\n\n",(void *) curr->next);
        curr = curr->next;
    }
}

struct node * insert_element(int x, struct node *head)
{
    struct node *new_node = malloc(sizeof(*new_node));

    if (new_node == NULL) {
        fprintf(stderr, "Allocation error in function insert_element()\n");
        exit(EXIT_FAILURE);
    }

    new_node->data = x;
    new_node->next = head;

    return new_node;
}

Answer 2

while(temp1->next!=NULL)

Change this to

while(temp1 != NULL)

And it should work fine.

Reason: I think it does not prints the first element you input.

Example: Input: 1 2 3

Linked list formed as : 3 -> 2 -> 1 -> NULL Notation used: Every number is the data, and the arrow shows the pointer next.

Then when you start the loop, For each iteration:

• temp1 points to address of 3

• temp1 -> next != NULL (true as temp1 -> next points to address of 2)

• Prints 3 and temp1 now points to address of 2

• temp1 -> next != NULL (true as temp1 -> next points to address of 1)

• Prints 2 and temp1 now points to address of 1

• temp1 -> next != NULL This becomes False as temp1 points to address of 1 and temp1 -> next is NULL.

So we never go inside the loop to print 1.

So the correct thing is to use temp1 != NULL as this will eliminate the above bug.