Lesson32 lab exercise - list1

Background:

1.   The student outline contains a program which stored a linked list of five nodes, but in reverse order.  The objective of this lab exercise is to create a linked list with the nodes assembled in order as they are generated.  If a loop is used to create the values 1-5, the resulting list should look like this:

The next value to be inserted would go at the right end of the list.  To avoid traversing the entire list each time, two pointers will provide access at the front (L.first = left end) and the end (L.last = right end) of the list.  The first and last pointers will be packaged as a structure.

struct listNode

{

    int  data;

    listNode  *next;

    listNode (int, listNode *);       // struct constructor

};

listNode::listNode (int tempData, listNode * tempNext)

{

      data = tempData;

      next = tempNext;

}

typedef  listNode*  listPtr;

struct  listType

{

    listPtr  first;

    listPtr  last;

};

In function main the declaration of the data structure would be something like

        listType  L;

2.   You are encouraged to use a struct constructor in this lab. 

3.   Your lab work can begin with the example program from Handout HA31-1, listDemo.cpp.

4.   If you do not use a struct constructor, the for loop inside of function createList should still be set up in ascending order, i.e.,

            for (int  k=1; k<=20; k++)

                  insert (someList, k);                                 

        The insert function will have to deal with several cases this time, an empty list case and a general case.  A two case solution is required because the pointer hookups are different for each case.  The following code/pseudocode is provided:

void insert (listType &temp,  int value)

//  Takes in value, packages it in a new node, inserts the new node at the end of the list.

{

if an empty list then

     set both first and last pointers to the newly constructed node

else

     construct a new node at the end of the list 

5.   If you use a struct constructor, you can skip the use of a separate insert function and build the list in function createList.

6.   Adjust the code in the other routines as needed.

Assignment:

  1.   Using the guidelines in the Background section above, code a linked list which stores the 20 integers from 1-20 in ascending order.

  2.   After the list is created, call printList to traverse the list and print out the 20 numbers in one line on the screen.

  3.   Add a function countNodes which returns a count of the number of nodes in the list.  Call this function from within function main and print out this value to the screen.

Instructions:

1.   Turn in your source code and a printed run output.

  2.   The run output will consist of the 20 numbers and a count of how many nodes are in the list.