In this lab you will implement a number of functions for linked lists of strings, creating both an iterative version and a recursive version. This builds of course on Unit 9 on linked lists but also relies on Section 5 from Unit 5 on how to write your own header files.

1 Linked list library

You will write and submit three files for this lab: a header file list.h that contains a struct definition as well as function prototypes as outlined below, and two different definitions files iterlist.c and recurlist.c. Those definitions files will implement all the same functions listed in list.h, once using loops and once using recursive calls.

Here is a main.c program that shows some very small examples of using the functions you’re about to implement. To compile this program with the iterlist.c implementation, you would run

roche@ubuntu$ gcc iterlist.c main.c -o main

(And similarly to try it with the recurlist.c implementation.)

Of course, this is just a very small test; you should definitely write your own tests and can create any other main programs you like! For grading, we will only look at list.h, iterlist.c, and recurlist.c.

Here are the functions you should implement for this part:

• struct node* add2front(char* s, struct node* L); — you’ve seen this one before
• void print_fwd(struct node* L); — prints all the strings in the order they occur in the linked list
• void free_list(struct node* L); — frees all nodes in the linked list
• int contains(char* s, struct node* L); — returns 1 if the string s appears in the list L, otherwise returns 0
• char* get_ith(int i, struct node* L); — returns the ith string in the linked list, counting the first item in the list as index 0
• int num_chars(struct node* L); — returns the total number of characters in all the strings in the linked list

And here is how the main.c program will run once you have those implemented:

roche@ubuntu$ ./main
Enter 5 words in reverse order: blue green purple orange red

Contents in order:
red
orange
purple
green
blue

contains orange: 1
contains brown: 0

the string at index 2 is purple

the total number of characters is 24

2 Two more functions (going further)

The rest of this lab is optional for your enrichment and enjoyment. Be sure to work on this only after getting everything else perfect. You should still submit this work, but make sure it doesn't break any of the parts you already had working correctly!

Try these two if you have time, both iteratively and recursively. Which version do you like better?

• void print_rev(node* L); — prints all the strings in reverse order, from last to first
• node* remove_ith(int i, node* L); — removes the node at index i in the list, and returns the resulting list with that node removed.

Once this part is finished, you can uncomment the last lines in the main.c program to get:

roche@ubuntu$ ./main
Enter 5 words in reverse order: blue green purple orange red

Contents in order:
red
orange
purple
green
blue

contains orange: 1
contains brown: 0

the string at index 2 is purple

the total number of characters is 24

Contents in reverse order:
blue
green
purple
orange
red

Contents after removing index 3:
red
orange
purple
blue