Requirements:

In this project, you will implement a classes:

1. Doubly linked sentinel lists: Double_sentinel_list

A skeleton header files for this classes is provided with the associated class. You may modify these files for the project, though you must add your own comments. Do not copy text from the specifications. Testing tools for some of the classes provided in the associated testing directory. Included is a simple exception header file which contains two classes, underflow and overflow which are thrown by some of the member functions.

You are required to submit within your gzipped tar file the following header files:

• Double_sentinel_list.h

The commands are:

{ecelinux:1} tar -cvf uwuserid_p1.tar Double_sentinel_list.h
{ecelinux:2} gzip uwuserid_p1.tar

Do NOT forget the uwuserid_p1.tar in the first command; otherwise, the command will overwrite the file Double_sentinel_list.h.

Be sure to read the instructions on the Projects page with regard to the submission of projects.

Runtime

The run time of each member function is specified in parentheses at the end of the description.

Comments

You are expected to comment your code. At least 20% of your source code must be in the form of valid and informative comments. As you will use this class in future projects, it is advisable to comment it appropriately. You are also expected to comment the provided bare header files.

Testing

With each project, two drivers are provided, one using the type int, the other using the type double. The use of these drivers is explained in the Testing directory in the left hand menu. Please note, in MS Visual Studio it is not possible to include both drivers in the same project, as both will have a main function. You must either:

• Rename main to _main in one of the two driver files, or
• Include only one, implement it appropriately, and then proceed to test it on Unix using both drivers.

Testing Strategies

In this case, there is only one boundary condition: when the list is empty. Each function should be tested with instructions which cause it to manipulate both an empty list and non-empty list.

Look at each function which has an if statement. Try to create a sequence of instructions which cause the conditional statent to evaluate to true. Next, do the same thing, however, create a sequence of instructions which will cause the conditional to evaluate to false.

What are other possible scenerios which could cause your classes to fail?

Testing Example

Rather than immediately starting with a driver such as the Double_sentinel_list_driver.cpp program, it is probably a lot easier to write a small int main() function which you can build up. Each time you implement a function, add a function which tests it.

For example, consider

#include <iostream>
using namespace std;

#include "Double_sentinel_list.h"

int main() {
	Double_sentinel_list<int> list;

	cout << "Size:  " << list.size() << " ( = 0 )" << endl;
	cout << "Empty:  " << list.empty() << " ( = 1 )" << endl;

	// start with 1, then try 2, and then 3, etc.

	const int N = 1;

	for ( int i = 0; i < N; ++i ) {
		list.push_front( i );
	}

	cout << "Front:  " << list.front()
	     << " ( = " << (N - 1) << " )" << endl;
	cout << "Back:  " << list.back() << " ( = 0 )" << endl;
	
	for ( int i = N - 1; i >= 0; --i ) {
		cout << "Pop front: " << list.pop_front()
		     << " ( = " << i << ")" << endl;
	}

	return 0;
}

A smaller routine like this would allow you to make full and effective use of the debugger: you can easily track what is occuring. Notice how I test some of the functions, but not all, based on the order in which I would implement them.

Check List

Have you:

• Have you named the file correctly? (uwuserid_p1.tar.gz where uwuserid is your UW User ID.)
• Are you submitting a gzipped tar file? (Not a rar nor a zip.)
• Is the gzipped file not corrupt?
• Does your submission contain the files mentioned above?

Hints

You will always be using pointers to nodes, and therefore you will always use -> operator and not the . operator. Because the linked-list classes are friends of the appropriate node classes, you can either access the values through the member functions

ptr->retrieve() and ptr->next()

or directly

ptr->element and ptr->next_node

You should only access the node member variables directly (the second method) if you are explicitly changing their value.

When iterating through a linked list, you can iterate through the same way as if you were iterating through an array. For an array, you would use

	for ( int i = 0; i < N; ++i ) {
		// use array[i]
	}

For a linked list, you can do essentially the same thing:

	for (
		Node<Type> *ptr = list_head;
		ptr != 0;
		ptr = ptr->next()
	) {
		// ptr
	}

Note the equivalencies:

	array	linked list
Initialization	int i = 0 The entry array[0] is the first entry in the array.	Node<Type> * ptr = list_head The list head points to the first element.
Test	i < N We know there are N elements in the array.	ptr != 0 The next pointer of the last entry in the linked list is assigned 0.
Increment	++i The next element is in array is at location i + 1	ptr = ptr->next() ptr is pointing to the current node being examined in the linked list, hence ptr->next() returns a pointer to the next element