Question

implement a doubly-linked list in C. Each node in the linked list should contain a string, a pointer to the previous node (or NULL), and a pointer to the next node (or NULL). The nodes should be sorted by their strings. 

struct node_t {
    char* str;
    struct node_t* prev; 
    struct node_t* next; 
}

To maintain the doubly-linked list, you should keep a pointer to the head node of the list (or NULL if the list is empty), and a pointer to the tail node of the list (or NULL if the list is empty). Optionally you may also keep an integer count, which indicates the current number of nodes in the list.

You should implement the following functions in mylist.c file (a template file is provided). The functions are declared in the header file mylist.h (the header file is provided and you’re not allowed to modify this file).

1. insert(char* str), which creates a node with the given string. Important: you should use the malloc() function twice: once to allocate the space for the node, and the other to allocate the space for copying the string (str) passed in as the argument. You should then insert the newly created node into the doubly-linked list in increasing order (using the standard strcmp() function from libc for string comparison). It’s OK to have nodes with the same string.
2. delete (char* str), which removes the node that has the given string. You should search for the node by following the linked list in order; once the node is found, you should reclaim the node by calling the free() function twice: once to reclaim the space occupied by the string, and the other to reclaim the node itself. If the node is not found, the operation can be simply ignored.
3. list(int reverse_order), which prints out all the strings stored in the linked list in order. If reverse_order is true (i.e., non-zero), print the strings from tail to head. Otherwise, print the strings from head to tail.

A main function is provided in main.c file (this file is provided and you are not allowed to modify this file). The main function takes command from standard input. If it’s ‘insert’, the main function will call the insert() function with the string to follow. If it’s ‘delete’, the main function will call the delete() function with the string to follow. If it’s ‘list', the main function will call the list() function with the integer value (true or false) to follow. Type ‘quit’ or ‘exit’ to terminate the program.

Answer 1

Screenshot of the code:

Sample Output:

Code to copy:

//mylist.h:

//Include required extensions of the header file.

#ifndef __MYLIST_H__

#define __MYLIST_H__

//Declare the prototype of the required functions.

extern void insert(char* str);

extern void delete(char* str);

extern void list(int reverse_order);

#endif /*__MYLIST_H__*/

//mylist.c:

//Include required header files.

#include "mylist.h"

#include <string.h>

#include <stdio.h>

#include <stdlib.h>

//Define the structure of the node.

struct node_t

{

//Declare required members of the structure of the

//node of the doubly linked list.

char* str;

struct node_t* prev;

struct node_t* next;

};

//Create two pointers to the structure one for head of

//the list and second for the tail of the list.

struct node_t *head = NULL;

struct node_t *tail = NULL;

int count_of_nodes = 0;

//Define the function insert() having required string

//value.

void insert(char* str)

{

  printf("command: insert('%s')\n", str);

//Create a new node of the structure node_t.

struct node_t *new_node = (struct node_t*)malloc

(sizeof(struct node_t));

//Initialize required pointers of the new node.

new_node -> next = NULL;

new_node -> prev = NULL;

//Allocate memory for the string of the new node.

new_node -> str = (char *)malloc(sizeof(strlen(str)));

//Assign the given string to the new node's string

//value.

strcpy(new_node -> str, str);

//If the list is empty i.e., head of the list is null,

//then make the new node as head and tail of the list.

if(head == NULL)

{

    head = new_node;

    tail = new_node;

}

else

{

    //Declare and initialize required pointers to

    //structure.

    struct node_t *temp = head;

    struct node_t *curr = NULL;

    //Start a while loop till the temp is not null.

    while(temp != NULL)

    {

      //If the current node's string is greater than

      //the new node's string, then break the loop.

      if(strcmp(temp->str, new_node->str) > 0)

      {

        break;

      }

      //Assign temp to curr pointer and traverse the

      //list forward by assigning next of the temp

      //node to the pointer temp.

      curr = temp;

      temp = temp -> next;

    }

    //If the pointer curr is still null, then it

    //means insertion should be on head.

    if(curr == NULL)

    {

      //Assign temp to the next of new node.

      new_node -> next = temp;

      //Assign new node to the previous of temp

      //node.

      temp -> prev = new_node;

     

      //Make new node as new head of the list.

      head = new_node;

    }

    //If the temp is still null, then it means

    //insertion should be at the end of the list.

    else if(temp == NULL)

    {

      //Assign new node to the next of the current

      //node.

      curr -> next = new_node;

      //Assign current node to the previous of the

      //new node.

      new_node -> prev = curr;

      //Assign new node to the tail pointer.

      tail = new_node;

    }

    //Otherwise,

    else

    {

      //Assign new node to the next of the current

      //node.

      curr -> next = new_node;

      //Assign new node to the previous of the temp

      //node.

      temp -> prev = new_node;

     

      //Assign current node to the previous of the new

      //node.

      new_node -> prev = curr;

     

      //Assign temp to the next of the next of the

      //new node.

      new_node -> next = temp;

    }

}

//Increment the count of the node of the list.

count_of_nodes++;

}

