#include <iostream>
#include <string>

using namespace std;

template <class T>
class Node {
	T data;
	Node<T> *next;
public:
	Node( T data, Node<T> *next ) : data(data), next(next) {}
	T getData() { return data; }
	Node<T> *getNext() { return next; }
	void setNext( Node<T> *node ) { next = node; }
	//friend LList;
};

template <class T>
class LList {
	Node<T> *head;
public:
	LList() { head = NULL; }
	bool isEmpty() { return head == NULL; }
	void append( T data );
	Node<T> *find( T data );
	void print();
};

template <class T>
void LList<T>::append( T data )
{
	if( isEmpty() ) {
		head = new Node<T>(data, NULL );
	} else {

		Node<T> *n = head;
		while( n->getNext() ) {
			n = n->getNext();
		}

		// for( n=head; n->getNext(); n=n->getNext() );
		/// n = last_node();

		// n is the last node
		n->setNext( new Node<T>( data, NULL ) );

	}
}

template <class T>
void LList<T>::print() 
{
	// use while
	/*
	Node<T> *n = head;
	while( n ) {
		cout << n->getData() << "-->";
		n = n->getNext();
	}
	*/

	// use for
	// for( <initialize> ; <exit condition> ; <step> )

	for( Node<T> *n = head; n; n=n->getNext() ) {
		cout << n->getData() << "-->";
	}
	cout << "NULL" << endl;
}

template <class T>
Node<T> *LList<T>::find( T data )
{
	Node<T> *n = head;
	while( n ) {
		if( n->getData() == data )
			return n;
		n = n->getNext();
	}
	return NULL;
}

int main()
{
	LList<string> list;
	list.append( "Mercury" );
	list.append( "Venus" );
	list.append( "Earth" );
	list.append( "Mar" );
	list.append( "Jupiter" );
	list.append( "Saturn" );
	list.append( "Uranus" );
	list.append( "Naptune" );
	list.print();
	Node<string> *n = list.find( string("Jupiter") );
	cout << n->getData() << endl;
	system("pause");
}