#ifndef H_LinkedListType #define H_LinkedListType #include <iostream> #include <cassert> using namespace std; //Definition of the node template <class type=""> struct nodeType { Type info; nodeType<type> *link; }; template <class type=""> class linkedListIterator { public: linkedListIterator(); //Default constructor //Postcondition: current = NULL; linkedListIterator(nodeType<type> *ptr); //Constructor with a parameter. //Postcondition: current = ptr; Type operator*(); //Function to overload the dereferencing operator *. //Postcondition: Returns the info contained in the node. linkedListIterator<type> operator++(); //Overload the pre-increment operator. //Postcondition: The iterator is advanced to the next // node. bool operator==(const linkedListIterator<type>& right) const; //Overload the equality operator. //Postcondition: Returns true if this iterator is equal to // the iterator specified by right, // otherwise it returns the value false. bool operator!=(const linkedListIterator<type>& right) const; //Overload the not equal to operator. //Postcondition: Returns true if this iterator is not // equal to the iterator specified by // right; otherwise it returns the value // false. private: nodeType<type> *current; //pointer to point to the current //node in the linked list }; template <class type=""> linkedListIterator<type>::linkedListIterator() { current = NULL; } template <class type=""> linkedListIterator<type>:: linkedListIterator(nodeType<type> *ptr) { current = ptr; } template <class type=""> Type linkedListIterator<type>::operator*() { return current->info; } template <class type=""> linkedListIterator<type> linkedListIterator<type>::operator++() { current = current->link; return *this; } template <class type=""> bool linkedListIterator<type>::operator== (const linkedListIterator<type>& right) const { return (current == right.current); } template <class type=""> bool linkedListIterator<type>::operator!= (const linkedListIterator<type>& right) const { return (current != right.current); } //***************** class linkedListType **************** template <class type=""> class linkedListType { public: const linkedListType<type>& operator= (const linkedListType<type>&); //Overload the assignment operator. void initializeList(); //Initialize the list to an empty state. //Postcondition: first = NULL, last = NULL, count = 0; bool isEmptyList() const; //Function to determine whether the list is empty. //Postcondition: Returns true if the list is empty, // otherwise it returns false. void print() const; //Function to output the data contained in each node. //Postcondition: none int length() const; //Function to return the number of nodes in the list. //Postcondition: The value of count is returned. void destroyList(); //Function to delete all the nodes from the list. //Postcondition: first = NULL, last = NULL, count = 0; Type front() const; //Function to return the first element of the list. //Precondition: The list must exist and must not be // empty. //Postcondition: If the list is empty, the program // terminates; otherwise, the first // element of the list is returned. Type back() const; //Function to return the last element of the list. //Precondition: The list must exist and must not be // empty. //Postcondition: If the list is empty, the program // terminates; otherwise, the last // element of the list is returned. virtual bool search(const Type& searchItem) const = 0; //Function to determine whether searchItem is in the list. //Postcondition: Returns true if searchItem is in the // list, otherwise the value false is // returned. virtual void insertFirst(const Type& newItem) = 0; //Function to insert newItem at the beginning of the list. //Postcondition: first points to the new list, newItem is // inserted at the beginning of the list, // last points to the last node in the list, // and count is incremented by 1. virtual void insertLast(const Type& newItem) = 0; //Function to insert newItem at the end of the list. //Postcondition: first points to the new list, newItem // is inserted at the end of the list, // last points to the last node in the list, // and count is incremented by 1. virtual void deleteNode(const Type& deleteItem) = 0; //Function to delete deleteItem from the list. //Postcondition: If found, the node containing // deleteItem is deleted from the list. // first points to the first node, last // points to the last node of the updated // list, and count is decremented by 1. linkedListIterator<type> begin(); //Function to return an iterator at the begining of the //linked list. //Postcondition: Returns an iterator such that current is // set to first. linkedListIterator<type> end(); //Function to return an iterator one element past the //last element of the linked list. //Postcondition: Returns an iterator such that current is // set to NULL. linkedListType(); //default constructor //Initializes the list to an empty state. //Postcondition: first = NULL, last = NULL, count = 0; linkedListType(const linkedListType<type>& otherList); //copy constructor ~linkedListType(); //destructor //Deletes all the nodes from the list. //Postcondition: The list object is destroyed. void reversePrint() const; protected: int count; //variable to store the number of //elements in the list nodeType<type> *first; //pointer to the first node of the list nodeType<type> *last; //pointer to the last node of the list private: void copyList(const linkedListType<type>& otherList); //Function to make a copy of otherList. //Postcondition: A copy of otherList is created and // assigned to this list. void recursiveReversePrint(nodeType<type> *current) const; }; template <class type=""> bool linkedListType<type>::isEmptyList() const { return(first == NULL); } template <class type=""> linkedListType<type>::linkedListType() { //default constructor first = NULL; last = NULL; count = 0; } template <class type=""> void linkedListType<type>::destroyList() { nodeType<type> *temp; //pointer to deallocate the memory //occupied by the node while (first != NULL) { //while there are nodes in the list temp = first; //set temp to the current node first = first->link; //advance first to the next node delete temp; //deallocate the memory occupied by temp } last = NULL; //initialize last to NULL; first has already //been set to NULL by the while loop count = 0; } template <class type=""> void linkedListType<type>::initializeList() { destroyList(); //if the list has any nodes, delete them } template <class type=""> void linkedListType<type>::print() const { nodeType<type> *current; //pointer to traverse the list current = first; //set current so that it points to //the first node while (current != NULL) { //while more data to print cout << current->info << " "; current = current->link; } }//end print template <class type=""> int linkedListType<type>::length() const { return count; } //end length template <class type=""> Type linkedListType<type>::front() const { assert(first != NULL); return first->info; //return the info of the first node }//end front template <class type=""> Type linkedListType<type>::back() const { assert(last != NULL); return last->info; //return the info of the last node }//end back template <class type=""> linkedListIterator<type> linkedListType<type>::begin() { linkedListIterator<type> temp(first); return temp; } template <class type=""> linkedListIterator<type> linkedListType<type>::end() { linkedListIterator<type> temp(NULL); return temp; } template <class type=""> void linkedListType<type>::copyList (const linkedListType<type>& otherList) { nodeType<type> *newNode; //pointer to create a node nodeType<type> *current; //pointer to traverse the list if (first != NULL) //if the list is nonempty, make it empty destroyList(); if (otherList.first == NULL) { //otherList is empty first = NULL; last = NULL; count = 0; } else { current = otherList.first; //current points to the //list to be copied count = otherList.count; //copy the first node first = new nodeType<type>; //create the node first->info = current->info; //copy the info first->link = NULL; //set the link field of //the node to NULL last = first; //make last point to the //first node current = current->link; //make current point to //the next node //copy the remaining list while (current != NULL) { newNode = new nodeType<type>; //create a node newNode->info = current->info; //copy the info newNode->link = NULL; //set the link of //newNode to NULL last->link = newNode; //attach newNode after last last = newNode; //make last point to //the actual last node current = current->link; //make current point //to the next node }//end while }//end else }//end copyList template <class type=""> linkedListType<type>::~linkedListType() { //destructor destroyList(); }//end destructor template <class type=""> linkedListType<type>::linkedListType (const linkedListType<type>& otherList) { first = NULL; copyList(otherList); }//end copy constructor //overload the assignment operator template <class type=""> const linkedListType<type>& linkedListType<type>::operator= (const linkedListType<type>& otherList) { if (this != &otherList) { //avoid self-copy copyList(otherList); }//end else return *this; } #endif
var
This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)