Runtime error and wrong anwer Linked list

Question

Here is my solution to the problem in C:

#include<stdio.h>
#include<stdlib.h>
struct node{
    int data;
    struct node*next;
};
struct node* head=NULL;

void insertFront(int data)
{
    struct node*newnode=(struct node*)malloc(sizeof(struct node));
    newnode->data=data;
    newnode->next=NULL;
    newnode->next=head;
    head=newnode;
}
int returnSize(){
    int cnt=0;
    struct node*temp=head;
    while(temp!=NULL)
    {
        cnt++;
        temp=temp->next;
    }
    return cnt;
}
void insertAt(int position,int data)
{
    struct node*newnode=(struct node*)malloc(sizeof(struct node));
    newnode->data=data;
    newnode->next=NULL;
    if(head==NULL&&position>0)//marker1
    {
        head=newnode;
        return;
    }//marker2
    int cnt=returnSize();
    if(position>cnt)
    {
        struct node*var=head;
        while(var->next!=NULL)
        var=var->next;
        var->next=newnode;
        return;
    }
    int i;
    struct node*temp=head;
    if(position==0)
    {
    newnode->next=head;
    head=newnode;
    return;
    }
    else
    {
        for(i=0;i<position-1;i++)
        {
            temp=temp->next;
        }
        newnode->next=temp->next;
        temp->next=newnode;

    }   
}
void deleteAt(int position)
{
    if(head==NULL)
    {
        printf("empty");
        return;
    }
    int i,cnt=0;
    struct node*dummy=head;
        while(dummy->next!=NULL)
        {
            cnt++;
            dummy=dummy->next;
        }
        if(position>cnt)
        return;
    if(position==0)
    {
        struct node*temp=head;
        head=head->next;
        free(temp);
    }
    else
    {
        struct node*temp=head;
        for(i=0;i<position-1;i++)
        {
            if(temp!=NULL)
            temp=temp->next;
            else
            return;
        }
        temp->next=temp->next->next;
    }
}
void deleteFront()
{
    if(head==NULL)
    {
        printf("empty");
        return;
    }
    struct node*temp=head;
    head=head->next;
    free(temp);
    if(head==NULL)
    {
        printf("empty");
        return;
    }
}
void print()
{
    struct node*temp=head;
    while(temp!=NULL)
    {
        printf("%d ",temp->data);
        temp=temp->next;
    }
    printf("\n");
}
int main()
{ 
char a;
do{

    char tmp;
    int b,c;
    scanf("%c",&a);
    if(a=='r')
    {
        deleteFront();

        print();
    }
    else if(a=='i')
    {
        scanf("%d",&b);
        scanf("%d",&c);
        insertAt(b,c);  
        print();
    }
    else if(a=='f')
    {
        scanf("%d",&b);
        insertFront(b);

        print();
    }
    else if(a=='d')
    {
        scanf("%d",&b);
        deleteAt(b);

        print();
    }
    scanf("%c",&tmp);
}while(a!='q');
    return 0;
}

If I remove the lines I marked as marker in the form of comment lines in the function insertAt(), I get a segfault. When I use them I get a wrong answer. I tested for many cases and I couldn't figure out where I was wrong.

Could someone help me out?

Why do you want to remove the lines? One suggestion would be to call insertFront when the condition (head==NULL and position > 0) is satisfied. — envy_intelligence, Jun 07 '15 at 08:32
My question was why should those lines be removed? Also put up the test case for which you are receiving wrong results. — envy_intelligence, Jun 07 '15 at 08:38
Initially i though the condition would be checked by position>cnt condition. but thats not true. And i don't know the test cases for which the program gets failing. — user154, Jun 07 '15 at 08:46
Err. I was missing a "\n" which got me a ton of unsuccessful submissions. It was accepted now. Thanks a lot @envy_intelligence for your time :) — user154, Jun 07 '15 at 09:24

score 0 · Answer 1 · edited May 23 '17 at 12:08

Firstly, I advise that you take a look at this question: Do I cast the result of malloc?... Suffice to say, the best pattern to follow as far as maintenance goes looks more like this:

foo *bar = malloc(sizeof *bar);
if (bar == NULL) {
    /* handle allocation error */
}

This way, if you ever have to change the type of bar, it's less likely that you'll forget to replace a typename somewhere; you'll be less likely to create new bugs during maintenance if you use this pattern.

newnode->next=NULL; /* <--- THIS IS UNNECESSARY */
newnode->next=head; /* <--- because this ends up being the value immediately after */

There are potential null pointer dereferences anywhere you've used malloc and neglected to check its return value. See the pattern above.

There's a potential null pointer dereference in insertAt, here: temp=temp->next; and here: newnode->next=temp->next;. The code between the markers guards your program from this null pointer reference when head is NULL... but that's not the only scenario where this null pointer dereference may be triggered.

There's a potential null pointer dereference in deleteAt, here: temp->next=temp->next->next;

You really should be checking the return value of scanf every time you use it.

For future reference, please fix your tabulation key so that we may help you more easily... It wouldn't surprise me if this is the reason only I have answered your question so far.

Runtime error and wrong anwer Linked list

1 Answers1