Laboratory Exercise on Linked Lists

Overview:

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

Introduction

Throughout this lab, 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 session on Scheme-like lists. After this practice, additional functionality is explored.

This lab involves working with lists of data, using an existing driver program which actually constructs the lists. In particular, 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.

1. 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, program namelist.c contains several stubs for additional functions, but details of these functions are not given. Your task in this lab is to fill in the pieces for two of these new functions on the menu.

Work Started in Class

2. Write the details for countList (struct Node * first) which counts 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.

3. Write the details for function printLast (struct Node * first) which should print the data for the last item on the list. (If the list is null, 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 .

4. Before moving to the putFirst function, review the code for namelist.c carefully. Functions print, printLast, and countList, take parameters of type Node *, while functions addName and deleteName take parameters of type Node **. Give a careful statement of why two types of parameters are used in these various functions.

   Note: Do NOT go on to the next part until you have written a convincing answer to this question!

5. Write the details for function putFirst (struct Node ** 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 remove that given item from its current place in the list (if it is not already first). Finally you need to insert that given item at the beginning of the list.

   Since 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 either list is null or the item designated is not found on the list.

Homework

6. The original namelist.c program included a print function that worked iteratively (with a while loop) to print the elements in the list. Write a function printRec that produces a similar listing using recursion.

7. Write a function printLast (struct Node * first) which uses recursion to print the last item on the list.

8. Write a function printReverse (struct Node *first) that prints the names in the nodes from the last node to the front.

   Test your program to see if it works for different cases such as a null list.

   Hint: As with Step 6, think recursively.