Implement the member function find() of list. find() takes a data element as input and returns an iterator that points to the node that contains the element. If the element is not in the list, the returned iterator points to NULL. This is all the code that was given //list.h #ifndef LIST_H #define LIST_H template class Node; //forward declaration template class listIterator; //forward declaration template class List { protected: Node *first; Node *last; public: //type definition typedef T value_type; typedef listIterator iterator; //constructor and destructor List (); virtual ~List(); //operations bool empty(); int size(); T &front(); //returns first element T &back(); //returns last element void push_front ( T & ); //insert from the front void push_back( T & ); //insert from the back void pop_front(); //remove first element void pop_back(); //remove last element iterator begin(); iterator end(); void sort(); void insert( iterator &, T &); void erase( iterator & ); void erase( iterator &, iterator &); }; template class listIterator { typedef listIterator iterator; protected: List *theList; Node *currentNode; friend class List; public: //constructor listIterator (); listIterator ( List *tl, Node *cl ); T &operator * (); //dereferencing bool operator != ( iterator &rhs ); iterator & operator ++ ( int ); //prefix iterator operator ++ (); //postfix }; #endif 

////////list.cpp//////////////////

//list.cpp #include #include "list.h" #include "node.h" #include

using namespace std;

template List::List() { first = last = 0; //null list }

template bool List::empty() { return first == 0; }

template int List::size() //count the number of elements in collection /* Comments from Tong: This is NOT a good implementation as it takes time to traverse the list. A better way is to include a field called 'size' in the List class; when elements are inserted or deleted, size is adjusted. */ { int count = 0; Node *p; for ( p = first; p != 0; p = p->next ) count++; return count; }

template void List::push_front( T &a ) { Node *newNode = new Node ( a ); if ( empty() ) first = last = newNode; else { first->prev = newNode; newNode->next = first; first = newNode; } }

template void List::pop_front() { Node *temp = first; first = first->next; if ( first != 0 ) first->prev = 0; else last = 0; delete temp; }

template List::~List() { Node *p = first; while ( p != 0 ) { Node *temp = p; p = p->next; delete temp; } }

template listIterator List::begin() { return iterator ( this, first ); }

template listIterator List::end() { return iterator ( this, 0 ); //points beyond last }

//listIterator

//constructors template listIterator::listIterator() { }

template listIterator::listIterator( List *lp, Node *lkp ) { theList = lp; currentNode = lkp; }

template T & listIterator::operator * () { return currentNode->value; }

template bool listIterator::operator != ( iterator &rhs ) { return currentNode != rhs.currentNode; }

template listIterator & listIterator::operator ++ (int) { currentNode = currentNode->next; return *this; }

template listIterator listIterator::operator ++ () //postfix form of increment ( e.g. assigned, then increment ) { //make an old copy listIterator clone ( theList, currentNode ); currentNode = currentNode->next; //advance pointer return clone; //return old iterator }

template void List::insert( listIterator &itr, T &a ) { Node *p = new Node ( a ); Node *current = itr.currentNode;

if ( empty() ) { //empty list first = last = p; return; } //assert ( current ); if ( current == 0 ){ //point to end, thus append to list last->next = p; p->next = 0; p->prev = last; last = p; return; } //otherwise, always insert before p->next = current; p->prev = current->prev; current->prev = p; current = p->prev; if ( current != 0 ) current->next = p; else first = p; }

template void List::erase ( listIterator &start, listIterator &stop ) //remove elements from the range ( before stop ) {

Node *p = start.currentNode; Node *q = p->prev; Node *stopNode = stop.currentNode;

if ( q == 0 ) { //removing initial portion of list first = stopNode; if ( stopNode == 0 ) //pointing to end last = 0; //whole list is deleted else stopNode->prev = 0; } else { q->next = stopNode; if ( stopNode == 0 ) last = q; else stopNode->prev = q; // q->prev = q; }

//now delete the atoms while ( start != stop ) { listIterator next = start; ++next; delete start.currentNode; start = next; } }

/////////////////node.h//////////////

//node.h

#ifndef NODE_H #define NODE_H

template class List; //forward declaration template class listIterator; //forward declaration //a Node is a node ( cell ) template class Node { private: Node ( T &v ); //constructor T value; Node *next; Node *prev;

//allow lists and iterators to access members friend class List; friend class listIterator; }; #endif

///////////node.cpp//////////////

//node.cpp #include "node.h" #include "list.h"

using namespace std;

template Node::Node( T &v ) { value = v; prev = next = 0; }