Insertion Sort with Linked List Pointers in C

Question

Disclaimer: I am a very novice programmer so if this question is stupid I do apologize. With the recent shutdown of universities I can no longer ask my TA's for help so the internet is the next best thing.

I've been having some issues working with linked lists - mainly sorting the values with a secondary pointer using insertion sort.

The list is generated with numbers using the 'next' pointer indicating direction, I'm attempting to sort the list by the randomly generated value held in each element, with the 'sort1' pointer indicating the sorted lists order.

The problem area in the code seems to be this while loop:

while(new->value >= current->value && current != NULL){
    current = current->sort1;
}

its used to go through the elements that are already sorted and find where the 'new' element should be placed, but I'm getting a segmentation fault error here, I believe when it reaches the end of the list, and the new element should be placed at the end of the list so the 'current' pointer points to null.

Any insight? TIA!

The test code, for reference:

int main(){

    int i, length;
    Node *head, *current, *new, *sorthead;

    head = NULL;
    sorthead = NULL;
    length = 5;

    //create linked list
    for(i=0;i<length; i++){

        new = (Node*) malloc(sizeof(Node));

        new->value = (int)rand_double(0,10);
        new->sort1 = NULL;

        new->next = head;
        head = new;
    }   

    //print list
    current = head;
    while(current != NULL){
        printf("<  %d  >\n", current->value);
        current = current->next;
    }

    //sort with sort 1
    new = head;
    while(new!=NULL){

        if(sorthead == NULL || new->value < sorthead->value){
            new->sort1 = sorthead;
            sorthead = new;
        }
        else{
            current = sorthead;

            while(new->value >= current->value && current != NULL){
                current = current->sort1;
            }
            new->sort1 = current;
            current->sort1 = new;

        }
       new=new->next;
    }

    //print sorted
    current = sorthead;
    while(current != NULL){
        printf("<  %d  >\n", current->value);
        current = current->sort1;
    }

    return 0;
}

Please provide a minimal reproducible example with specific hard coded data to demonstrate your problem. Otherwise see ericlippert.com/2014/03/05/how-to-debug-small-programs — Yunnosch
– Yunnosch, Commented Mar 25, 2020 at 19:57

Beta · Accepted Answer · 2020-03-25 20:26:07Z

1

Consider this loop:

while(new->key1 < current->key1 || current->sort1 == NULL){
    current = current->sort1;
}

If the first comparison is always true (i.e if the "new" node's key is less than any value already in the sorted list), then the loop will reach a node whose sort1 is null, set current equal to NULL, and then dereference it in the next pass -- Undefined Behavior, seg-fault if you're lucky.

The correction to the conditional is straightforward, but I think it's important that you work it out for yourself.

answered Mar 25, 2020 at 20:26

Beta

99.5k18 gold badges159 silver badges156 bronze badges

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

1 Comment

Cody Over a year ago

I found my error right after I posted it unfortunately haha, but thank you for pointing it out! The while loop seems to still give me errors even with the correct conditions, any insight as to why? (Not sure if these comments are allowed but.. again I'm new and you seem to know what you're doing!)

Collectives™ on Stack Overflow

Insertion Sort with Linked List Pointers in C

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related