Linked Lists in C

Goals:

This laboratory helps you gain more experience with the use of lists and pointers.

Introduction

Throughout this lab, you must work directly with C pointers and structs. Do not use the Scheme-like functions car, cdr, and cons that were included in some parts of the previous lab.

Some parts of this lab ask you to utilize work you may have done in parts of the previous lab on Scheme-like lists. After this practice, we explore additional functionality.

This lab involves working with lists of data, using an existing driver program to actually construct the lists. In particular, the file namelist.c contains a menu-driven program to maintain a list of names.

As written, the program contains functions to insert a name on the list (before a designated node), to delete a specified name from the list, and to print the names on the list.

Exercises

Copy namelist.c to your account, compile it, and run it several times to discover just what the program does.

As you may have discovered, in addition to the above features, the program namelist.c contains several stubs for additional functions, but details of these functions are not given. In this lab, your tasks will be to fill in the pieces for two of these new functions on the menu.

Implement the stub
```
countList (const node_t * first)
```
which prints a count of the number of items in the list.

To perform this task, you will want to move along the list item-by-item, counting the items as you go.
Implement the stub
```
printLast (const node_t * first)
```
which should print the data for the last item on the list. (If the list is empty, the procedure should print a message to that effect instead.)

To perform this task, proceed iteratively, moving along the list item-by-item until coming to the end, where the next field is NULL.
Before moving on to the putFirst stub, review the code for namelist.c carefully. Functions print, printLast, and countList take parameters of type node_t *, while functions addName and deleteName take parameters of type node_t **. Give a careful statement of why the two different types of parameters are used in these various functions.

Note: Do NOT go on to the next part until you have written (preferably on paper) a convincing answer to this question!
Implement the stub
```
putFirst (node_t ** firstPtr)
```
which reads the name of an item on the list and moves that item to the front of the list.

To perform this task, you first have to read in the name of the item desired. Then you need to search the list item-by-item to find the desired item. Next you need to move that given item from its current place in the list (if it is not already first) to the beginning of the list.

Because manipulation of lists is most efficient if only pointers are manipulated, your program should neither create new nodes nor dispose of existing ones. In particular, your program should not use either the malloc or free functions during the processing of putFirst.

In effect, you will be reassigning several pointers. Consider a list where the item "sought" appears somewhere in the middle of the list, as shown below.

After putFirst runs, the various pointers will be reassigned as follows.

Your search loop must account for the need to manipulate the next field of the node preceding the entry containing "sought". (Alas, there is no previous field in our list node structure.)

Finally, your program should respond appropriately in all cases. In particular, putFirst should print appropriate messages if the list is empty or the item designated is not found on the list.
The original namelist.c program included a print function that worked iteratively (with a for loop) to print the elements in the list. Implement the function printRec that produces a similar listing using recursion.
Implement the function
```
void
printLastRec (const node_t * first)
```
that uses recursion to print the last item on the list.
Implement the function
```
void
printReverse (const node_t * first)
```
that prints the names in the nodes from the last node to the front.

Test your program to see whether it works for different cases such as a null (empty) list.

Hint: As with Step 6, think recursively. You may need a helper function (as with all functions; it too should be documented.)