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

/* Node structure */
typedef struct node {
    int data;
    struct node *prev;
    struct node *next;
} NODE;

/* Global head pointer */
NODE *head = NULL;

/* Insert node at end (Create list) */
void insert(int value) {
    NODE *newNode, *temp;

    newNode = (NODE *)malloc(sizeof(NODE));
    if (!newNode) {
        printf("Memory allocation failed\n");
        return;
    }

    newNode->data = value;
    newNode->next = NULL;

    /* Case 1: Empty list */
    if (head == NULL) {
        newNode->prev = NULL;
        head = newNode;
        printf("Inserted %d\n", value);
        return;
    }

    /* Case 2: List not empty → go to last node */
    temp = head;
    while (temp->next != NULL) {
        temp = temp->next;
    }

    temp->next = newNode;
    newNode->prev = temp;

    printf("Inserted %d\n", value);
}

/* Delete node by value (HEAD / MIDDLE / LAST handled) */
void delete_value(int value) {
    NODE *temp = head;

    /* Case 0: Empty list */
    if (head == NULL) {
        printf("List is empty\n");
        return;
    }

    /* Search for the node */
    while (temp != NULL && temp->data != value) {
        temp = temp->next;
    }

    /* Value not found */
    if (temp == NULL) {
        printf("Element not found\n");
        return;
    }

    /* Case 1: Deleting HEAD node */
    if (temp->prev == NULL) {
        head = temp->next;      // move head forward
        if (head != NULL) {
            head->prev = NULL;  // new head prev must be NULL
        }
    }

    /* Case 2: Deleting LAST node */
    else if (temp->next == NULL) {
        temp->prev->next = NULL;
    }

    /* Case 3: Deleting MIDDLE node */
    else {
        temp->prev->next = temp->next;
        temp->next->prev = temp->prev;
    }

    free(temp);
    printf("Deleted %d\n", value);
}

/* Display list */
void display() {
    NODE *temp = head;

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

    printf("List: ");
    while (temp != NULL) {
        printf("%d <-> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

/* Main function */
int main() {
    int choice, value;

    while (1) {
        printf("\n--- DOUBLY LINKED LIST MENU ---\n");
        printf("1. Insert\n");
        printf("2. Delete\n");
        printf("3. Display\n");
        printf("4. Exit\n");
        printf("Enter choice: ");
        scanf("%d", &choice);

        switch (choice) {

        case 1:
            printf("Enter value: ");
            scanf("%d", &value);
            insert(value);
            break;

        case 2:
            printf("Enter value to delete: ");
            scanf("%d", &value);
            delete_value(value);
            break;

        case 3:
            display();
            break;

        case 4:
            exit(0);

        default:
            printf("Invalid choice\n");
        }
    }
}