Ankur Singh Ankur Singh - 2 months ago 58
C Question

Insertion Sort on doubly linked list in C

I am trying to perform insertion sort on a doubly linked list. When a user enters 'P' it will print the sorted elements stored. Elements are stored in list until the no of lines are exhausted which is denoted by nLines in code.

I am getting a segmentation fault.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
int data;
struct Node* previous;
struct Node* next;
}Node;

Node* head = {NULL};

// To insert new element into the doubly linked list
void insert(Node* currentPointer, int element)
{
Node* temp = (Node*)malloc(sizeof(Node));

if (head == NULL)
{
head = temp;
currentPointer = head;
head -> data = element;
head -> previous = NULL;
head -> next = NULL;
}

else
{
temp -> previous = currentPointer;
currentPointer -> next = temp;
currentPointer = temp;
currentPointer -> data = element;
currentPointer -> next = NULL;
}
}

//Performing insertion sort on the doubly linked list
void insertionSort(Node* currentPointer)
{
Node* temp = currentPointer;

while (temp != NULL && temp -> data < (temp -> previous) -> data)
{
int variable = temp -> data;
temp -> data = (temp -> previous) -> data;
(temp -> previous) -> data = variable;
temp = temp -> previous;
}
}

//Function to print the sorted elements
void printSorted()
{
Node* temp = head;
while(temp != NULL)
{
printf("%d ",temp -> data);
temp = temp -> next;
}
printf("\n");
}


int main()
{
int nLines;
Node* currentPointer0;
printf("Enter the no. of lines: ");
scanf("%d\n",&nLines);

while(nLines--)
{
int variable;
scanf("%d\n",&variable);

if ((char)variable == 'P' )
{
printSorted();
}

else
{
insert(currentPointer0,variable);
insertionSort(currentPointer0);
}

}

//After the program is done free all the memory
while(head != NULL)
{
Node* temp = head;
head = head -> next;
free(temp);
}

return 0;
}

Answer

From your code it seems you expect the insert function to update currentPointer0 in main.

Well, it doesn't.

C uses pass by value and any change you make to that value inside the function is lost when the function returns. In other words: If currentPointer0 has the value 42 when you call insert, it still has the value 42 when the function returns! The assignment like currentPointer -> next = temp; has no effect when the function returns.

In your case it is uninitialized so dereferencing it will (most likely) cause a crash.

You probably need double pointers:

void insert(Node** currentPointer, int element) // Notice
{
   Node* temp = (Node*)malloc(sizeof(Node));

   if (head == NULL)
   {
        head = temp;
        *currentPointer = head; // Notice
        head -> data = element;
        head -> previous = NULL;
        head -> next = NULL;
   }

   else
   {
        temp -> previous = *currentPointer;   // Notice
        (*currentPointer) -> next = temp;     // Notice
        (*currentPointer) = temp;             // Notice
        (*currentPointer) -> data = element;  // Notice
        (*currentPointer) -> next = NULL;     // Notice
   }
}

and call it like:

insert(&currentPointer0,variable);
Comments