Implementing a Doubly-Linked List in C

Creating a Node with String Data

In this assignment, you are asked to implement a doubly-linked list in C. Each node in the linked list should contain a string (in a fixed sized char array), a pointer to the previous node (or Null), and a pointer to the next node (or Null).

struct node_t {

    char str[256];

    struct node_t* prev;

    struct node_t* next;

}

The order of the nodes in the linked list should be sorted in increase order of the strings. No two strings in the list shall be the same (see the insert() function below on how to handle the case when a duplicate string wants to be inserted into the list).

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

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 (note that you’re not allowed to modify this header file).

insert(char* str), which creates a node with the given string. You should use the malloc() function to allocate the space for the new node. You should use strcpy() function to copy the string str, which is passed in as the function argument, to the node's str char array. You should then insert the newly created node into the doubly-linked list by maintaining that all nodes are stored in the list in increasing order (you can use the standard strcmp() function from libc for string comparison). IMPORTANT: If the linked list already has a node with the the same string, instead of inserting the new node, you should remove both nodes (the newly created node and the node already in the list). The result is that the linked list shall never contain duplicate strings.

rev_list(), which prints out all the strings stored in the linked list in reverse order. That is, you print the strings by scanning the list from the tail of the list to the head of the list by chasing the prev pointer.

A main function is provided in the main.c file (you are not allowed to modify this file also). The main function takes input from stdin. Insert the input strings to the linked list until the input is exhausted (end of file). Then the function prints the list in decreasing order (using rev_list() function).

Sorting the List in Increasing Order

An example is shown as follows:

$ cat myfile

this is a book

a very interesting book

but what?

you don't see this

because

you don't see this

here here

$ ./hw4 < myfile

this is a book

here here

but what?

because

a very interesting book

Note that the line "you don't see this" appeared twice in the input (in myfile); therefore they were both removed from the linked list and from final print-out.

To complete this homework assignment, following the steps below:

Download the file templates here as a tgz file: hw4-template.tgz Download hw4-template.tgz

Create a directory for this homework and name it “hw4”. Place the files provided for this assignment into this directory.

Modify the file mylist.c, where all your implementation should reside.

One should be able to compile your programs by typing ‘make’, which will generate the executable file.

What hw4-template.tgz holds

 #include                                                                                                      

#include                                                                                                     

#include                                                                                                     

#include "mylist.h"

/* print the strings (from stdin) in decreasing order; duplicate                                                           

strings are removed from print */  

int main()

 {   

char buf[256]; 

char* str;                                                                                                              

while((str = fgets(buf, 255, stdin)) != NULL) {                                                                           

insert(str);                                                                                                         

 }                                                                                                                       

rev_list();                                                                                                          

 }                                                                                                                        

this is a book                                                                                                          

a very interesting book                                                                                                 

but what?                                                                                                              

you don't see this                                                                                                     

 because                                                                                                                 

you don't see this                                                                                                      

here here

all:hw4   

hw4: main.o mylist.o     

gcc -Wall main.o mylist.o -o $@ main.o: main.c mylist.h                                                                                                         

gcc -c -Wall $< -o $@ mylist.o: mylist.c mylist.h                                                                                               

gcc -c -Wall $< -o $@ clean:

rm -f hw4 *.o core *~

#include                                                                                                      

#include "mylist.h" /* The head and tail of the linked list. */                                                                             

struct node_t* head = NULL;                                                                                             

struct node_t* tail = NULL; 

void insert(char* str)                                                                                                 

 {                                                                                                                         

/* add your code here */                                                                                              

}                                                                                                                                                                                                                                               void rev_list()                                                                                                        

 {                                                                                                                         

/* add your code here */                                                                                              

}                                                                                                                         

#ifndef __MYLIST_H__                                                                                                    

#define __MYLIST_H__ struct node_t {                                                                                                           

char str[256];                                                                                                          

struct node_t* prev;                                                                                                   

 struct node_t* next;                                                                                                  

};                                                                                                                                                    

/* Create a node (of struct node_t type) that contains a COPY of the                                                       

string given as the argument. Insert the node into the doubly                                                           

linked list at the right location. (All nodes in the linked list                                                        

are sorted in increasing order. IMPORTANT: In case one inserts a                                                       

 string already contained in the list, this function will REMOVE the                                                     

string from the list. */                                                                                             

extern void insert(char* str);                                                                                                                                                            

/* Print the strings one by one by going through the linked list in                                                        

reverse order (from tail to head). */                                                                                

extern void rev_list(); 

#endif /*__MYLIST_H__*/