Question
Implement the member function find() of list . find() takes a data element as input and returns an iterator that points to the node that
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. //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
//allow lists and iterators to access members friend class List
///////////node.cpp//////////////
//node.cpp #include "node.h" #include "list.h"
using namespace std;
template
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started