In Laboratory 5 you had to implement a linked list application using classes. Here are the problems again.

Repeat of Problem 5.1 Update the solution to Problem 4.1 that uses classes and a linked list by adding the following functionality:

• return true/false if a given integer is in the list,
• add a node to the end of the list,
• delete the entire list,
• count the number of elements in the list.

  Repeat of Problem 5.2 Update your solution to Problem 5.1 by adding the following functionality:

• delete a given integer from the list,
• print the list out in the opposite direction to PrintList() given above.

Here is a solution to Problem 5.1, with a test routine coded in main(). Make sure you understand all of this program. Ask your demonstrators to explain it if you have any difficulties (remember, drawing the linked list pictures will help you!). I have outlined how to solve Problem 5.2 in lectures.

Here are this week's problems. Once again, those students who do some work during the week will find they have a head start.

Problem 6.1 Same as Problem 5.2. A second chance to get a credit for this problem.

Problem 6.2 A class to maintain an ordered linked list of integers is required. Integers are to be sorted in ascending order. Call your class OrdIntList. The following methods should be supported by your class:

There is no need for any user interaction. Use main() to test your program. An example of one such main() is shown below (text version here).

void main(void){
  OrdIntList list; // the ordered list
  int tempint; // temporary storage

  list.Add(5);
  list.Add(2);
  list.Add(9);
  list.PrintList();

  tempint = 99;
  cout << endl << tempint << " is ";
  if (!list.Contains(tempint)) {
    cout << "not ";
  }
  cout << "in the list.";

  tempint = 9;
  cout << endl << tempint << " is ";
  if (!list.Contains(tempint)) {
    cout << "not ";
  }
  cout << "in the list.";
}

As soon as you are finished a problem, please show your solution to a demonstrator and they will mark you down for a credit (one credit per problem). When you are finished both problems, try to write methods for the following tasks. Good luck!

Linked list functionality that may be required in the future:

• Return the n^th integer in the list (if the list has >n elements)
• Return the location of integer X in the list (if it is in the list)
• Search for duplicates in the list
• Remove any duplicates from the list
• Swap any occurances of integer X in the list with integer Y
• Remove all integers less than X from the list
• Find the average value of the integers in the list

Information for Demonstrators:

When checking Problem 6.1, try all three possible delete cases (deleting from the front of the list, from the middle of the list, from the end of the list).

End of Lab Sheet