Im trying to implement an Insertion Sort Doubly Linked List with User Input that sorts the List every time the User inputs data.
My code works just fine if you call the insertion sort function after all the data have been inputted by the user.
User Input: 5
User Input: 1
User Input: 3
User Input: 8
User Input: 7
User Input: 9
Unsorted List: 5 1 3 8 7 9
//Insertion Sort Function gets called after all the data have been entered//
Output: 1 3 5 7 8 9
But it gets messed up if I call the insertion sort function every time the user inputs a new data and somehow, it overwrites the next node if the inserted node is not at the end of list even though it has successfully inserted the new data in between the list.
User Input: 1
//Insertion Sort Function gets called//
Output: 1
User Input: 2
//Insertion Sort Function gets called//
Output: 1 2
User Input: 9
//Insertion Sort Function gets called//
Output: 1 2 9
User Input: 3
//Insertion Sort Function gets called//
Output: 1 2 3 9
User Input: 4
//Insertion Sort Function gets called//
Output: 1 2 3 4
As you can see, the 3 gets inserted just fine into the List but somehow, my code thinks that the end of the list is now after 3 so when I input a new data, for example, 4 into the new list, 9 gets overwritten because it thinks that 3 was the end of the list.
Is there something wrong with my insertion sort function?
How do I navigate back to the end of the list and make it so it adds the new data at the end of the list?
my whole code is included below,
#include<stdio.h>
#include<stdlib.h>
//// structure for a node ////
struct Node
{
int data;
struct Node *prev;
struct Node *next;
};
typedef struct Node NODE;
void UserInput();
void printList(struct Node *head, );
void insertionSort(struct Node **head_ref);
void sortedInsert(struct Node** head_ref, struct Node* newNode);
void main()
{
UserInput();
_getch();
}
void UserInput()
{
int loop=0;
int data;
struct Node *temp;
NODE *tail = NULL;
struct Node *head;
head = (struct Node*)malloc(sizeof(struct Node)); ////create node, store address to temp
printf("\nEnter Data: ");
scanf(" %d" , &data);
head->data = data;
head->prev = NULL; //// head node's prev is set to NULL
head->next = NULL; //// head node's next is set to NULL
tail = head;
printList(head);
while (loop < 9999)
{
temp = (struct Node*)malloc(sizeof(struct Node)); ////create node, store address to temp
printf("\nEnter Data: ");
scanf(" %d" , &data);
if(data == 9999)
{
break;
}
temp->data = data;
printList(head);
temp->prev = tail; //// prev pointer of temp is referenced to the last node
temp->next = NULL; //// next pointer of temp is NULL
tail->next = temp; //// next pointer of the tail node is referenced to the temp
tail = temp; //// temp is made as the tail node
insertionSort(&head);
printList(head);
loop++;
}
printf("Insertion of Numbers Terminated.");
//// If insertionSort function is called after all User Inputs, there are no problems in sorting.
//insertionSort(&temp);
printList(temp);
}
////Printing Function to get called every loop////
void printList(struct Node *head)
{
struct Node *temp1 = head;
temp1 = head;
printf("\nSorted Numbers: ");
while(temp1 != NULL)
{
printf(" %d ", temp1->data);
temp1 = temp1->next;
}
}
////Insertion Sort Algorithm to sort the list////
void insertionSort(struct Node **head_ref)
{
//// Initialize 'sorted' - a sorted doubly linked list
struct Node* sorted = NULL;
//// Traverse the given doubly linked list and insert every node to 'sorted'
struct Node* current = *head_ref;
while (current != NULL) {
//// Store next for next iteration
struct Node* next = current->next;
//// removing all the links so as to create 'current' as a new node for insertion
current->prev = current->next = NULL;
//// insert current in 'sorted' doubly linked list
sortedInsert(&sorted, current);
//// Update current
current = next;
}
//// Update head_ref to point to sorted doubly linked list
*head_ref = sorted;
}
void sortedInsert(struct Node** head_ref, struct Node* newNode)
{
struct Node* current;
//// if list is empty
if (*head_ref == NULL)
{
*head_ref = newNode;
}
//// if the node is to be inserted at the beginning of the doubly linked list
else if ((*head_ref)->data >= newNode->data)
{
newNode->next = *head_ref;
newNode->next->prev = newNode;
*head_ref = newNode;
}
else
{
current = *head_ref;
//// locate the node after which the new node is to be inserted
while (current->next != NULL && current->next->data < newNode->data)
{
current = current->next;
}
////Make the appropriate links ////
newNode->next = current->next;
//// if the new node is not inserted at the end of the list
if (current->next != NULL)
{
newNode->next->prev = newNode;
}
current->next = newNode;
newNode->prev = current;
}
}
The problem is in UserInput() while inserting the data the temp node's next should point to the tail's next so change this line
temp->next = NULL;
into this
temp->next = tail->next;
Why?? Because you are swapping the nodes themselves so after each insertionSort() the next of updated tail is not going to be NULL but its pointing to some previously added node's address since we are swapping the nodes so the addresses are being interchanged. Check the sample code here: https://ideone.com/gSKK7B