Linked List Implementation in C - Segmentation fault error

Question

I am struggling to find the error in the following implementation of linked list.I am getting segmentation fault error when I append or add at beginning

Please Help me where I am doing wrong

#include

#include<stdlib.h>

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

void append(struct node *p,int num)
{
    struct node *temp,*q;
    q=p;
    temp=(struct node*)malloc(sizeof(struct node));
    temp->data=num;
    temp->link=NULL;
    if(p==NULL)
        p=temp;
    else
    {
        while(q->link!=NULL)
            q=q->link;

        q->link=temp;
    }
}



int main()
{
    int i,choice,num,pos;
    struct node p;
    printf("Enter your choice\n");
    printf("1-Append\n2-Add At Beg\n3-Add after\n4-Delete\n5-Exit");
    scanf("%d",&choice);
    while(choice!=5)
    {
        switch(choice)
        {
            case 1:printf("Enter the number\n");
                    scanf("%d",&num);
                    append(&p,num);
                    break;


        }
        printf("1-Append\n2-Add At Beg\n3-Add after\n4-Delete\n5-Exit");
        scanf("%d",&choice);
    }
}

Too much code. Remove unnecessary parts.

Konstantin
– Konstantin

2013-09-21 12:38:36 +00:00
Commented Sep 21, 2013 at 12:38 — Konstantin
– Konstantin, Commented Sep 21, 2013 at 12:38
Learn how to write a SSCCE

Aubin
– Aubin

2013-09-21 12:45:41 +00:00
Commented Sep 21, 2013 at 12:45 — Aubin
– Aubin, Commented Sep 21, 2013 at 12:45
Removed unnecessary code

InsaneCoder
– InsaneCoder

2013-09-21 12:53:35 +00:00
Commented Sep 21, 2013 at 12:53 — InsaneCoder
– InsaneCoder, Commented Sep 21, 2013 at 12:53

vaibhav · Accepted Answer · 2013-09-21 13:03:43Z

3

do

struct node*p=NULL;

call append like this-

append(&p,num);

We do this as we want to keep the pointer to the first node of our link list with us. By doing append(p,num), a copy of the pointer goes into our method and the changes to p are lost when that method returns.

and write the append routine as-

void append(struct node **p,int num)
{
   struct node *temp,*q;
   q=*p;
   temp=(struct node*)malloc(sizeof(struct node));
   temp->data=num;
   temp->link=NULL;
   if(*p==NULL)
   {
        *p=temp;
        printf("here");
    }
  else
   {
       while(q->link!=NULL)
        q=q->link;

       q->link=temp;
   }
}

do similarly for add routine.

answered Sep 21, 2013 at 13:03

vaibhav

1178 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

wildplasser Over a year ago

You can eliminate the special case in your append() function.

ebo · Accepted Answer · 2013-09-21 14:28:59Z

1

Final edit: User vaibhav caught it: struct node *p is uninitialized and may not be NULL even if the list is empty.

Just for general enjoyment, the clang static analyser seems to get it:

clang -Wall --analyze lists.c
lists.c:13:5: warning: Assigned value is garbage or undefined
  q = *p;
    ^ ~~
1 warning generated.

void append(struct node *p,int num);

While the algorithms themselves seem fine, there is a problem in the way you handle the p-argument. You pass the pointer p by value, which means changes to *p will change the allocated memory, but changes to p itself will not be propagated to the calling context.

The correct method to handle this case would be:

void append(struct node **p, int num) { *p = temp; }

#include<stdlib.h>

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

void append(struct node **p,int num)
{
  struct node *temp,*q;
  q = *p;
  temp = (struct node*)malloc(sizeof(struct node));
  temp->data = num;
  temp->link = NULL;
  if(*p == NULL)
    *p = temp;
  else
    {
      while(q->link != NULL)
        q = q->link;

      q->link = temp;
    }
}

int main()
{
  struct node *p;

  append(&p, 1);
  append(&p, 2);
  append(&p, 3);
}

edited Sep 21, 2013 at 14:28

answered Sep 21, 2013 at 12:44

ebo

9,2853 gold badges33 silver badges37 bronze badges

3 Comments

InsaneCoder Over a year ago

What if I want to use the signature void append(struct node *p,int num); only. What changes should I make I make in main().I tried struct node p; and then passing address as addatbeg(&p,num) but even that doesn't help.

ebo Over a year ago

The problem with append is the initialisation of the list. You can disallow NULL for append and use a special initializer method. Or you can use a list type which holds a pointer to the first list element and can be constructed without a value.

wildplasser Over a year ago

You can eliminate the special case in your append() function.

zubergu · Accepted Answer · 2013-09-21 13:02:06Z

0

In this line:

struct node*p;

it should be

struct node p;

you're creating pointer to node. But don't initialize it later, so no node is created and it points to random location. Then you pass that as argument to your functions.
When you are dereferencig this pointer in your functions p-> you have a segmentation fault.

In your main function you should have declaration of 'node', not pointer to node, and then pass node's address to function with & operator.

So your function declaration void addatbeg(struct node *p,int num); is fine but it should be called (after you declare node p):

addatbeg(&p,some_number);

Also, every function that makes use of p should be changed to treat p like a structure, not like pointer to structure.

What you did here is confused some information on linked lists.
Usually head of a singly linked list declared as a pointer to node. When I implemented sll myself I did that, too. Then you pass that pointer by reference to functions manipulating on linked list and it works fine.
On the other hand you got doubly linked lists, and there it is more convinient to treat head of doubly linked list as just another node, but without value.
You are trying to mix those ideas together without understanding ideas behind them.
I gave you bunch of tips on how to make it work, but fixing it would mean that I have to rewrite your whole code.

And that's not the point since you should learn it yourself.

edited Sep 21, 2013 at 13:02

answered Sep 21, 2013 at 12:40

zubergu

3,7254 gold badges28 silver badges39 bronze badges

6 Comments

David W Over a year ago

You need to make the corresponding changes to the other routines - display, count, etc. or the same thing will happen there as well.

ebo Over a year ago

I don't think it is a good idea to have one list element on the stack and the rest on the heap. If you add some elements at the beginning and some at the hand, how would you know which element not to free? Additionally this element gets lost when the function it is defined in ends.

zubergu Over a year ago

@ebo And I don't think you get answer. I gave some tips on how given code could work. Not the best idea on implementing singly linked list. That's why I elaborated so much about reading how to do it correctly.

ebo Over a year ago

IMHO using a stack value here is even worse!

zubergu Over a year ago

@ebo worse than what? I don't see any alternatives. And what's the reason keeping me from putting head of a sll on the stack, when it's in main? One less thing to free.

|

Collectives™ on Stack Overflow

Linked List Implementation in C - Segmentation fault error

3 Answers 3

1 Comment

3 Comments

6 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

3 Comments

6 Comments

Your Answer

Sign up or log in

Post as a guest

Related