CODEWITHSUNDEEP
c++sortinglinked-listsegmentation-faultsingly-linked-list
SAM
SAM

Reputation: 3

Segmentation fault on insertion of more than one elements in the linked list in a sorted order

I tried to do an insertion sort in a linked list. When only one element is inserted(i.e the first one),it executes well and fine but for multiple elements it gives segmentation fault. Can anyone tell me where the problem is?

#include <iostream>
using namespace std;

struct node
{
    int data;
    node* next;
} *head = NULL;

node* createNode(int x)
{
    node *temp = new node;
    temp->data = x;
    temp->next = NULL;
    return temp;
}

void insertSort(int x)
{
    if(head==NULL)
    {
        node  *temp = createNode(x);
        head = temp;
        return;
    }

    node *temp = createNode(x);
    node *prev = NULL;
    node *curr = head;
    bool inserted = false;

    while(curr != NULL || !inserted)
    {
        if(temp->data < head->data)
        {
            temp->next = head;
            head = temp;
            inserted = true;
        }

        else
        {
        if(temp->data < curr->data)
            {
                prev->next = temp;
                temp->next = curr;
                inserted = true;
             }
            else
            {
                prev = curr;
                curr = curr->next;
            }
        }


    }

    if(!inserted)
    {
    prev->next = temp;
    }

}

void display()
{
    node *p = head;
    while(p != NULL)
    {
        cout<<p->data<<" ";
        p = p->next;
    }

}

Upvotes: 0

Views: 85

Answers (1)

Vlad from Moscow
Vlad from Moscow

Reputation: 310930

For starters the function insertSort has redundant code

if(head==NULL)
{
    node  *temp = createNode(x);
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    head = temp;
    return;
}
node *temp = createNode(x);
^^^^^^^^^^^^^^^^^^^^^^^^^^^

Secondly the condition in the while statement

while(curr != NULL || !inserted)

is incorrect. There must be

while(curr != NULL && !inserted)

In any case the function is too complicated. It can be written simpler.

Here is a demonstrative program that shows how the function can be implemented.

#include <iostream>
#include <cstdlib>
#include <ctime>

struct node
{
    int data;
    node* next;
} *head = nullptr;

node* createNode(int x)
{
    return new node { x, nullptr };
}

std::ostream &  display( std::ostream &os = std::cout )
{
    for ( node *current = head; current != nullptr; current = current->next )
    {
        os << current->data << " - > ";
    }

    return os << "NULL";
}

void insertSort( int x )
{
    node *new_node = createNode( x );

    node **current = &head;

    while ( *current != NULL && not ( x < ( *current )->data ) ) 
    {
        current = &( *current )->next;
    }

    new_node->next = *current;
    *current = new_node;
}

int main() 
{
    const int N = 10;

    std::srand( ( unsigned int )std::time( nullptr ) );

    for ( int i = 0; i < N; i++ ) insertSort( std::rand() % N );

    display() << '\n';

    return 0;
}

The program output might look like

1 - > 2 - > 2 - > 3 - > 3 - > 3 - > 3 - > 8 - > 9 - > 9 - > NULL

Upvotes: 1

Related Questions