C Programming - Create a Doubly Linked List of Strings

[alexexcl]

Hello, I am trying to create a Doubly Linked List of Strings, and I need to modify the void insert, delete, and print methods respectively. To insert a node with the string alphabetically, delete a specific node, and print the linked list in reverse order and increasing order. The specifications are commented in the code. So in other words the implementation is as follows...
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).

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.
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.
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.

An example output for the program is:

$ ./hw3
CMD> list
command: list(0)
<empty>
CMD> insert hello
command: insert('hello')
CMD> insert good morning
command: insert('good morning')
CMD> insert bye
command: insert('bye')
CMD> insert good afternoon
command: insert('good afternoon')
CMD> list
command: list(0)
0: bye
1: good afternoon
2: good morning
3: hello
CMD> delete bye
command: delete('bye')
CMD> list 1
command: list(1)
2: hello
1: good morning
0: good afternoon
CMD> delete whatever
command: delete('whatever')
CMD> delete good afternoon
command: delete('good afternoon')
CMD> list
command: list(0)
0: good morning
1: hello
CMD> exit
bye!

My code that I have so far is below, can someone please help me complete or explain the void insert, delete, and print methods to get the desired output above?

#include "mylist.h"
#include <stdbool.h> //C library for boolean operations
#include <stddef.h> //C library for NULL operations
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*
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.
 */
typedef struct node_t node_t;
typedef struct node_t 
{
    char* str; //pointer to string
    struct node_t* prev; //pointer to previous
    struct node_t* next; //pointer to front
    
};
  struct node_t* head = NULL;

  //this link always point to last Link 
struct node_t *last = NULL;
struct node_t *current = NULL;
  //is list empty
 bool isEmpty()
 {
    return head == NULL;
 }
/*
insert(char* str), which creates a node with the given string. 
Important: 
1) 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.
 */
void insert(char* str) 
{

/* allocate node */
    struct node_t* new_node = (struct node_t*) malloc(sizeof(struct node_t));
	 char *newString;
//allocate the space for copying the string (str) passed in as the argument
    new_node->str = (char*)malloc(sizeof(char)*(strlen(str)+1));
    strcpy(newString, str);
if( new_node == NULL || new_node == head)//inserting at the front of Linked list
  {
    new_node->next = head;  //point it to old first new_node as the head
    head = new_node; //point first to new first new_node
  }
else if( new_node == last) //inserting at the end of the Linked List
{
  new_node->next = last; //point the tail it to old first new_node as
  last = new_node; //point first to new last new_node
}
while( ( *str != '\0' && *str2 != '\0' ) && *str == *str2 )
    {
        str++;
        str2++;
    }
 
    if(*str == *str2)
    {
        return 0; // strings are identical
    }
 
    else
    {
        return *str - *str2;
    }
}
 //strcmp() 
	/* 
    if(isEmpty()) 
      {
        //make it the last link
        last = link;
      } 
    else 
      {
        //update first prev link
        head->prev = link;
      }

   //point it to old first link
   link->next = head;
	
   //point first to new first link
   head = link;
   */
}

/*
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.
 */
 void delete(char* str)
 {
//start from the first link
    struct node_t* current = head;
    struct node_t* previous = NULL;
	
    //if list is empty
   if(head == NULL) {
      return NULL;
    }

    //navigate through list
    while(current->key != key) {
       //if it is last node
		
       if(current->next == NULL) {
          return NULL;
       } else {
          //store reference to current link
          previous = current;
			
          //move to next link
          current = current->next;             
       }
    }

    //found a match, update the link
    if(current == head) {
       //change first to point to next link
       head = head->next;
   } else {
       //bypass the current link
       current->prev->next = current->next;
    }    

    if(current == last) {
       //change last to point to prev link
       last = current->prev;
    } else {
       current->next->prev = current->prev;
    }
 	 free(str); //reclaim the space occupied by the string, and the other to reclaim the node itself. 
   free(new_node); //reclaim the space to reclaim the node itself
 
  
   return current;
	
 }
 /*
 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.
  */
 void list(int reverse_order)
 {
   while(node!=NULL)
   {
    printf("%d ", node_t->str);
    node = node_t->next;
   }
  //Missing boolean to print strings in order or reverse_order
 }

[dhayden]

Lines 13-20 should be:

struct node_t
{
    char *str;                  //pointer to string
    struct node_t *prev;        //pointer to previous
    struct node_t *next;        //pointer to front

};
typedef struct node_t node_t;

When working with a structure like a linked list, it's really helpful to have functions that will print the structure out. Here are functions to print the list, both in forward and reverse order. This will let you check to see if your list is valid:

void printList()
{
    // Print forward
    for (node_t *cur = head; cur; cur = cur->next) {
        printf("%s ", cur->str);
    }
    printf("\n");

    // Print reverse
    for (node_t *cur = last; cur; cur = cur->prev) {
        printf("%s ", cur->str);
    }
    printf("\n");
}

While developing your functions, you'll want to print the list after each change so you'll know right away if it becomes inconsistent or incorrect.

Let's work on insert() first. Here are some comments on your code:

void
insert(char *str)
{
    struct node_t *new_node = (struct node_t *) malloc(sizeof(struct node_t));
    char *newString;  // not necessary. See below

    // No need to include sizeof(char) below.
    new_node->str = (char *) malloc(sizeof(char) * (strlen(str) + 1));
    strcpy(newString, str);   // should be strcpy(new_node->str, str);

    // if new_node is null then you're out of memory.  For this program I'd ignore out of
    // memory conditions

    if (new_node == NULL || new_node == head)
    {
        new_node->next = head;
        head = new_node;
    } else if (new_node == last) /* last points to a node (or
                                    null). New_node points  to the
                                    new node. They will never be equal */
    {
        new_node->next = last;
        last = new_node;
    }

    // Use strcmp() to find the location to insert the node
    while ((*str != '\0' && *str2 != '\0') && *str == *str2) {
        str++;
        str2++;
    }

    if (*str == *str2) {
        return 0;                                // strings are identical
    }

    else {
        return *str - *str2;
    }
}

With the change to line 9 above, you have code that constructs the new node correctly. After that there are two things and you should code them up separately:
1. Decide where the new node should go in the list.
2. Insert it there.

I'll give you the code to figure out where it goes:

    node_t *prev=NULL, *cur;  // previous and next nodes

    for (cur = head; cur ; cur = cur->next) {
        if (strcmp(cur->str, new_node->str) > 0) {
            break;
        }
        prev = cur;
    }

    // Now cur is NULL or points to the node that we should insert before.
    // Prev is NULL or points to the node before cur 

See if you can add the code to insert it in the right order. Use this main program to test:

int main()
{
    insert("D");
    insert("E");
    insert("B");
    insert("C");
    printList();
}

The output should be:

B C D E
E D C B