//
// 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;
}