#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();
	void insert( Node<T> *n, T data );
	void prepend( T data ) { head = new Node<T>( data, head ); }
	void remove( T data );
};


template <class T>
void LList<T>::remove( T data )
{
	// find the previous node to data
	Node<T> *n = head;
	// CORNER-CASE 1: if list is empty
	if( isEmpty() ) return;
	// CORNER-CASE 2: if the first node is to be deleted
	if( n->getData() == data ) {
		head = n->getNext();
		delete n;
		return;
	}
	// NORMAL CASE
	while( n->getNext()->getData() != data ) {
		n = n->getNext();
		// CORNER-CASE 3: if the data is not found
		if( n->getNext() == NULL )
			return;
	}
	/*
	while() {
		Node<T> *next_node = n->getNext();
		if( !next_node ) return;
		if( next_node->getData() == data )
			break;
		n = n->getNext();
	}
	*/
	Node<T> *prev_node = n;
	Node<T> *found_node = n->getNext();

	// remove the node
	prev_node->setNext( found_node->getNext() );

	// deallocate the memory
	delete found_node;
}

template <class T>
void LList<T>::insert( Node<T> *n, T data )
{
	n->setNext(new Node<T>(data, n->getNext() ));
}

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( "Mars" );
	//list.append( "Jupiter" );
	list.append( "Saturn" );
	list.append( "Uranus" );
	list.append( "Naptune" );
	list.append( "Pluto" );
	list.print();

	Node<string> *n = list.find( string("Mars") );
	//cout << n->getData() << endl;
	list.insert( n, "Jupiter" );
	// list.insert( list.find( string("Mars") ), "Jupiter" );
	list.print();

	list.prepend( "Sun" );
	list.print();

	list.remove("Sun");
	list.print();

	system("pause");
}