Question

C PROGRAMMING

Doubly Linked List For this program you’ll implement a doubly linked list of strings. You must base your code on the doubly linked list implementation given in my Week 8 slides. Change the code so that instead of an ‘int’ each node stores a string (choose a suitable size). Each node should also have a next node pointer, and previous node pointer. Then write functions to implement the following linked list operations:

• A printList function that prints the items in the list starting at the head, one item per line of output.

• An insertSorted function that can be used to insert strings (such as people’s names) and keep the list sorted. You’ll have to find the right place to insert the string according to alphabetical order. You can base your logic on the search code given in my slides. After that you can use the addNode, appendNode, or insertNode functions from my slides, as appropriate.

For example, when the list is empty you can immediately add the first string using addNode (or appendNode): Henry Suppose the next string is “Arun” which is earlier alphabetically. You would search for the node that comes after the new string and find “Henry”. Since this is the first node in the list you add the new one at the front using addNode: Arun Henry Imagine the next string is “Raveena” which comes after all existing nodes. You would reach the end of the list when searching and use insertNode (or appendNode) to add it after the node “Henry”. Arun Henry Raveena If the next string is “Gina” you would search for the first node that comes after the new string and find “Henry”. You add the new node “Gina” after the node that comes 2 before “Henry” using the insertNode function. Arun Gina Henry Raveena Don’t forget to use strcmp to compare strings, and strcpy to copy/assign them! There are several other ways to implement this logic – for example you could write an “insertBefore” function which is not given in my slides.

Main function: Your program’s main function should do the following in the order shown. – Initialize an empty linked list. – Use a loop to input strings from the user and add them to the list by calling insertSorted. The loop should stop when the user types “Done” (case insensitive, use strcasecmp). The word “Done” should not be added to the list. – Print the resulting sorted list. Computational Complexity Analysis: In comments at the top of your main .c file give the computational complexity of your program’s main loop using big-O notation. Consider what happens as the number of strings entered increases, including what happens in insertSorted. Write a couple of sentences to justify your answer. You should write clean modular code as much as possible, making use of functions to avoid code duplication

Answer 1

Solution - The required code is given below -

In this code, the structure defined is as follows -

struct node {
   char *data;          // to store the array to characters
   struct node *next;       // next pointer to linked list
   struct node *prev;      // prev pointer to linked list
};

There are two functions Insert_to_list() and Print_list().

1. Insert_to_list() function takes two parameters head and the string to insert. It inserts every string in sorted order. The order is determined by comparing the current string, prev string in linked list and next string in linked list using strcmp() function.
2. Print_list() takes one parameter to print the list.

In this code i have given input in the code itself but you can also take input values from the user using this code -

char str[20];
scanf("%s",str);
while(1){
   scanf("%s",str);
   if(strcmp("Done",str)==0 || strcmp("done",str)==0)
       break;
   Insert_to_list(&head,str);
}

#include <stdio.h> #include <string.h> #include <stdlib.h> #include <stdbool.h> // Structure of doubly linked list struct node {    char *data;    struct node *next;    struct node *prev; }; // print the linked list void Print_list(struct node** head) {    struct node *ptr = *head;    printf("\n[ ");       while(ptr != NULL) {             printf("%s ",ptr->data);       ptr = ptr->next;    }    printf(" ]\n"); } // insert element in sorted order in the linked list void Insert_to_list(struct node** head_ref, char *data) { // Allocating a new node for linked list and // initializing it with new string with prev and next NULL     struct node *newNode = (struct node*) malloc(sizeof(struct node));     newNode->data = data;     newNode->next = NULL;     newNode->prev = NULL;     struct node* current;     if (*head_ref == NULL)         *head_ref = newNode;     else if (strcmp((*head_ref)->data,newNode->data) >= 0) {         newNode->next = *head_ref;         newNode->next->prev = newNode;         *head_ref = newNode;     }     else{         current = *head_ref;         while (current->next != NULL && strcmp(current->next->data,newNode->data) < 0)             current = current->next;         newNode->next = current->next;         if (current->next != NULL)             newNode->next->prev = newNode;         current->next = newNode;         newNode->prev = current;     } } void main() { // Inserting string to linked list.    struct node* head = NULL;    Insert_to_list(&head, "One");    Insert_to_list(&head, "Two");    Insert_to_list(&head, "Three");    Insert_to_list(&head, "Four");    Insert_to_list(&head, "Five");    printf("The linked list is : \n"); // printing the list    Print_list(&head); }

Refer to the screenshot of code and output -

Output -