Help with Linked List template testing

[tegi00]

We're supposed to test a linked list class template that is provided for us but I'm having trouble figuring out how to test a couple of the functions.

Here is the linked list template .h file.

#ifndef LinkedList_h
#define LinkedList_h

#include <iostream>
using namespace std;

// LinkedList.h -- class for a linked list as a data structure

template <class DataType>
struct Node
{
	DataType data;
	Node<DataType> *next;
};

template <class DataType>
class LinkedList
{
public:
	LinkedList();
	LinkedList (const LinkedList<DataType> & aplist);
	~LinkedList();
	LinkedList<DataType> & operator = (const LinkedList<DataType> & rlist);
	void insert (const DataType & element); // no current position after use
	bool first (DataType & listEl);	  // returns first element of list in listEl
	inline bool getNext (DataType & listEl);	  // retrieves the next element of a linked list
	bool find (const DataType & element);  // returns true if element is found
	bool retrieve (DataType & element);  // like find, except returns found element
	bool replace (const DataType & newElement); // replaces element at current position
	bool remove (DataType & element);    // returns true if element is found
	bool isEmpty() const;				  // returns true if linked list is empty
	void makeEmpty();					  // no current position
private:
	Node<DataType> *start;
	Node<DataType> *current;			  // points to node at current position
	inline void deepCopy (const LinkedList<DataType> & original);
};

template <class DataType>
LinkedList<DataType>::LinkedList()
: start(0), current(0) {}

template <class DataType>
LinkedList<DataType>::LinkedList (const LinkedList<DataType> & aplist)
{
	deepCopy( aplist );
}

template <class DataType>
LinkedList<DataType>::~LinkedList()
{
	makeEmpty( );
}

template <class DataType>
LinkedList<DataType> & LinkedList<DataType>::operator = (const LinkedList<DataType> & rlist)
{
	if (this == &rlist)
		return *this;
	makeEmpty();
	deepCopy (rlist);
	return *this;
}

// inserts at the beginning of the linked list
// no current position after use
template <class DataType>
void LinkedList<DataType>::insert(const DataType& parameter) // O(1)
{
  current = 0;
  Node<DataType>* node = new Node<DataType>;
  node->data = parameter;
  node->next = start;
  start = node;
}

template <class DataType>
bool LinkedList<DataType>::first(DataType& parameter) // O(1)
{
  if (!start) return false;
  parameter = start->data;
  current = start;
  return true;
}

template <class DataType>
bool LinkedList<DataType>::getNext(DataType& parameter) // O(1)
{
  if (!current) return false;
  current = current->next;
  if (!current) return false;
  parameter = current->data;
  return true;
}

template <class DataType>
bool LinkedList<DataType>::find(const DataType& parameter) // O(n)
{
  DataType temp;
  if (first(temp)) do
  {
    if (parameter == temp) return true; // found it
  } while (getNext(temp));
  return false; // no match
}

template <class DataType>
bool LinkedList<DataType>::retrieve(DataType& parameter) // O(n)
{
  if (!find(parameter)) return false;
  parameter = current->data; // set in find
  return true;
}

template <class DataType>
bool LinkedList<DataType>::replace(const DataType& parameter) // O(1)
{
  if (!current) return false;
  current->data = parameter;
  return true;
}

template <class DataType>
bool LinkedList<DataType>::remove(DataType& parameter) // O(n)
{
  // find node to remove
  Node<DataType>* p;
  Node<DataType>* prev;
  for (prev = 0, p = start; p; prev = p, p = p->next)
    if (p->data == parameter)
      break;
  
  // deallocate node here
  if (!p) return false; // no match
  if (prev) prev->next = p->next; else start = p->next;
  if (p == current) current = current->next;
  parameter = p->data;
  delete p;
  return true;
}

template <class DataType>
bool LinkedList<DataType>::isEmpty() const // O(1)
{
  return start == 0;
}

template <class DataType>
void LinkedList<DataType>::makeEmpty() // O(n)
{
  while (start)
  {
    current = start->next;
    delete start;
    start = current;
  } }

template <class DataType>
inline void LinkedList<DataType>::deepCopy( const LinkedList<DataType> & original )
{
	start = current = NULL;
	if ( original.start == NULL )
		return;
	Node<DataType> *copyptr = start = new Node<DataType>;
	Node<DataType> *originalptr = original.start;
	copyptr->data = originalptr->data;
	if ( originalptr == original.current )
		current = copyptr;
	while ( originalptr->next != NULL ) {
		originalptr = originalptr->next;
		copyptr->next = new Node<DataType>;
		copyptr = copyptr->next;
		copyptr->data = originalptr->data;
		if ( originalptr == original.current )
			current = copyptr;
	}
	copyptr->next = NULL;
}
  
#endif 

Here is my Linked List test driver .cpp file. In the past I used assertion tests to determine all of my functions are working. The insert, isEmpty, makeEmpty functions were easy to test but the other ones I'm not sure if I'm going about testing them correctly. I'm on testing the get first function which get the first value and set "current" to its node. How would I go about doing an assertion test for this?

#include "LinkedList.h"
#include "LinkedList.h" // to test #ifndef
#include <cassert>
using namespace std;

int main()
{  
  LinkedList <int> a; // test obj
  int var;
  
  // testing constructor
  assert (a.isEmpty() == true);
  cout << "Constructor working successfully" << endl;
  
  a.insert(5);
  a.insert(6);
  
  assert (a.isEmpty() == false);
  cout << "Insert working successfully" << endl;

  a.makeEmpty();
  assert(a.isEmpty() == true);
  cout << "makeEmpty working successfully" << endl;
  
  a.insert(7);
  assert(a.isEmpty() == false);
  
  a.first(var); // get first value and set "current" to its node
}

[Albatross]

You need to test for two conditions with first(): when the list is empty, and when it isn't. You seem to return everything by reference (which is somewhat unorthodox), so keep track of what the value of the first element should be, call first, and compare the value that you get out of it. Then empty the list and check if first() reports that it failed.

Speaking more generally, what you could do is make a list for each function of all the conditions you might face when calling it (ex. calling remove() when the list is empty, for a data value that exists, and for a data value that does not exist). From there, the tests shouldn't be too hard to construct if you always keep in mind the results you're expecting from each case.

-Albatross