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

struct Node {
    char *data;
    struct Node *prev;
    struct Node *next;
};

// Create node
struct Node* createNode(const char *data) {
    struct Node *newNode = (struct Node*)malloc(sizeof(struct Node));
    if (!newNode) return NULL;

    newNode->data = (char*)malloc(10);
    strncpy(newNode->data, data, 9);
    newNode->data[9] = '\0';

    newNode->prev = NULL;
    newNode->next = NULL;

    return newNode;
}

// Insert at end (helper)
void insertEnd(struct Node **head, const char *data) {
    struct Node *newNode = createNode(data);

    if (*head == NULL) {
        *head = newNode;
        return;
    }

    struct Node *temp = *head;
    while (temp->next)
        temp = temp->next;

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

// Insert after a given value
void insertAfter(struct Node **head, const char *target, const char *data) {
    struct Node *temp = *head;

    while (temp && strcmp(temp->data, target) != 0)
        temp = temp->next;

    if (!temp) return;

    struct Node *newNode = createNode(data);

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

    if (temp->next)
        temp->next->prev = newNode;

    temp->next = newNode;
}

// Insert before a given value
void insertBefore(struct Node **head, const char *target, const char *data) {
    struct Node *temp = *head;

    while (temp && strcmp(temp->data, target) != 0)
        temp = temp->next;

    if (!temp) return;

    struct Node *newNode = createNode(data);

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

    if (temp->prev)
        temp->prev->next = newNode;
    else
        *head = newNode;   // updating head

    temp->prev = newNode;
}

// Delete node by value
void deleteNode(struct Node **head, const char *target) {
    struct Node *temp = *head;

    while (temp && strcmp(temp->data, target) != 0)
        temp = temp->next;

    if (!temp) return;

    if (temp->prev)
        temp->prev->next = temp->next;
    else
        *head = temp->next;

    if (temp->next)
        temp->next->prev = temp->prev;

    free(temp->data);
    free(temp);
}

// Reverse DLL
void reverse(struct Node **head) {
    struct Node *temp = NULL;
    struct Node *current = *head;

    while (current) {
        temp = current->prev;
        current->prev = current->next;
        current->next = temp;
        current = current->prev;
    }

    if (temp)
        *head = temp->prev;
}

// Print list
void printList(struct Node *head) {
    printf("List: ");
    while (head) {
        printf("%s <-> ", head->data);
        head = head->next;
    }
    printf("NULL\n");
}

// Free memory
void freeList(struct Node **head) {
    struct Node *temp;

    while (*head) {
        temp = *head;
        *head = (*head)->next;
        free(temp->data);
        free(temp);
    }
}

int main() {
    struct Node *head = NULL;

    printf("==== CREATE LIST ====\n");
    insertEnd(&head, "A");
    insertEnd(&head, "B");
    insertEnd(&head, "C");
    printList(head);

    printf("\n==== INSERT AFTER B ====\n");
    insertAfter(&head, "B", "X");
    printList(head);

    printf("\n==== INSERT BEFORE B ====\n");
    insertBefore(&head, "B", "Y");
    printList(head);

    printf("\n==== DELETE NODE B ====\n");
    deleteNode(&head, "B");
    printList(head);

    printf("\n==== INSERT AT HEAD (before A) ====\n");
    insertBefore(&head, "A", "HEAD");
    printList(head);

    printf("\n==== REVERSE LIST ====\n");
    reverse(&head);
    printList(head);

    printf("\n==== CLEANUP ====\n");
    freeList(&head);

    return 0;
}