//Define the function delete() having a parameter

//as a string.

void delete(char* str)

{

printf("command: delete('%s')\n", str);

//Declare and initialize required pointer to the

//structure variables.

struct node_t *temp = head;

struct node_t *curr = NULL;

//Start the while loop till the temp node is

//not null.

while(temp != NULL)

{

    //If the given string is equal to the temp

    //node's string, then break the loop.

    if(strcmp(str, temp->str) == 0)

    {

      break;

    }

    //Assign temp node to the current node.

    curr = temp;

    //Traverse the list forward by assigning next

    //of the temp node to the pointer temp.

    temp = temp -> next;

}

//If the temp pointer is still null, then return

//from the function.

if(temp == NULL)

{

    return;

}

//Otherwise,

else

{

    //If the number of node is 1, then make head

    //and tail of the list null and free both the

    //string and node of the list.

    if(count_of_nodes == 1)

    {

      head = NULL;

      tail = NULL;

      free(temp->str);

      free(temp);

    }

    //If the current node is still null.

    else if(curr == NULL)

    {

      //Make next of the temp node as new head of the list.

      head = temp -> next;

     

      //Assign null to the previous of the head pointer.

      head -> prev = NULL;

      //Free both the string and current node of the

      //list.

      free(temp -> str);

      free(temp);

    }

    //If the next of the temp node is null.

    else if(temp -> next == NULL)

    {

      //Assign previous of the temp node to the tail

     //pointer.

      tail = temp -> prev;

      //Assign null to the next of the tail node.

      tail -> next = NULL;

      //Free both the string and current node of the

      //list.

      free(temp->str);

      free(temp);

    }

    //Otherwise,

    else

    {

      //Assign next of the temp node to the next of

      //the current node.

      curr -> next = temp -> next;

      //Assign current node to the next of the temp

      //node.

      temp -> next -> prev = curr;

      //Free both the string and current node of the

      //list.

      free(temp -> str);

      free(temp);

    }

    //Decrement the count of the nodes.

    count_of_nodes--;

}

}

//Define the function list() having required

//integer parameter.

void list(int reverse_order)

{

//Assign count of nodes to a variable

//num_of_nodes.

int num_of_nodes = count_of_nodes;

//Initialize a variable num_nodes to 0 to store

//the current node number while displaying the

//list from head to tail.

int num_nodes = 0;

//Display the message to show the command.

  printf("command: list(%d)\n", reverse_order);

//If head is null i.e., list is empty, then

//show the message <empty> and return from

//the function.

if(head == NULL)

{

    printf("<empty>\n");

    return;

}

//Otherwise,

else

{

    //If the value of the reverse_order is not zero,

    //then display the list from tail to the head of

    //the list.

    if(reverse_order != 0)

    {

      //Assign tail of the list to the pointer to

      //structure variable temp.

      struct node_t *temp = tail;

      //Start a while loop till the temp node is not

      //null.

      while(temp != NULL)

      {

        //Display the current node's string.

        printf("%d: %s\n", (num_of_nodes - 1),

        temp -> str);

        //Assign previous of the temp node to the temp

        //pointer to traverse the list from tail to head.

        temp = temp -> prev;

        //Decrement the value of num_of_nodes variable.

        num_of_nodes--;

      }

    }

    //Otherwise,

    else

    {

      //Assign head of the list to the pointer to

      //structure variable temp.

      struct node_t *temp = head;

      //Start a while loop till the temp node is not

      //null.

      while(temp != NULL)

      {

        //Display the current node's string.

        printf("%d: %s\n", num_nodes, temp -> str);

        //Assign next of the temp node to the temp

        //pointer to traverse the list from head to tail.

        temp = temp -> next;

        //Incrementing the value of the variable num_nodes.

        num_nodes++;

      }

    }

}

}

//main.c:

//Include required header files.

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <ctype.h>

#include "mylist.h"

//Start the execution of the main() method.

int main(void)

