#include <iostream>
using namespace std;

class LList {
public:
	LList() :head(0), tail(0) {}  
	~LList() {
		Node * cur = head;
		while (cur) {
			cur = cur->next;
			delete head;
			head = cur;
		}
	}	
	void insert(int val) {
	  if (!tail) {
	    head=tail=new Node(val);
	  }
	  else {
	    tail->next=new Node(val, 0, tail);
	    tail=tail->next;
	  }
	}	
	void printReverse() const;
	bool remove(int val);	

private:
	struct Node {
		Node(int d, Node *n = 0, Node *p = 0) : data(d), next(n), prev(p) {}
		int data;
		Node *next, *prev;
	};
	Node * head, *tail;
};


bool LList::remove(int val){
	Node * curr = tail;

	while (curr != NULL && curr->data != val){
		curr = curr->prev;
	}
	if (curr == NULL)return false;
	if (curr == head)
		head = head->next;
	else
		curr->prev->next = curr->next; 

	if (curr == tail)
		tail = tail->prev;
	else
		curr->next->prev = curr->prev; 

	delete curr;
	return true;
}


void LList::printReverse()const{
	Node * curr = tail;
	while (curr){
		cout << curr->data << endl;
		curr = curr->prev;
	}
}

//Test
void main(){
	LList hello;
	hello.insert(1);
	hello.insert(2);
	hello.insert(3);
	hello.printReverse();//prints 123
	hello.remove(2);
	hello.printReverse();//prints 13
	hello.remove(3);
	hello.printReverse();//prints 1
	hello.remove(1);
	hello.printReverse();//prints NOTHING 
}