//////////////////////////////////////////////////////////////////////
// linkedlist.h

// declaration of a linked list class

template <typename T>
class ExampleLinkedList
{
public:
	class iterator;
private:
	class ExampleNode
	{
		friend class ExampleLinkedList<T>::iterator;
		friend class ExampleLinkedList<T>;
		ExampleNode *prev;
		T data;
		ExampleNode *next;
	public:
		ExampleNode(T d) {
			prev = NULL;
			next = NULL;
			data = d;
		};
	};
	ExampleNode *head;
	ExampleNode *tail;
	int count;
public:
	class iterator
	{
		ExampleNode *here;
	public:
		friend class ExampleLinkedList<T>;
		iterator() {
			here = NULL;
		};
		iterator(ExampleNode *h) {
			here = h;
		};
		iterator &operator ++() {
			if(here)
				here = here->next;
			return *this;
		};
		iterator operator ++(int) {
			iterator temp = *this;
			++*this;
			return temp;
		};
		iterator &operator --() {
			if(here)
				here = here->prev;
			return *this;
		};
		iterator operator --(int) {
			iterator temp = *this;
			--*this;
			return temp;
		};
		T &operator *() {
			return here->data;
		};
		const T &operator *() const {
			return here->data;
		};

		T *operator ->() {
			return &here->data;
		};
		const T *operator ->() {
			return &here->data;
		};

		bool operator == (const iterator &it) {
			return here == it.here;
		};
		bool operator != (const iterator &it) {
			return here != it.here;
		};
	};
	friend class ExampleLinkedList<T>::iterator;

	ExampleLinkedList() {
		head = tail = NULL;
		count = 0;
	};

	iterator begin() {
		return iterator(head);
	};

	iterator end() {
		return iterator();
	};

	~ExampleLinkedList() {
		clear();
	};

	void push_back(T data) {
		ExampleNode *p = new ExampleNode(data);
		tail->next = p;
		p->prev = tail;
		tail = p;
	};

	void push_front(T data) {
		ExampleNode *p = new ExampleNode(data);
		head->prev = p;
		p->next = head;
		head = p;
	};

	T pop_back() {
		ExampleNode *p = tail->prev;
		T temp = tail->data;
		delete tail;
		tail = p;
		p->next = NULL;
		return temp;
	};

	T pop_front() {
		ExampleNode *p = head->next;
		T temp = head->data;
		delete head;
		head = p;
		p->prev = NULL;
		return temp;
	};

	void insert(iterator it, T data) {
		ExampleNode *p = new ExampleNode(data);
		ExampleNode *q = it.here->next;
		it.here->next = p;
		p->prev = it.here;
		q->prev = p;
		p->next = q;
	};

	T remove(iterator it) {
		it.here->next->prev = it.here->prev;
		it.here->prev->next = it.here->next;
		T temp = it.here->data;
		delete it.here;
		return temp;
	};

	void clear() {
		ExampleNode *p = head;
		while(p) {
			ExampleNode *q = p->next;
			delete p;
			p = q;
		}
	};
};