Segmentation fault using doubly linked list in C

Question

I've written an implementation of a doubly linked list with a .h prototype here and everything runs fine until I start entering values in the terminal. I get a segmentation fault after entering the second value, but, if I just use 1 value it executes normally. I've gone through it several times, but, I can't find my mistake. Could you guys help me find why I'm getting the error?

Here's the .h file:

#include <stdio.h>
typedef struct node Node;

struct node
{
    int d;
    Node *link;
}*head,*current,*prev;

int num_nodes;

void linked_list_init(int data);
void linked_list_sort();
void linked_list_print();

And here's the .c file:

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

void main(){

    int n,e,i;
    printf("How many numbers do you want to sort: ");
    scanf("%d",&e);
    for(i=0;i<e;i++){
        printf("Enter number: ");
        scanf("%d",&n);
        linked_list_init(n);
    }
    linked_list_sort();
    printf("The sorted numbers are: ");
    linked_list_print();
}

void linked_list_init(int data){
    Node *prev=0,*next=0;

    current=(Node*)malloc(sizeof(Node));    
    if(head==0)
    {
        head=current;
        current->d=data;
        current->link=0;
        prev=current;

    }
    else{
        current->d=data;
        current->link=0;
        prev->link=current;
        prev=current;
    }
    }

void linked_list_sort(){
    int i,j;
    Node *prev=0,*next=0;

    current=head;
    prev=head;
    next=head->link;

    for(i=0;i<num_nodes-1;i++)
    {
        for(j=0;j<num_nodes-i-1;j++)
        {
            if(current->d>next->d)
            {
                current->link=next->link;
                next->link=current;
                if(current==head)
                {
                    head=next;prev=next;
                }
                else
                {
                    prev->link=next;prev=next;
                }
                if(next!=0) //check whether final node is reached
                    next=current->link;

            }
            else //move each node pointer by one position
            {
                prev=current;
                current=next;
                next=current->link;
            }

        }
        //next iteration
        current=head;
        prev=head;
        next=current->link;
    }

}

void linked_list_print(){
    current=head;
    while(current!=0){
        printf("%d ",current->d);
        current=current->link;
    }
}

Some programmer dude · Accepted Answer · 2013-02-06 06:47:19Z

5

The problem is that you're masking the global variables with local declarations in your function. That means that the variable prev in the functions are not the same as the global variable prev.

Aside from that, you should never place variable definitions in header files, as those will clash with each other if the header file is included in multiple files.

There is also another small bug, in that you don't increase the counter when inserting a new node into the list.

edited Feb 6, 2013 at 6:47

answered Feb 6, 2013 at 4:18

Some programmer dude

411k36 gold badges420 silver badges655 bronze badges

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

5 Comments

Bhavik Shah Over a year ago

Also OP is checking head==0 shouldn't it be head==NULL ?

Some programmer dude Over a year ago

@BhavikShah Often in C, NULL is a macro (#define) that resolves to ((void *) 0). This was relaxed in C++ where NULL is almost never used instead of using 0 directly.

SecurityMatt Over a year ago

@JoachimPileborg: Say what? if(head == NULL) is easier to read than if(head == 0). And if you prefer shorter code, you'd probably be doing if(head) anyway.

SecurityMatt Over a year ago

@JoachimPileborg: Global variables are auto-initialized to zero as part of the ELF and PE file specifications, but you're right, Robert should be initializing them to avoid a NULL dereference segfault.

Some programmer dude Over a year ago

@SecurityMatt You're right about the initialization of global variables. I always seem to forget that. :)

Sagar Sakre · Accepted Answer · 2013-02-06 05:16:14Z

1

There is no need to initialize head to 0 because in your case you have declared it globally in header file ( although its not a good practice to declare variables in header files). The problem here is you are redefining prev node in void linked_list_init(int data) function. Just delete the prev node from there and everything would work fine.

Tips:

-> Declare the head, prev, current nodes in .c file.

-> Use NULL instead of 0 or even you can use (void *) 0 instead of simply 0

answered Feb 6, 2013 at 5:16

Sagar Sakre

2,43624 silver badges31 bronze badges

Comments

FieryDragon87 · Accepted Answer · 2013-02-06 04:24:22Z

0

It seems like you are creating and initializing *prev and *current everytime the linked_list_init function is called. Hence after you enter the second value, the second if loop is using prev, which has actually been set to 0.

I think what you are trying to do is use the *prev, *head and *current as global variables (since you have declared them in your header file). Just use extern to declare them in the source file and things should work.

answered Feb 6, 2013 at 4:24

FieryDragon87

591 silver badge8 bronze badges

Comments

rockstar · Accepted Answer · 2013-02-06 05:07:32Z

The global variable used in your program are uninitialized and hence prone to garbage values . Also i suggest the following defination for your node

struct node {
    int d;
    node *llink; // Left Link
    node *rlink; // Right Link
};
typedef struct node* Node;
Node head = NULL; // Head node

Also

void linked_list_init(int data) {

    Node newnode = (Node) malloc(sizeof (Node));
    newnode->d = data;

    Node curr;

    if (head == NULL) {

        newnode->llink = NULL;
        newnode->rlink = NULL;
        head = newnode;

    } else {
        curr = head;
        while (curr->rlink) {
            curr = curr->rlink;
        }
        curr->rlink = newnode;
        newnode->rlink = NULL;
        newnode->llink = curr;       
    }
}

The above will keep adding elements to the end of the list .

You can print data out easily as follows :

void linked_list_print() {
    Node curr;
    curr = head;
    while (curr) {
        printf("Element Data : %d", curr->d);
        curr = curr->rlink;
    }
}

Collectives™ on Stack Overflow

Segmentation fault using doubly linked list in C

4 Answers 4

5 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

5 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related