////////list.cpp////////////////// //list.cpp #include #include \"list.h\" #incl

Question

////////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;
}

Explanation / Answer

This is the function for finding the value in the list and return the iterator position that will point the node location.

We have created one function with returntype of iterator that currentnode locattion will point to the find element position. We have pass two arguments, one is for the start pointer of iterator and second the value that we have to search. So we have started a for loop from the starting position of list till the list will not empty or found an element.

iterator List::find ( listIterator &start, T &f)
//find element from the list and return iterator.
{

             Node *p = start.currentNode;

         for ( ; p != 0; p = p->next )

             {
                                if(p-> == f)

                                           return list;

              }

              return list;
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.