Lab06, CISC181, Fall 2005

Practice with Linked Lists

This lab is designed to give you practice working with linked lists.

Look at the source file: lists.cc (found in the lab06 directory on the course web site.)

In this file, the pointer variable mylist (in the main function) points to the first element in the linked list. A function make_a_list builds the linked list. Three other functions: print_list, add_at_front and add_at_back, are not complete. The calls to the other functions are already given in the main program (some are commented out). Your assignment is to complete these functions.

Understanding each of the List functions

• make_a_list
  This function builds the linked list. Note that head points to the head, or start, of the list, and is initially NULL since the list starts out empty.
  
  The functions loops through the integers 20 down to 2. During each iteration, a new node is created. This new node will be inserted at the beginning of the list. The value field of this node gets assigned the current integer (num), and the next field of the node is assigned what head used to point to.
  
  When the loop finishes, the value of head, which points to the first element of the list, automatically goes back to the calling function, since it is itself a reference parameter.
  
• print_list
  Once you understand the previous code, a good place to start is the print_list function. Basically, you want to loop through each node in the list until you reach a NULL value (which indicates the end of the list). As you are looping, you want to print the integer value stored in that node.
  
• add_at_front
  The add_at_front function will insert a new node at the beginning of the list. So, you want to first create a new node. Next, assign to this new node (in its value field) the integer value (addvalue) that was passed to the function. You also want the node's next field to point to the previous first element of the list. Finally, you want the head of the list to point to this new first element.
  
• add_at_back
  In this function, you will need to loop through all elements of the list until you reach the last element of the list. Since we are adding a new node to the list, you will want to create a new node. Then, assign to this new node the integer value that was passed to the function. Since this new node will be the last node in the list, be sure to assign its net field appropriately. Finally, don't forget to have the previous node point to the new node.
  

What you have to do

• Make a copy of lists.cc in a file lab06a.cc. Notice that each of the add functions has similar code to make the new node, i.e.:
  
  

  tptr = new node;
  tptr->value = (some number value);
  tptr->next = (some pointer value);

  This suggests that a function might be good: create a function, called make_new_node which takes a single int as an argument, builds a new node (setting the value field to the int passed in, and the next field to NULL) and returns the address of the new node.
  
  The change the "add" functions so that they use the new function. Once this works, make a script file lab06a.txt to hand in.
  
• Make a copy of lab06a.cc in a file lab06b.cc Next, change each "add" function so that is properly handles adding to an empty list ( where head is null ). Make a script lab06b.txt with the source code and a run of a small test program to show this working.
  
• Finally, make a copy of lab06b.cc in a file lab06c.cc. In this version, the function make_a_list should call the "add" functions to make the list. Have it alternately call add_at_back and add_at_front. Make a script lab06c.txt showing this working.
  
  Hints for lab06c.cc:
  • You are alternating between calling add_at_back and add_at_front inside the while loop that counts down from 20 to 2
  • One way to do it involves using the % operator
  • Another way is to declare a bool variable with bool nextCallShouldBeToAddAtFront = true; and each time through the loop, test that variable and then toggle it (toggle means to change from true to false, or false to true).

Finishing and Submitting

1. Upload your three .txt files and your three .cc files to WebCT and submit. Print your three scripts files for your TA.

Grading:

100 pts: 30 pts each for the three files (divided among style and correctness as the TA sees fit), and 10 points for overall correct submission.