/* These are generic Functions for a Generic List
 * Note:-Only Functions not including a Menu and an Interface
 * You could use these Functions for your own Benefit*/
#include <iostream>
using namespace std;
template <class X> struct node{   //Template Structure
	X data;
	node* next;
	node* prev;
};
 
template <class Y> void insert_first(node<Y>** l,Y elem) 
{
	node<Y>* Q=new node<Y>();
	Q->data=elem;
	Q->prev=NULL;
	Q->next=*l;
	*l=Q;
}
template <class Y> void print_l(node<Y>* l)//Print the List
{
	while(l!=NULL)
	{
		cout<<l->data<<"   ";
		l=l->next;
	}
}
template <class type> int count(node<type>* l)//Count the List
{
	int counter=0;
	while(l!=NULL)
	{
		counter++;
		l=l->next;
	}
	return counter;
}
 
template <class type> void append(node<type>** l,type elem)
{
	if(*l==NULL)
		insert_first(&*l,elem);
	else
	{
		node<type>*temp=*l;
		node<type> *Q=new node<type>;
		Q->data=elem;
		while(temp->next!=NULL)
		{
			temp=temp->next;
		}
		temp->next=Q;
		Q->prev=temp;
	}
}
template <class type> 
void insert_at_pos(node<type> **l,int pos,type elem)
{
	if(pos<=0||pos>count(*l))
	{
		cout<<"Invalid Position"<<endl;
		exit(1);
	}
	node<type>* Q=new node<type>;
	node<type>* temp=*l;
	int i=2;
	if(pos==1)
	{
		insert_first(&*l,elem);
	}
	else
	{
		while(temp!=NULL)
		{
			if(pos==i)
			{
				Q->data=elem;
				Q->next=temp->next;
				Q->prev=temp;
				temp->next=Q;
			}
			i++;
			temp=temp->next;
		}
	}
}
 
int main(int argc, char** argv)
{
	node<int>* q=NULL;//Create Empty Pointer that Will point to the Head of the List
	insert_first(&q,2);
	insert_at_pos(&q,2,2);
	return 0;
}