// Doubly Linked List.cpp

#include <iostream>
using std::cout;
using std::cin;
using std::endl;

struct Node{
	int data;
	Node* prev;
	Node* next;
};//End of the structure definition

class Doubly_Linked_list{
private:
	Node* HEAD;
public:
	Doubly_Linked_list():HEAD(NULL){}// Initialise the HEAD pointer
	void Insert_at_the_Beginning(int i);
	void Forward_Traverse();
	void Reverse_Traverse();
	~Doubly_Linked_list();
};// End of the class definition

Doubly_Linked_list::~Doubly_Linked_list(){
	cout<<"Destructor Called\nMemory Realesed\n";
	Node* p;
	while(HEAD != NULL){
		p = HEAD;
		HEAD = HEAD->next;
		delete p; 
	}
	HEAD = NULL;  

}
void Doubly_Linked_list::Insert_at_the_Beginning(int i){
	Node* p = new Node; 
	if(p!=NULL){
		
		p->data=i;
		p->prev=NULL;
		p->next=NULL;
		if(HEAD==NULL){
			HEAD=p;
			return;
		}		
		p->next=HEAD;
		HEAD->prev=p;
		HEAD=p;
	}
	else{
		cout<<"Memory Exception Occurred";
		return;
	}
}// End of the function

void Doubly_Linked_list::Forward_Traverse(){
	for(Node* START = HEAD; START!=NULL; START=START->next)	{
		cout<< START->data<<endl; 
		//cout<< START->next<<endl; 
	}
	cout<<endl;
}
// Function  to traverse a doubly linked list in the reverse direction


void Doubly_Linked_list::Reverse_Traverse(){
	Node* END,*CURRENT;
	for(CURRENT = HEAD; CURRENT!=NULL; CURRENT=CURRENT->next);
	
	END = CURRENT;
	
	for(CURRENT = END; CURRENT!=HEAD; CURRENT=CURRENT->prev){
		cout<<CURRENT->data<<endl;
	}
} 

int main(){
	
	Doubly_Linked_list* l = new Doubly_Linked_list();

	l->Insert_at_the_Beginning(10);
	l->Insert_at_the_Beginning(20);
	l->Insert_at_the_Beginning(30);
	l->Insert_at_the_Beginning(50);
	l->Forward_Traverse();
	l->Reverse_Traverse();
	delete l;
return 0;
}