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

typedef struct Node {
    int data;
    struct Node *prev;
    struct Node *next;
} Node;

Node *head = NULL;
Node *tail = NULL;

Node* createNode(int data) {
    Node *n = (Node*)malloc(sizeof(Node));
    n->data = data;
    n->prev = NULL;
    n->next = NULL;
    return n;
}

void insertEnd(int data) {
    Node *n = createNode(data);

    if (head == NULL) {
        head = n;
        tail = n;
        return;
    }

    tail->next = n;
    n->prev = tail;
    tail = n;
}

void deleteKey(int key) {
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }

    Node *curr = head;
    while (curr != NULL && curr->data != key) {
        curr = curr->next;
    }

    if (curr == NULL) {
        printf("Key not found\n");
        return;
    }

    if (curr->prev != NULL)
        curr->prev->next = curr->next;
    else
        head = curr->next;

    if (curr->next != NULL)
        curr->next->prev = curr->prev;
    else
        tail = curr->prev;

    free(curr);
}

void displayForward() {
    Node *temp = head;
    printf("DLL forward: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

void displayBackward() {
    Node *temp = tail;
    printf("DLL backward: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->prev;
    }
    printf("\n");
}

int main() {
    int choice, value;

    while (1) {
        printf("\n--- DOUBLY LINKED LIST MENU ---\n");
        printf("1. Insert at end\n");
        printf("2. Delete by key\n");
        printf("3. Display forward\n");
        printf("4. Display backward\n");
        printf("5. Exit\n");
        printf("Enter your choice: ");
        scanf("%d", &choice);

        switch (choice) {
            case 1:
                printf("Enter value: ");
                scanf("%d", &value);
                insertEnd(value);
                break;
            case 2:
                printf("Enter key to delete: ");
                scanf("%d", &value);
                deleteKey(value);
                break;
            case 3:
                displayForward();
                break;
            case 4:
                displayBackward();
                break;
            case 5:
                return 0;
            default:
                printf("Invalid choice\n");
        }
    }
}