#include <stdio.h>

#include <stdlib.h>

struct Node {

    int data;

    struct Node* prev;

    struct Node* next;

};

struct Node* createNode(int data) {

    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));

    if (newNode == NULL) {

        printf("Memory allocation failed.\n");

        exit(1);

    }

    newNode->data = data;

    newNode->prev = NULL;

    newNode->next = NULL;

    return newNode;

}

void displayForward(struct Node* head) {

    struct Node* current = head;

    while (current != NULL) {

        printf("%d -> ", current->data);

        current = current->next;

    }

    printf("NULL\n");

}

void displayBackward(struct Node* tail) {

    struct Node* current = tail;

    while (current != NULL) {

        printf("%d -> ", current->data);

        current = current->prev;

    }

    printf("NULL\n");

}

void insertBetween(struct Node* prevNode, struct Node* nextNode, int data) {

    struct Node* newNode = createNode(data);

    newNode->prev = prevNode;

    newNode->next = nextNode;

    prevNode->next = newNode;

    nextNode->prev = newNode;

}

int main() {

    struct Node* node1 = createNode(1);

    struct Node* node2 = createNode(2);

    node1->next = node2;

    node2->prev = node1;

    struct Node* head = node1;

    struct Node* tail = node2;

    printf("Doubly Linked List (Forward): ");

    displayForward(head);

    printf("Doubly Linked List (Backward): ");

    displayBackward(tail);

    int newData;

    printf("Enter the data for the new node: ");

    scanf("%d", &newData);

    insertBetween(node1, node2, newData);

    printf("Updated Doubly Linked List (Forward): ");

    displayForward(head);

    printf("Updated Doubly Linked List (Backward): ");

    displayBackward(tail);

    free(node1);

    free(node2);

    return 0;

}