#include "LinkedList.h" // Construct the list. template LList::LList( ) { header = new LListNode; } // Copy constructor. template LList::LList( const LList & rhs ) { header = new LListNode; *this = rhs; } // Destructor. template LList::~LList( ) { makeEmpty( ); delete header; } // Test if the list is logically empty. // Return true if empty, false, otherwise. template bool LList::isEmpty( ) const { return header->next == NULL; } // Make the list logically empty. template void LList::makeEmpty( ) { while( !isEmpty( ) ) remove( first( ).retrieve( ) ); } // Return an iterator representing the header node. template LListItr LList::zeroth( ) const { return LListItr( header ); } // Return an iterator representing the first node in the list. // This operation is valid for empty lists. template LListItr LList::first( ) const { return LListItr( header->next ); } // Insert item x after p. template void LList::insert( const Object & x, const LListItr & p ) { if( p.current != NULL ) p.current->next = new LListNode( x, p.current->next ); } // Return iterator corresponding to the first node containing an item x. // Iterator isPastEnd if item is not found. template LListItr LList::find( const Object & x ) const { LListNode *p = header->next; while( p != NULL && p->element != x ) p = p->next; return LListItr( p ); } // Return iterator prior to the first node containing an item x. template LListItr LList::findPrevious( const Object & x ) const { LListNode *p = header; while( p->next != NULL && p->next->element != x ) p = p->next; return LListItr( p ); } // Remove the first occurrence of an item x. template void LList::remove( const Object & x ) { LListNode *p = findPrevious( x ).current; if( p->next != NULL ) { LListNode *oldNode = p->next; p->next = p->next->next; // Bypass deleted node delete oldNode; } } // Deep copy of linked lists. template const LList & LList::operator=( const LList & rhs ) { if( this != &rhs ) { makeEmpty( ); LListItr ritr = rhs.first( ); LListItr itr = zeroth( ); for( ; !ritr.isPastEnd( ); ritr.advance( ), itr.advance( ) ) insert( ritr.retrieve( ), itr ); } return *this; }