Question

In C Language. build a singly linked list where each node stores a randomly generated value on [0,1]. Keep the list sorted. Generate some number of nodes at startup. Print out the list formatted as e.g. → 0.04,0.19,0.27,0.33,0.54,0.66,0.75,0.99

Answer 1

Hi. I have answered similar questions before. Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. Thanks

#include<stdio.h>

#include <stdlib.h>

#include<time.h>

//structure representing a node

struct ListNode{

                double data;

                struct ListNode *next;

};

//method to create a node with given data and return it

struct ListNode* createNode(double data){

                //creating memory dynamically, for a ListNode

                struct ListNode* node = malloc(sizeof(struct ListNode));

                //setting data

                node->data = data;

                //NULL value for next field

                node->next = NULL;

                return node;

}

//method to insert a data at proper position, so that the list is sorted

//returns the head node of the updated list

struct ListNode* insertSorted(struct ListNode* head, double data){

                //creating node

                struct ListNode* node=createNode(data);

                //if list is empty, adding as head node

                if(head==NULL){

                                head=node;

                                return head;

                }else{

                                //checking if item can be added before head

                                if(data<head->data){

                                               //adding before head

                                               node->next=head;

                                               head=node;

                                               return head;

                                }

                                //now we check each adjacent pair of nodes, to see if we can

                                //add new item at the middle

                                struct ListNode* temp=head;

                                struct ListNode* temp2=head->next;

                                //looping until end of list

                                while(temp2!=NULL){

                                               //checking if item can be added in between temp and temp2

                                               if(data>=temp->data && data<temp2->data){

                                                               //adding to the middle

                                                               node->next=temp2;

                                                               temp->next=node;

                                                               return head;

                                               }

                                               temp=temp->next;

                                               temp2=temp2->next;

                                }

                                //if program control reached this line, it means that the item is not

                                //added anywhere, so adding at the last

                                temp->next=node;

                                return head;

                }

}

//method to print a linked list comma separated.

void printList(struct ListNode* head){

                //taking a reference to head.

                struct ListNode* temp=head;

                //looping and printing data of each node, formatted with 2 digits precision

                while(temp!=NULL){

                                printf("%.2f",temp->data);

                                temp=temp->next;

                                //if this is not last node, printing a comma and space

                                if(temp!=NULL){

                                               printf(", ");

                                }

                }

                printf("\n");

}

//method to deallocate memory occuppied by nodes, to prevent memory leakage

void freeMemory(struct ListNode* head){

                struct ListNode* temp=head;

                while(temp!=NULL){

                                struct ListNode* temp2=temp;

                                temp=temp->next;

                                free(temp2);

                }

}

int main(){

                //seeding random number generator with time.

                srand(time(NULL));

                //creating a list, adding 20 random values

                struct ListNode* head=NULL;

                for(int i=0;i<20;i++){

                                //generating a value between 0 and 1

                                double randNum=(rand()/(double)RAND_MAX);

                                //adding to list, updating head.

                                head=insertSorted(head,randNum);

                }

                //printing list, it should be in sorted order.

                printList(head);

                //de allocating memory, and exiting

                freeMemory(head);

                return 0;

}

/*OUTPUT*/

0.09, 0.15, 0.17, 0.22, 0.29, 0.29, 0.34, 0.46, 0.48, 0.48, 0.49, 0.51, 0.53, 0.57, 0.59, 0.69, 0.74, 0.90, 0.94, 0.94