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

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

// allocate node with 10-char buffer
struct Node* createNode(const char *value)
{
    struct Node *newNode = malloc(sizeof(struct Node));

    newNode->value = malloc(10); 
    strncpy(newNode->value, value, 9);
    newNode->value[9] = '\0';      // safety null termination
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}

// print list
void printList(struct Node *head)
{
    struct Node *curr = head;

    printf("NULL <-> ");
    while (curr)
    {
        printf("%s <-> ", curr->value);
        curr = curr->next;
    }
    printf("NULL\n");
}
////////////////////////////////////////////////////
// insert at end
void pushBack(struct Node **head, const char *value)
{
    struct Node *n = createNode(value);

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

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

    curr->next = n;
    n->prev = curr;
}
////////////////////////////////////////////////////////
// insert after
void insertAfter(struct Node **head, const char *target, const char *value)
{
    struct Node *curr = *head;

    while (curr)
    {
        if (strcmp(curr->value, target) == 0)
        {
            struct Node *n = createNode(value);

            n->next = curr->next;
            n->prev = curr;

            if (curr->next)
                curr->next->prev = n;

            curr->next = n;
            return;
        }
        curr = curr->next;
    }
}
/////////////////////////////////////////////////////////
// insert before
void insertBefore(struct Node **head, const char *target, const char *value)
{
    struct Node *curr = *head;

    while (curr)
    {
        if (strcmp(curr->value, target) == 0)
        {
            struct Node *n = createNode(value);

            n->next = curr;
            n->prev = curr->prev;

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

            curr->prev = n;
            return;
        }
        curr = curr->next;
    }
}

// delete after
void deleteAfter(struct Node **head, const char *target)
{
    struct Node *curr = *head;

    while (curr)
    {
        if (strcmp(curr->value, target) == 0 && curr->next)
        {
            struct Node *del = curr->next;

            curr->next = del->next;
            if (del->next)
                del->next->prev = curr;

            free(del->value);  // FREE STRING
            free(del);         // FREE NODE
            return;
        }
        curr = curr->next;
    }
}

// delete before
void deleteBefore(struct Node **head, const char *target)
{
    struct Node *curr = *head;

    while (curr)
    {
        if (strcmp(curr->value, target) == 0 && curr->prev)
        {
            struct Node *del = curr->prev;

            if (del->prev)
            {
                del->prev->next = curr;
                curr->prev = del->prev;
            }
            else
            {
                *head = curr;
                curr->prev = NULL;
            }

            free(del->value);  // FREE STRING
            free(del);         // FREE NODE
            return;
        }
        curr = curr->next;
    }
}

// reverse list
void reverseList(struct Node **head)
{
    struct Node *curr = *head;
    struct Node *temp = NULL;

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

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

// FREE ENTIRE LIST (IMPORTANT)
void freeList(struct Node **head)
{
    struct Node *curr = *head;
    struct Node *next = NULL;

    while (curr)
    {
        next = curr->next;
        free(curr->value);
        free(curr);
        curr = next;
    }

    *head = NULL;
}

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

    pushBack(&head, "A");
    pushBack(&head, "B");
    pushBack(&head, "C");
    pushBack(&head, "D");

    printList(head);

    insertAfter(&head, "B", "X");
    printList(head);

    insertBefore(&head, "C", "Y");
    printList(head);

    deleteAfter(&head, "A");
    printList(head);

    deleteBefore(&head, "D");
    printList(head);

    reverseList(&head);
    printList(head);

    freeList(&head);   // CLEAN MEMORY

    return 0;
}