{

//Declare required variables to show the sample

//output.

char* command;

char* function_name;

char *functionArgument;

int i = 0;

int j = 0;

int index = 0;

int function_argument_length;

size_t MAX = 100;

//Start a while loop.

while(1)

{

    //Prompt the user to enter a command.

    printf("CMD> ");

    getline(&command, &MAX, stdin);

    //Append null character at the end of the string

    //command.

    command[strlen(command) - 1] = '\0';

    //Convert the whole command entered into lowercase

    //string.

   

    //Start a for loop till the null character of the

    //string command.

    for(i = 0; command[i] != '\0'; i++)

    {

      //If the current character of the string is an

      //upper case letter, then add 32 to its ASCII

      //value to convert it into lower case letter.

      if(command[i] >= 'A' && command[i] <= 'Z')

      {

        command[i] = command[i] + 32;

      }

    }

    //Again, initialize i to 0.

    i = 0;

    //If the command entered is quit or exit, then

  //break the loop.

    if(strcmp(command, "quit") == 0 ||

    strcmp(command, "exit") == 0)

    {

      printf("bye!\n");

      break;

    }

    //Otherwise,

    else

    {

      //Start the loop to traverse the command entered.

      for(i = 0; i < strlen(command); i++)

      {

        //Extract the name of the function to be called

        //from the whole string command. The loop will

        //run till the first space found in the command

        //string.

        //If current character in the command is not a

        //space.

        if(command[i] != ' ')

        {

          //If the length of the word which is to be

          //made for the function name is 0, then

          //allocate a memory of 1 byte (char) to the

          //variable function_name.

          if(index == 0)

          {

            function_name = (char*)malloc(sizeof(char));

          }

          //Otherwise,

          else

          {

            //Reallocate the memory to function_name by

            //incrementing by the value of the index

            //variable.

            function_name = (char*)realloc

            (function_name, index * sizeof(char));

          }

          //Assign current character to the

          //function_name string at current index

          //value and increment the index value by 1.

          function_name[index] = command[i];

          index = index + 1;

        }

       

        //If the current character in the command is

        //space.

        else

        {

          //If the length of the function name (the

          //string accessed before the first space

          //character in the command) is not 0.

          if(index != 0)

          {

            //Append null character to the function

            //name extracted.

            function_name[index] = '\0';

          }

         

          //Set the index value to 0 again for the next

          //function name going to be extracted in the

          //next command.

          index = 0;

         

          //And break the loop.

          break;

        }

      }

   

      //If the length of the function name extracted is

      //not 0 (only the function name is written in the

      //command, then there will be no spaces to read

      //and the else part of the above for loop will

      //never be executed, so to append the null

      //character in the function name extracted

      //which is equal to the command entered in

      //this case, this if statement is used).

      if(index != 0)

      {

        //Copy command to the function name in this

        //case and make the length of the function

        //name (index) again 0 for the next command

        //to read.

        strcpy(function_name, command);

        index = 0;

      }

      //Get the length of the argument written in the

      //command by subtracting the length of the

      //function name extracted from the length of the

      //command.

      function_argument_length = strlen(command) -

      strlen(function_name);

     

      //Allocate the memory for the function argument

      //written in the command.

      functionArgument = (char*)malloc(sizeof(char) *

      function_argument_length);

      //Traverse the command from 0 to the length of

      //the function argument.

      for(j = 0; j < function_argument_length; j++)

      {

        //Append the character placed at the index

        //value (length of the function name plus

        //current index of the loop plus 1) in the

        //command to the function argument made from

        //the command at current index of the loop.

        functionArgument[j] = command[strlen

        (function_name) + j + 1];

      }

      //Append null character at the end of the

      //function argument extracted from the command.

      functionArgument[j] = '\0';

      //Convert the whole function name extracted from

      //the command into lowercase string.

      //Start a for loop till the null character of the

      //function_name string.

      for(i = 0; command[i] != '\0'; i++)

      {

        //If the current character of the string is an

        //upper case letter, then add 32 to its ASCII

        //value to convert it into lower case letter.

        if(function_name[i] >= 'A' &&

        function_name[i] <= 'Z')

        {

          function_name[i] = function_name[i] + 32;

        }

      }

      //If the function name in the command is insert,

      //and if the length of the function argument is

      //not 0, then call the function insert() by

      //passing the argument in the function.

      if(strcmp("insert", function_name) == 0 &&

      function_argument_length != 0)

      {

        insert(functionArgument);

      }

      //If the function name in the command is delete,

      //and if the length of the function argument is

      //not 0, then call the function delete() by

      //passing the argument in the function.

      else if(strcmp("delete", function_name) == 0 &&

      function_argument_length != 0)

      {

        delete(functionArgument);

      }

      //If the function name in the command is list, and

      //if the length of the function argument is not 0,

      //then call the function insert() by passing the

      //argument in the function.

      else if(strcmp("list", function_name) == 0)

      {

        //If there is no function argument written i.e.,

        //the length of the function argument is 0, then

        //call the function list() by passing the

        //argument 0.

        if(function_argument_length == 0)

        {

          list(0);

        }

       

        //Otherwise, call the function list() by

        //passing the function argument converted

        //into the integer.

        else

        {

          list(functionArgument[0] - '0');

        }

      }

      //Free the memory occupied by the function_name.

      free(function_name);

    }

}

}