Back to CS211 home

The problem described in Lab Exam 3 was familiar to you. A number of integers/characters were required from the user and this data was to be processed by your program in some manner (searched for duplicates, for example). Unfortunately, as was stated in the problem, "the user indicates that they are finished by entering" a negative integer or special character. How large, then, should we make the array? Ten, one hundred, one million elements? And what if we then require space for one million and one?

The solution was to make an array of length zero, and add one to it every time the user enters an integer/character. The following snippit of code gets the idea across (list is an integer array of length size. newint holds the next value to be stored in the list).

    /* save a pointer to list called templist, create a new list,
    ** copy templist into list, append tempint, delete templist.
    */
    int * templist = list;

    size++; // increase the length by one
    list = new int[size];

    counter = 0;
    /* copy the old list into the new (longer) list
    */
    while (counter < (size-1)){
      list[counter] = templist[counter];
      counter++;
    }
    list[counter] = newint;

    delete [] templist;

This solves the problem, but it is a very inefficient method. Can you see that in order to read in a new letter we must copy every previous letter? One way of reducing this extra work would be to double the length of our array every time we ran out of space, rather then increasing it by one. A way of avoiding the need to copy altogether would be to use a linked list. This is the problem asked in Lab Sheet 3 Problem 3.3. (Linked lists have many other advantages since they are not restricted to a grid-like shape as arrays are. Linked lists have disadvantages too; see last semester's CS210 notes.) Here is the problem again.

Problem 4.1 A computer program is required that reads positive integers, one per line, from the keyboard into a list. The user indicates that they are finished by entering any negative integer (the negative integer itself is not stored). The computer program then prints out the list of numbers, on a single line, separated with blank spaces. Write this program using a linked list.

By the end of this lab you MUST be capable of solving problem Problem 4.1 or you will have great difficulty keeping up with lectures. To start you off, Problems 3.2 and 3.4 on the last sheet are designed to highlight the issues involved with inserting into and searching a linked list (re-read last semester's CS210 notes). When you have a clear understanding of what is required (if you are having difficulties, get into groups with your colleagues, ask your demonstrators or myself) then you may begin designing and coding.

The following code might come in handy:

Create a user-defined type for the list elements:
struct ListElement
{
  int element; // the data
  ListElement * next; // a pointer to the next element in the list
};

Create an empty list:
  ListElement * list; // a pointer to the head of the list
  list = NULL; // initialise the list (mark the end of the list with NULL).

Typical function prototypes:
ListElement * AddtoFront(ListElement * head, int newdata);
  /* This function takes a linked list and a piece of data and creates
  ** a new node with that data, adding it to the front of the list.
  */
ListElement * PrintList(ListElement * list);
  /* This function prints out the list. It does so by printing out the
  ** contents of the head of the list and then repointing the head to
  ** the next element in the list. It repeats this until the end of the
  ** list (a NULL) is found. The function returns a pointer to the
  ** head of the list.

Create a pointer to a node:
  ListElement * ptr1;

Allocate memory for a node:
  ptr1 = new ListElement;

Put the integer 5 in a node pointed to by ptr1:
  ptr1->element = 5;

Point ptr1 at the node ptr2 is pointing to:
  ptr1 = ptr2;

Point the node ptr1 is pointing to at the node ptr2 is pointing to:
  ptr1->next = ptr2;

Please show a demonstrator your program when it is finished and they will mark you down for a credit. The next step is to code additional functionality:

Problem 4.2 Modify your solution to Problem 4.1 by adding the following functions: