// // this is an example of linked lists using an iterator class. // the test data is from the poem Jabberwocky by Lewis Carroll. // // Written by Maxwell Sayles, 2001, for CPSC331, University of Calgary. // #include using namespace std; // // class/structure declarations // struct Node; class Iterator; class List; // // class/structure definitions and member declarations // // linked list nodes struct Node { char* data; // pointer to an ASCIZ string Node* next; }; // list iterator // this iterator keeps track of the current and previous node, to allow for deleting of the current node class Iterator { public: Iterator (List* list); bool HasMore(); char* Item(); void Next(); void Insert (char* string); void Delete(); private: List* list; Node* currentNode; Node* previousNode; }; // list class class List { friend Iterator; public: List(); ~List(); void Prepend (char* string); Iterator Iterate(); private: Node* firstNode; }; // // create an iterator from a list // Iterator::Iterator (List* list) { this->list = list; this->currentNode = list->firstNode; this->previousNode = 0; } // // return true if there are more items in the list to iterate through // bool Iterator::HasMore() { return (this->currentNode != 0); } // // return the item the iterator currently points to // char* Iterator::Item() { return this->currentNode->data; } // // move the iterator to the next item // void Iterator::Next() { this->previousNode = this->currentNode; this->currentNode = this->currentNode->next; } // // creates a new node // inserts the node into the list immediately before current node // set the current node to the new node // void Iterator::Insert (char* string) { Node* newNode = new Node; newNode->data = string; newNode->next = this->currentNode; // link the new node to this->current // are we inserting at the beginning of the list? if (this->currentNode == this->list->firstNode) { // link first node of list to newNode this->list->firstNode = newNode; } else { // link previous node to newNode this->previousNode->next = newNode; } this->currentNode = newNode; } // // delete the node currently pointed to // point to the next node in the list // void Iterator::Delete() { // does the currentNode point to the firstNode in the list? if (this->currentNode == this->list->firstNode) { // link first node in list to next node this->list->firstNode = this->currentNode->next; } else { // link previous node to next node this->previousNode->next = this->currentNode->next; } Node* nextNode = this->currentNode->next; delete this->currentNode; this->currentNode = nextNode; } // // construct an empty list // List::List() { this->firstNode = 0; } // // go through each node and delete it // List::~List() { Node* n = this->firstNode; while (n != 0) { Node* next = n->next; delete n; n = next; } } // // prepend a string onto the beginning of the list // void List::Prepend (char* string) { Node* newNode = new Node; newNode->data = string; newNode->next = this->firstNode; this->firstNode = newNode; } // // create a list iterator // Iterator List::Iterate() { return Iterator (this); } // // print the list // void PrintList (List& list) { Iterator iter = list.Iterate(); while (iter.HasMore()) { cout << iter.Item() << endl; iter.Next(); } cout << endl; } // // program entry // int main() { List list; // prepend lines of Jaberwocky into the list // the lines are prepended in reverse order, because each new line is put on the front of the list list.Prepend (" And the mome raths outgrabe."); list.Prepend ("All flimsy were the borogoves,"); list.Prepend (" Did gyre and gimble in the wabe:"); list.Prepend ("'Twas brillig, and the slithy toves"); PrintList (list); // the third line has a typo ('flimsy' should be 'mimsy'), so we need to delete it Iterator iter = list.Iterate(); // iter points to first line iter.Next(); // iter points to second line iter.Next(); // iter points to third line iter.Delete(); // delete the third line iter.Insert ("All mimsy were the borogoves,"); // insert the correct line PrintList (list); return 0; }