#ifndef LINKED_LIST
#define LINKED_LIST
#include <iostream>
using namespace std;

template<class T>
class Node{
public:
	T data;
	Node* next;
	Node(T d, Node* n):data(d),next(n){}
};

template<class T>
class LinkedList{

public:
	Node<T>* head;
	LinkedList():head(0){}
	void deleteNode(T d){
		if(!head){
			cout << d << " not in empty list " << endl;  
			return;
		}
		Node<T>* prev = 0;
		Node<T>* curr = head;
		while(d != curr->data && curr->next ){
			prev = curr;
			curr = curr->next;
		}

		// delete at beginning of list
		if(!prev){
			Node<T>* temp = head;
			head = head->next;
			delete temp;
		}

		// delete at end of list
		else if(!curr->next){
			Node<T>* temp = curr;
			prev->next = 0;
			delete temp;
		}

		// delete in middle of list
		else {
			Node<T>* temp = curr;
			prev->next = curr->next;
			delete temp;
		}
	}
	void add(T d){
		if(!head){
			head = new Node<T>(d,0); 
			return;
		}
		Node<T>* prev = 0;
		Node<T>* curr = head;
		while(d > curr->data && curr ){
			prev = curr;
			curr = curr->next;
			if(!curr)break;
		}

		// insert at beginning at list
		if(!prev){
			head = new Node<T>(d, head);
		}

		// insert at end
		else if(!curr){
			prev->next = new Node<T>(d, 0);
		}

		// insert in middle
		else{
			prev->next = new Node<T>(d, curr);
		}
	}

	bool empty(){
		return !head;
	}

	~LinkedList(){
		Node<T> *curr = head;
		Node<T> *temp;
		cout << "in d-tor" << endl;
		while(curr){
			cout << " deleting at " << curr << endl;
			temp = curr;
			curr = curr->next;
			delete temp;
		}
	}
	friend ostream& operator << (ostream o, LinkedList const &L);
};

template <class T>
ostream& operator << (ostream &o, LinkedList<T> const &L){
	Node<T> *curr = L.head;
	if(!L.head){o << "empty list" << endl; return o;}
	o << endl << "Linked List: " << endl << endl;
	while(curr){
		o << curr->data << endl;
		curr = curr->next;
	}
	o << endl;
	return o;
}

#endif