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

typedef struct Node {
    int value;

    struct Node *prev;
    struct Node *next;
} Node;

typedef struct {
    Node *head;
    Node *tail;
} List;


// Создание нового узла
Node *create_node(int value)
{
    Node *node = malloc(sizeof(Node));

    if (node == NULL) {
        return NULL;
    }

    node->value = value;
    node->prev = NULL;
    node->next = NULL;

    return node;
}


// Добавление в конец
void push_back(List *list, int value)
{
    Node *node = create_node(value);

    if (node == NULL) {
        return;
    }

    if (list->tail == NULL) {
        // Список пуст
        list->head = node;
        list->tail = node;
        return;
    }

    node->prev = list->tail;
    list->tail->next = node;
    list->tail = node;
}


// Вывод слева направо
void print_forward(const List *list)
{
    Node *current = list->head;

    while (current != NULL) {
        printf("%d ", current->value);
        current = current->next;
    }

    printf("\n");
}


// Вывод справа налево
void print_backward(const List *list)
{
    Node *current = list->tail;

    while (current != NULL) {
        printf("%d ", current->value);
        current = current->prev;
    }

    printf("\n");
}

// Удаление узла
void remove_node(List *list, Node *node)
{
    if (node == NULL) {
        return;
    }

    // Если есть предыдущий узел,
    // связываем его со следующим.
    if (node->prev != NULL) {
        node->prev->next = node->next;
    } else {
        // Удаляется head
        list->head = node->next;
    }

    // Если есть следующий узел,
    // связываем его с предыдущим.
    if (node->next != NULL) {
        node->next->prev = node->prev;
    } else {
        // Удаляется tail
        list->tail = node->prev;
    }

    free(node);
}

// Поиск узла
Node *find_node(const List *list, int value)
{
    Node *current = list->head;

    while (current != NULL) {
        if (current->value == value) {
            return current;
        }

        current = current->next;
    }

    return NULL;
}

// Освобождение списка
void free_list(List *list)
{
    Node *current = list->head;

    while (current != NULL) {
        Node *next = current->next;
        free(current);
        current = next;
    }

    list->head = NULL;
    list->tail = NULL;
}


int main(void)
{
    List list = {
        .head = NULL,
        .tail = NULL
    };

    push_back(&list, 10);
    push_back(&list, 20);
    push_back(&list, 30);
    push_back(&list, 40);

    printf("Forward:  ");
    print_forward(&list);
    
    // Удаление узла из середины
    // находим узел 30
    Node *node = find_node(&list, 30);
    // удаляем его
    remove_node(&list, node);

    printf("Backward: ");
    print_backward(&list);

    free_list(&list);

    return 0;
}