// // this is an example of linked lists using manual insertion, deletion, and iteration // 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; struct Node { char* data; // pointer to an ASCIZ string Node* next; }; // // get the next node // Node* Next (Node* current) { return current->next; } // // inserts a node after the current node and before the next node // returns a pointer to the newly inserted node // Node* Insert (Node* current) { Node* newNode = new Node; newNode->next = current->next; current->next = newNode; return newNode; } // // deletes the current node // void Delete (Node* previous, Node* current) { previous->next = current->next; delete current; } // // prints the list starting at this node // this demonstrates traversing a list from a specific node until the list terminator (0) is found // void PrintFromNode (Node* current) { while (current != 0) { cout << current->data << endl; current = current->next; } cout << endl; } // // program entry // int main() { Node* firstNode = new Node; firstNode->data = "'Twas billig, and the slithy toves"; firstNode->next = 0; // list terminator Node* currentNode = firstNode; currentNode = Insert (currentNode); // create a new node, insert it, and move the current pointer to that node currentNode->data = " Did gyre and gimble in the wabe:"; currentNode = Insert (currentNode); currentNode->data = "All flimsy were the borogoves,"; currentNode = Insert (currentNode); currentNode->data = " And the mome raths outgrabe."; PrintFromNode (firstNode); // the third line has a typo ('flimsy' should be 'mimsy'), so we need to delete it // in order to delete the current node, we must keep track of the previous node as well Node* secondNode = firstNode->next; Node* thirdNode = secondNode->next; Delete (secondNode, thirdNode); // at this point thirdNode is a bad pointer // we want to insert the new line after the second node currentNode = Insert (secondNode); currentNode->data = "All mimsy were the borogoves,"; PrintFromNode (firstNode); return 0; }