#include <stdio.h>
#include <stdlib.h>


struct Nodes
{
    int value;
    Nodes *prev, *next;
}*head, *tail, *curr;

void pushHead()
{
    curr->next = head;
    head->prev = curr;
    head = curr;
}

void pushTail()
{
    curr->prev = tail;
    tail->next = curr;
    tail = curr;
}


void push(int value)
{
    curr = (Nodes*)malloc(sizeof(Nodes));
    curr->value = value;
    curr->prev = curr->next = NULL;
    if(head == NULL)
    {
        head = tail = curr;
    }
    else if(curr->value<head->value)
    {
        pushHead();
    }
    else if(curr->value>tail->value)
    {
        pushTail();
    }
    else
    {
        Nodes *temp = head;
        while(temp->next->value<curr->value)
        {
            temp = temp->next;
        }
        curr->prev = temp;
        curr->next = temp->next;
        temp->next = curr;
        curr->prev->next = curr;
    }
}

void popHead()
{
    if(head == NULL)
    {
        printf("No data");
        return;
    }
    else if(head == tail)
    {
        curr = head;
        head = tail = NULL;
        free(curr);
    }
    else
    {
        curr = head;
        head = head->next;
        head->prev = NULL;
        free(curr);
    }
}

void popTail()
{
    if(head == NULL)
    {
        printf("No data");
        return;
    }
    else if(head == tail)
    {
        curr = head;
        head = tail = NULL;
        free(curr);
    }
    else
    {
        curr = tail;
        tail = tail->prev;
        tail->next = NULL;
        free(curr);
    }
}

void popMid()
{
}

void print()
{
    curr = head;
    while(curr)
    {
        printf("%d ",curr->value);
        curr = curr->next;
    }
    printf("End Of Data\n");
}

int main()
{
    /*
    printf("Integer : %d\n",sizeof(int));
    printf("Node Pointer : %d\n",sizeof(Nodes*));
    printf("Nodes : %d\n",sizeof(Nodes));
    */
    push(3);
    push(5);
    push(9);
    push(7);
    push(2);
    push(1);
    push(6);
    printf("InitialData : ");
    print();
    popHead();
    printf("\n After popHead : ");
    print();
    printf("\n After popTail : ");
    popTail();
    print();
    getchar();
    return 0;
}