#include <iostream>
#include <cstdlib>
using namespace std;


typedef struct element{
	int key;
	struct element *next;
	struct element *prev;
}node;

node *head=NULL;
node *tail=NULL;

void addhead(node **head,node **tail, int key){
	node *nowa =(node*)malloc(sizeof(node));
	nowa->key=key;
	nowa->next=NULL;
	nowa->prev=NULL;
	if(*head == NULL){
		*head = nowa;
		*tail = nowa;
	}else{
		(*head)->prev=nowa;
		nowa->next = *head;
		*head = nowa;
	}
}
void addtail(node **head, node**tail, int key){
	node *nowa = (node*)malloc(sizeof(node));
	nowa->key=key;
	nowa->next = NULL;
	nowa->prev = NULL;

	if(*tail == NULL){
		*head = nowa;
		*tail = nowa;
	}else{
		(*tail)->next = nowa;
		nowa->prev = *tail;
		*tail = nowa;
	}
}

void printListFromHead(node *head){
	if(head!=NULL){
		cout << head->key << " ";
		printListFromHead(head->next);
	}
}

void printListFromTail(node *head){
	if(head!=NULL){
		printListFromTail(head->next);
		cout << head->key << " ";
	}
}

unsigned int listSize(node *head){
	unsigned int size = 0;
	while(head!=NULL){
		size++;
		head = head->next;
	}
	return size;
}

void removeHead(node **head, node **tail){
	if(*head!=NULL){
		if(*head == *tail){
	    *head = NULL;
	    *tail = NULL;
        }else{
		node *tmp = *head;
		(*head) = (*head)->next;
		if(*head!=NULL){
			(*head)->prev = NULL;
		}
		free(tmp);
	    }
	}
}

void removeTail(node **head, node **tail){
	if(*tail!=NULL){
		if(*tail == *head){
			*tail = NULL;
			*head = NULL;
		}else{
		    node *tmp = *tail;
		    (*tail) = (*tail)->prev;
		    if(*tail!=NULL){
			  (*tail)->next = NULL;
		    }
	        free(tmp);
	    }
	}
}



int main(){
 	int rando;
 	for(int i=0; i<5; i++){
 		rando = rand()%100+1;
 		addhead(&head,&tail,rando);
 		rando = rand()%100+1;
 		addtail(&head,&tail,rando);
 	}
 	cout << "List printed from head: " << endl;
 	printListFromHead(head);
 	cout << endl;
 	cout << "List printed from tail: " << endl;
 	printListFromTail(head);
 	cout << endl;
 	cout << "Number of elements in list: "<< listSize(head);
 	cout << endl;
 	for(int i = 0; i < 3; i++){
 		removeHead(&head, &tail);
 		removeTail(&head, &tail);
 	}
 	printListFromHead(head);
}