CS 14 - Lab 5

In this lab you are going to implement a List class using a singly-linked list.

Note that the program must be written, compiled, and executed under Linux.

Create a directory called lab5 using the mkdir command and create your program files in this directory. Remember, in order to compile your program, you will need to use the g++ command.

list.h

I have provided the class interface for you. Click here to get it. You must use this class declaration for your program.

The class uses a sentinel node. The sentinel is automatically allocated in the class constructor (also provided). Notice that if allocating the sentinel fails, an exception is thrown.

list.cc

Create a file called list.cc and implement the class methods in this file.

Insert

This method takes an integer to insert into the list. The method should allocate a new node, set its key to the passed in value, and insert the new node at the beginning of the list. If allocating the new node fails, the method should throw an exception.

Search

This method should search the list, returning true if the value passed in is in the list, false otherwise.

Remove

If the passed in value is in the list, this method should remove it and return true, else it should return false. Note that because this is a singly-linked list, you will need to have a pointer to the node before the node to delete.

Dump

This method simply prints all of the values in the list.

main() Function

Write a main() function to test your list class. The program should create a variable of type List, then present a menu to the user: 
   I) Insert Value To List
   S) Search For Value In List
   R) Remove Value From List
   D) Dump List
   Q) Quit
The program should allow the user to keep choosing options until 'Q' is selected.

Grading

When you have finished the program, your TA will grade it. To receive full credit, your TA will check all of the following: