// sample program with insertion and traversal on a simple linked list with only a head ptr

#include <iostream>

using namespace std;

struct NodeType
{
	int i;
	NodeType *Next;
};

NodeType *Head;

void Initialize ()
{
	Head = NULL;
}

void Output ()
{
	NodeType *p = Head;
	while (p != NULL)
	{
		cout << p->i << "\n";
		p = p->Next;
	}
}

void InsertHead ( NodeType *n )
{
	n->Next = Head;
	Head = n;
}

void InsertTail ( NodeType *n )
{
	if (Head == NULL) // empty list case
	{
		n->Next = Head;
		Head = n;
	}
	else // non-empty list
	{
		NodeType *Tail = Head;
		while (Tail->Next != NULL)
			Tail = Tail->Next;
		Tail->Next = n;
		n->Next = NULL;
	}
}

int main ()
{
	Initialize ();

	NodeType *aNode;

	aNode = new NodeType;
	aNode->i = 4;
	InsertHead (aNode);

	aNode = new NodeType;
	aNode->i = 5;
	InsertTail (aNode);

	aNode = new NodeType;
	aNode->i = 3;
	InsertHead (aNode);

	aNode = new NodeType;
	aNode->i = 6;
	InsertTail (aNode);

	aNode = new NodeType;
	aNode->i = 2;
	InsertHead (aNode);

	aNode = new NodeType;
	aNode->i = 7;
	InsertTail (aNode);

	aNode = new NodeType;
	aNode->i = 1;
	InsertHead (aNode);

	aNode = new NodeType;
	aNode->i = 8;
	InsertTail (aNode);

	Output ();

	return 0;
}