#include <iostream>
#include <string>

using namespace std;

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

template <class T>
class DList {
	Node<T> *head;
	Node<T> *tail;
public:
	DList() { head = NULL; tail=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 );
	void remove( T data );
	int count();
};

template <class T>
void DList<T>::remove( T data ){//
	if( isEmpty() ) return; //ºó ¸®½ºÆ®

	Node<T> *n = head;

	if( n->getData() == data ) { //ù ³ëµå »èÁ¦
		head = n->getNext();
		head->setPrev(NULL);//ù³ëµåÀÇ prev¸¦ NULL·Î
		delete n;
		return;
	}

	while( n->getNext()->getData() != data ) { //N->NEXT°¡ Áö¿ï ´ë»ó
		n = n->getNext();
		
		if( n->getNext() == NULL )
			return;
	}
	Node<T> *prev_node = n;
	Node<T> *found_node = n->getNext();

	prev_node->setNext( found_node->getNext() ); //prev -> nextnext ¿¬°á
	if(found_node->getNext() == NULL){ //nextnext°¡ NULLÀ̸é
		tail = prev_node;
		tail->setNext(NULL);
	}else{
		found_node->getNext()->setPrev( prev_node ); //prev <- nextnext ¿¬°á
	}
	delete found_node;
}

template <class T>
void DList<T>::insert( Node<T> *n, T data ){//
	if(n==NULL) return;
	Node<T> *insert_node = new Node<T>(data, n->getNext() , n ); // n <- insert -> next
	n->setNext(insert_node); //n -> insert
	if( insert_node->getNext() )
		insert_node->getNext()->setPrev(insert_node); //insert <- next
	else
		tail = insert_node;
}

template <class T>
void DList<T>::append( T data ){//
	if( isEmpty() ) {
		Node<T> *append_node = new Node<T>(data, NULL, NULL );
		head = append_node;
		tail = append_node;
	} else {

		tail->setNext(new Node<T>( data, NULL, tail ) );
		tail = tail->getNext();

		/*
		Node<T> *n = head;
		while( n->getNext() ) {
			n = n->getNext();
		}
		n->setNext( new Node<T>( data, NULL, n ) );
		tail = n->getNext();
		*/
	}
}

template <class T>
void DList<T>::prepend( T data ){
	if( isEmpty() ) {
		Node<T> *append_node = new Node<T>(data, NULL, NULL );
		head = append_node;
		tail = append_node;
	}else{
		head = new Node<T>( data, head , NULL );
		head->getNext()->setPrev(head);
	}
 }

template <class T>
void DList<T>::print(){
	if(isEmpty()) {cout<<"Empty"<<endl; return;}
	for( Node<T> *n = head; n; n=n->getNext() ) {
		cout << n->getData() << " <--> ";
	}
	cout << "NULL" << endl;
}

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

template <class T>
int DList<T>::count(){ //TailºÎÅÍ ¿ª¼øÀ¸·Î Ä«¿îÆ®
	int count=0;

	//for( Note<T> *n=head; n; n=n->getNext() ) 
	//	count++;

	Note<T> *n = head;
	whilte( n ) {
		n = n->getNext();
		count++;
	}

	return count;

	/*
	if(isEmpty()) return count;
	count=1;
	Node<T> *n = tail;
	while(n->getPrev() != NULL){
		count++;
		n= n->getPrev();
	}
	return count;
	*/
}

void main() {
	DList<string> list;

	list.print();

	list.append("1");
	list.append("2");
	list.append("4");
	list.print();
	cout<< "Dlist has "<< list.count() <<" Nodes"<<endl<<endl;

	list.insert(list.find("2"),"3");
	list.print();
	cout<< "Dlist has "<< list.count() <<" Nodes"<<endl<<endl;

	list.remove("3");
	list.print();
	cout<< "Dlist has "<< list.count() <<" Nodes"<<endl<<endl;
	
	list.prepend("0");
	list.print();
	cout<< "Dlist has "<< list.count() <<" Nodes"<<endl<<endl;

	system("pause");
}