Question

I know this code takes in a set of numbers into a doubly linked list and sorts it using insertion sort. Could you explain exactly how this code is working?

main.c Source Code:

#include
#include
#include "node.h"

int main()
{
struct mynode *head=NULL;
int value;

printf("Give first value: \n");
scanf("%d",&value);

printf("Give next values, and input 0 to end list: \n");
do{
if(value>0){
   head = pushNode(head, value);
   scanf("%d",&value);
}
}while (value>0);

printf("Before insertion sort: ");
printlist(head);

head=insertsort(head);
printf("After insertion sort: ");
printlist(head);
return 0;
}

Source Code node.c:

//defines all functions of myNode declared in node.h
#include
#include
#include "node.h"

void printlist (struct mynode *node)
{
while(node)
{
if(node->next)
printf("%d<==>", node->value);
else
printf("%d\n", node->value);

node=node->next;
}
return;
}

struct mynode* pushNode(struct mynode *node, int const newValue)
{
struct mynode *newNode = (struct mynode*)malloc(sizeof(struct mynode));
//assign the head in the list which will be returned every time
struct mynode *list = node;
int *ptr = &newNode->value;
*ptr = newValue;
newNode->next = NULL;
if(node == NULL)
{
newNode->prev=NULL;
node=newNode;
list=node;
return list;
}
while(node->next != NULL)
{
node=node->next;
}
newNode->prev = node;
node->next = newNode;
return list;
}

struct mynode* insertsort(struct mynode *head)
{
//list variable to store the sorted list
struct mynode* sorted = NULL;
struct mynode* list = NULL;

struct mynode* current = head;
while (current != NULL) {
struct mynode* next = NULL;
next = current->next;
current->next = NULL;
current->prev = NULL;

if (sorted == NULL)
{
sorted = current;
list=sorted;
}
else if (sorted->value >= current->value)
{
current->next = sorted;
current->next->prev = current;
sorted = current;
list=sorted;
}
else
{
list=sorted;

struct mynode* newVal = NULL;
newVal = sorted;
//check where to enter the new value
while (newVal->next != NULL && newVal->next->value < current->value)
{
newVal = newVal->next;
}

current->next = newVal->next;

if (newVal->next != NULL)
current->next->prev = current;

newVal->next = current;
current->prev = newVal;
}

current = next;
}

//return the sorted list
return list;
}

Source Code node.h:

//declares the data structure and the functions of said data structure
#ifndef NODE_H_
#define NODE_H_

struct mynode {
int const value;
struct mynode *next;
struct mynode *prev;
};

struct mynode * insertsort(struct mynode *head);
void printlist (struct mynode *node);
struct mynode* pushNode(struct mynode *node, int const newValue);
#endif

Answer 1

Dear Learner

As doubly linked list work in the way as I given below:

It has 4 ways to insert the node in to doubly linked list such as insert from front, last, before particular and after particular node.

As per this code the insertion only take place at the end/last of the list.

Step 1: Coder create a header file which contains

· Structure of doubly linked list by using structure called mynode

· Three functions called pushNode (adding node), printlist (traversal) and insertion sort.

Step 2: Save the file node.h, which become header. With this header file he has to import the file only instead declaring the structure in the same.

struct mynode

{
int const value;
struct mynode *next;
struct mynode *prev;
};

struct mynode * insertsort(struct mynode *head);
void printlist (struct mynode *node);
struct mynode* pushNode(struct mynode *node, int const newValue);

Step 3: coder open new file code source code of C like below

#include "node.h"                                                           // calling header file                       

int main()
{
struct mynode *head=NULL;       // declare head pointer as a pointer by declaring the Null value
int value;

printf("Give first value: \n");
scanf("%d",&value);

Step 4: Do while look will accept the input and add to the list and jump every time to puchNode() function definition to perform the action till user will not provide the 0 for exit it add the values.

printf("Give next values, and input 0 to end list: \n");

do

{
if(value>0)

{
   head = pushNode(head, value);
   scanf("%d",&value);
}
}while (value>0);

//

struct mynode* pushNode(struct mynode *node, int const newValue)
{
struct mynode *newNode = (struct mynode*)malloc(sizeof(struct mynode));

//assign the head in the list which will be returned every time
struct mynode *list = node;

int *ptr = &newNode->value;
*ptr = newValue;
newNode->next = NULL;
if(node == NULL)
{
newNode->prev=NULL;
node=newNode;
list=node;
return list;
}
while(node->next != NULL)
{
node=node->next;
}
newNode->prev = node;
node->next = newNode;
return list;
}

Step 5: Called printlist () function before Insertion sort to display all elements of linked list.

printf("Before insertion sort: ");
printlist(head);

//function will work like this

void printlist (struct mynode *node)
{
while(node)
{
if(node->next)
printf("%d: ", node->value);
node=node->next;
}
return;
}

Step 6: Called insertionsort () function to perform the sorting

head=insertsort(head);

// calling function to it will jump to the function definition

struct mynode* insertsort(struct mynode *head)
{
//list variable to store the sorted list
struct mynode* sorted = NULL;
struct mynode* list = NULL;

struct mynode* current = head;
while (current != NULL) {
struct mynode* next = NULL;
next = current->next;
current->next = NULL;
current->prev = NULL;

if (sorted == NULL)
{
sorted = current;
list=sorted;
}
else if (sorted->value >= current->value)
{
current->next = sorted;
current->next->prev = current;
sorted = current;
list=sorted;
}
else
{
list=sorted;

struct mynode* newVal = NULL;
newVal = sorted;
//check where to enter the new value
while (newVal->next != NULL && newVal->next->value < current->value)
{
newVal = newVal->next;
}

current->next = newVal->next;

if (newVal->next != NULL)
current->next->prev = current;

newVal->next = current;
current->prev = newVal;
}

current = next;
}

//return the sorted list
return list;
}

Step 7: Called printlist () function after Insertion sort to display all elements of linked list.
           printf("After insertion sort: ");
             printlist(head);

Step 8: Exit

For more understanding see the image..