#include using namespace std; //Def of node template struct nodeType { Type info; nodeType *link; }; // end struct nodeType //Linked list iterator; template class linkedListIterator { public: linkedListIterator(); //default constructor //Pc: current = NULL; linkedListIterator(nodeType *ptr); //constructor with parameter //Pc: current = ptr; Type operator*(); //overload derefrencing(*) operator //Pc: returns info contained in node; linkedListIterator operator++(); //overload preincrement (++) operator //Pc: iterator advances to next node; bool operator==(const linkedListIterator & right) const; //overload equality (==) operator //Pc: returns true if iterator is equal to right, otherwise false; bool operator!=(const linkedListIterator & right) const; //overload not equal (!=) operator //Pc: return true if iterator is not equal to right, otherwise false; private: nodeType *current; //pointer to point to the current node in the linked list; }; // end class linkedListIterator; //linkedListIterator functions def; template linkedListIterator::linkedListIterator() { current = NULL; } template linkedListIterator::linkedListIterator(nodeType *ptr) { current = ptr; } template Type linkedListIterator::operator*() { return current->info; } template linkedListIterator linkedListIterator::operator++() { current = current->link; return *this; } template bool linkedListIterator::operator==(const linkedListIterator & right) const { return (current == right.current); } template bool linkedListIterator::operator!=(const linkedListIterator & right) const { return (current != right.current); } // end linkedListIterator function defs; //class linkedListType; template class linkedListType { public: const linkedListType& operator=(const linkedListType&); //overload assignment(=) operator; void initializeList(); //itialize list to empty state //Pc: first = NULL, last = NULL; count = 0; bool inEmptyList() const; //checks if list is empty //Pc: return true if list is empty, otherwise return false; void print() const; //output data contained in each node //Pc: none; int length() const; //return the number of elements in the list //Pc: return the value of the count; void destroyList(); //delete all nodes from the list //Pc: first = NULL, last = Null, count = 0; Type front() const; //return the first element of the list //Prec: list must exist and not be empty //Pc: if list is empty, program terminates, otherwise return first element of list; Type back() const; //return the last element of the list //Prec: list must exist and not be empty //Pc: if list is empty, program terminates, otherwise return last element of list; virtual bool search(const Type& searchItem) const = 0; //determine whether searchItem is in list //Pc: return true if searchItem is in list, otherwise return false; virtual void insertFirst(const Type& newItem) = 0; //insert newItem in begininng of list //Pc: first points to newItem, newItem inserted at beginning of list, last points to last node, count incremented by 1; virtual void insertLast(const Type& newItem) = 0; //insert newItem in begininng of list //Pc: first points to first node in list, newItem inserted at end of list, last points to newItem, count incremented by 1; virtual void deleteNode(const Type& deleteItem) = 0; //delete deleteItem from list //Pc: if found, node containing deleteItem is deleted from list, first points to first node, last points to last node, count decremented by 1; linkedListIterator begin(); //return an iterator to beginning of list //Pc: return an iterator so current is set to first; linkedListIterator end(); // return an iterator to end of list //Pc: return an iterator so current is set to NULL; linkedListType(); //default constructor //Pc: first = NULL, last = NULL, count = 0; linkedListType(const linkedListType& otherList); //copy constructor ~linkedListType(); //destructor //deletes all nodes fro list //Pc: list object destroyed; protected: int count; //store total number of elements in list; nodeType *first; //pointer to first node in list; nodeType *last; //pointer to the last node of the list; private: void copyList(const linkedListType& otherList); //make a copy of otherList //Pc: a copy of otherList created and assigned to this list; }; // end class linkedListType; //linkedListType functions defs; template const linkedListType& linkedListType::operator=(const linkedListType& otherList) { if (this != &otherList) { copyList(otherList); } return *this; } template void linkedListType::initializeList() { destroyList(); } template bool linkedListType::inEmptyList() const{ return (first == NULL); } template void linkedListType::print() const { nodeType *current; current = first; while (current != NULL) { cout << current->info << " "; current = current->link; } } template int linkedListType::length() const { return count; } template void linkedListType::destroyList() { nodeType *temp; while (first != NULL) { temp = first; first = first->link; delete temp; } last = NULL; count = 0; } template Type linkedListType::front() const { assert(first != NULL); return first->info; } template Type linkedListType::back() const { assert(last != NULL); return last->info; } template linkedListIterator linkedListType::begin() { linkedListIterator temp(first); return temp; } template linkedListIterator linkedListType::end() { linkedListIterator temp(NULL); return temp; } template void linkedListType::copyList(const linkedListType& otherList) { nodeType *newNode; nodeType *current; if(first != NULL) { destroyList(); } if(otherList.first == NULL) { first = NULL; last = NULL; count = 0; } else { current = otherList.first; count = otherList.count; first = new nodeType; first->info = current->info; first->link = NULL; last = first; current = current->link; while (current != NULL) { newNode = new nodeType; newNode->info = current->info; newNode->link = NULL; last->link = newNode; last = newNode; current = current->link; } } } template linkedListType::linkedListType() { first = NULL; last = NULL; count = 0; } template linkedListType::linkedListType(const linkedListType& otherList) { first = NULL; copyList(otherList); } template linkedListType::~linkedListType() { destroyList(); } //end linkedListType function defs; //#ifndef H_unorderedLinkedList //#def H_unorderedLinkedList //class unorderedLinkedList template class unorderedLinkedList: public linkedListType { public: bool search(const Type& searchItem) const; //search for searchItem //Pc: return true if searchItem in list, otherwise false; void insertFirst(const Type& newItem); //insert newItem in the beginning of list //Pc: first points to newItem, newItem inserted in beginning of list, last points to last node, count incremented by one; void insertLast(const Type& newItem); //insert newItem in the beginning of list //Pc: last points to newItem, newItem inserted in end of list, first points to first node, count incremented by one; void deleteNode(const Type& deleteItem); //delete item from list //Pc: if found, node containing deleteItem deleted, first points to first node, last to last node, count decremented by 1; }; //end class unorderedLinkedList //unorderedLinkedList function defs template bool unorderedLinkedList::search(const Type& searchItem) const { nodeType *current; bool found = false; current = this->first; while (current != NULL && !found) { if (current->info == searchItem) { found = true; } else { current = current->link; } } return found; } template void unorderedLinkedList::insertFirst(const Type& newItem) { nodeType *newNode; newNode = new nodeType; newNode->info = newItem; newNode->link = this->first; this->first = newNode; this->count++; if (this->last == NULL) { this->last = newNode; } } template void unorderedLinkedList::insertLast(const Type& newItem) { nodeType *newNode; newNode = new nodeType; newNode->info = newItem; newNode->link = NULL; if (this->first == NULL) { this->first = newNode; this->last = newNode; } else { this->last->link = newNode; this->last = newNode; } this->count++; } template void unorderedLinkedList::deleteNode(const Type& deleteItem) { nodeType *current; nodeType *trailCurrent; bool found; if (this->first == NULL) { cout << "Cannot delete from an empty list." << endl; } else { if (this->first->info == deleteItem) { current = this->first; this->first = this->first->link; if (this->first == NULL) { this->last = NULL; } delete current; this->count--; } else { found = false; trailCurrent = this->first; current = this->first->link; while (current != NULL && !found) { if (current->info != deleteItem) { trailCurrent = current; current = current-> link; } else { found = true; } } //end while if (found) { trailCurrent->link = current->link; if (this->last == current) { this->last = trailCurrent; } delete current; this->count--; } else { cout << "The item to be deleted is not in the list" << endl; } //end else } //end else } //end else } //end deleteItem //end unorderedLinkedList function defs //#endif //#ifndef H_orderedLinkedList //#def H_orderedLinkedList //class orderedLinkedList template class orderedLinkedList: public linkedListType { public: bool search(const Type& searchItem) const; //search for searchItem //Pc: return true if searchItem in list, otherwise false; void insert(const Type& newItem); //insert item into correct position in list //Pc: first points to first node, newItem inserted appropriately, count incremented by 1; void insertFirst(const Type& newItem); //insert newItem in the beginning of list //Pc: first points to newItem, newItem inserted in beginning of list, last points to last node, count incremented by one; void insertLast(const Type& newItem); //insert newItem in the beginning of list //Pc: last points to newItem, newItem inserted in end of list, first points to first node, count incremented by one; void deleteNode(const Type& deleteItem); //delete item from list //Pc: if found, node containing deleteItem deleted, first points to first node, last to last node, count decremented by 1; }; //end class orderedLinkedList //orderedLinkedList function defs template bool orderedLinkedList::search(const Type& searchItem) const { nodeType *current; bool found = false; while (current != NULL && !found) { if (current->info >= searchItem) { found = true; } else { current = current->link; } } if (found) { found = (current->info == searchItem); } return found; } template void orderedLinkedList::insert(const Type& newItem) { nodeType *current; nodeType *trailCurrent; nodeType *newNode; bool found; newNode = new nodeType; newNode->info = newItem; newNode->link = NULL; if (this->first == NULL) { this->first = newNode; this->last = newNode; } else { current = this->first; found = false; while (current != NULL && !found) { if (current->info >= newItem) { found = true; } else { trailCurrent = current; current = current->link; } //end else } //end while if (current == this->first) { newNode->link = this->first; this->first = newNode; } else { trailCurrent->link = newNode; newNode->link = current; if (current == NULL) { this->last = newNode; } } //end else } //end else this->count++; } //end insert template void orderedLinkedList::insertFirst(const Type& newItem) { insert(newItem); } template void orderedLinkedList::insertLast(const Type& newItem) { insert(newItem); } template void orderedLinkedList::deleteNode(const Type& deleteItem) { nodeType *current; nodeType *trailCurrent; bool found; if (this->first == NULL) { cout << "Cannot delete from an empty list." << endl; } else { current = this->first; found = false; while (current != NULL && !found) { if (current->info >= deleteItem) { found = true; } else { trailCurrent = current; current = current->link; } //end else } //end while if (current == NULL) { cout << "The item to be deleted is not in the list." << endl; } else { if (current->info == deleteItem) { if (this->first == current) { this->first = this->first->link; if (this->first == NULL) { this->last = NULL; delete current; } //end if } else { trailCurrent->link = current->link; if (current == this->last) { this->last = trailCurrent; delete current; } } //end else this->count--; } else { cout << "The item to be deleted is not in the list" << endl; }//end else } //end else } //end else } //end deleteItem //end orderedLinkedList function defs //#endif int main() { unorderedLinkedList unlist1, unlist2; int unnum; cout << "Adding: 84, 72, 60, 48, 36, 24, 12, 0 to the unordered list." << endl; for (unnum = 7; unnum >= 0; unnum--) { unnum = unnum*12; unlist1.insertLast(unnum); unnum = unnum/12; } cout << endl; cout << "Printing unordered list1: "; unlist1.print(); cout << endl; cout << endl; cout << "Copying unordered list1 to unordered list2" << endl; unlist2 = unlist1; cout << endl; cout << "unordered List2: "; unlist2.print(); cout << endl; cout << endl; cout << "Deleting 24 from unordered list2" << endl; unlist2.deleteNode(24); cout << endl; cout << "unordered List2: "; unlist2.print(); cout << endl; cout << endl; cout << "unordered List1: "; unlist1.print(); cout << endl; cout << endl; cout << "*******NEW LIST************" << endl; orderedLinkedList list1, list2; int num; cout << "Adding: 77, 66, 55, 44, 33, 22, 11, 0 to the ordered list." << endl; for (num = 7; num >= 0; num--) { num = num*11; list1.insert(num); num = num/11; } cout << endl; cout << "Printing ordered list1: "; list1.print(); cout << endl; cout << endl; cout << "Copying ordered list1 to ordered list2" << endl; list2 = list1; cout << endl; cout << "ordered List2: "; list2.print(); cout << endl; cout << endl; cout << "Deleting 22 from ordered list2" << endl; list2.deleteNode(22); cout << endl; cout << "ordered List2: "; list2.print(); cout << endl; cout << endl; cout << "ordered List1: "; list1.print(); cout << endl; return 0; } // //Pc: ;

LinkedLists