#include <iostream>
using namespace std;

struct node {
    int data;
    struct node *next;
    struct node *prev;
};

void push(struct node **head_ref, int new_data){
    struct node *new_node = (struct node*) malloc(sizeof(struct node));
    new_node->data = new_data;
    new_node->next = *head_ref;
    new_node->prev = NULL;
    if(*head_ref != NULL){
        (*head_ref)->prev = new_node;
    }
    *head_ref = new_node;
    return;
}

/* Given a node as next_node, insert a new node before the given node */
void insertBefore(struct node** next_node, int new_data){

    // 1. check if the given next_node is NULL
    if(*next_node == NULL){
        cout<<"given node is NULL"<<endl;
        return;
    }
    // 2. allocate new node
    struct node* new_node = (struct node*)malloc(sizeof(struct node));
    // 3. put data in node
    new_node->data = new_data;

    // 4. case: if next_node id head
    if((*next_node)->prev == NULL){
        cout<<"inside into"<<endl;
        (*next_node)->prev = new_node;
         new_node->next = *next_node;
         new_node->prev = NULL;
         // setting new head
         *next_node = new_node;
        return;
    }

    // 5. set new_node's next & prev
    new_node->next =  *next_node;
    new_node->prev = (*next_node)->prev;

    cout<<"(*next_node)->data"<<(*next_node)->data<<endl;

    //*****************?????QUESTION??????****************
    // WHY THIS BELOW CODE CHANGING DATA (*next_node)->data 3 ???
    new_node->prev->next = new_node;

    cout<<"(*next_node)->data"<<(*next_node)->data<<endl;
    (*next_node)->prev = new_node;

    return;
}

void printList(struct node *node)
{
    struct node *last;
    cout<<"nTraversal in forward direction n";
    while (node != NULL)
    {
        cout<<" "<< node->data;
        last = node;
        node = node->next;
    }

    cout<<"nTraversal in reverse direction n";
    while (last != NULL)
    {
        cout<<" "<<last->data;
        last = last->prev;
    }

    return;
}

int main() {

    struct node* head = NULL;
    push(&head, 8);
    push(&head, 4);
    push(&head, 7);
    push(&head, 1);

    // Insert 3, before 7. So linked list becomes 1->3->7->8->4->NULL
    insertBefore(&(head->next), 3);
    cout<<"Created DLL is: ";
    printList(head);

    return 0;
}