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