A) Linked list implementation

The following is a simplified implementation of linked list and a demonstration of its usage.

list.h node.h list.cpp node.cpp list_demo.cpp Makefile.list

Copy and examine the files. Compile and test them.

THE QUESTIONS ARE LISTED BELOW: (1 & 2)

1. Wrtie a demo function to illustrate the use of all the implemented lists and iterator member functions, including empty(), size(), insert(), erase(), ++, *, pop_front() ..... Check if there're any bugs in the implementation. Fix them if you find any.

2. 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 

------------------------------------------------------------------

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

----------------------------------------------------------------------

//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.cpp #include "node.h" #include "list.h" using namespace std; template Node::Node( T &v ) { value = v; prev = next = 0; } 

-----------------------------------------------------------

//list_demo.cpp /* Because of the use of template when defining the List and node classes, unfortunately, we do need to include the .cpp files here for the current compilers. */ #include #include "list.cpp" #include "node.cpp" using namespace std; template void print_list( List &aList ) { typename List::iterator start, stop; start = aList.begin(); stop = aList.end(); while ( start != stop ){ cout << *start << ",\t"; ++start; } cout << endl; } int main() { typedef double T; List aList; //a list T n; while ( true ) { cout << "Enter a number, -99 to terminate: "; cin >> n; if ( n == -99 ) break; aList.push_front( n ); //insert into list at front } //while cout << "You have entered the list: " << endl; print_list( aList ); return 0; } 

-----------------------------------------------------------------------------------

#Makefile EXEC=list_demo SRCS=list.cpp node.cpp list_demo.cpp OBJS=$(SRCS:.cpp=.o) $(EXEC): $(OBJS) g++ -o $@ $(OBJS) #$< evaluates to the target's dependencies, #$@ evaluates to the target $(OBJS): g++ -c $*.cpp clean: rm $(OBJS)