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

struct dll_node
{
    int data;
    struct dll_node *prev, *next;
};

struct dll_node *create_list(int data)
{
    struct dll_node *new_node = (struct dll_node *)
        malloc(sizeof(struct dll_node));
    if (NULL != new_node)
    {
        new_node->data = data;
        new_node->prev = new_node->next = new_node;
    }
    return new_node;
}

struct dll_node *find_max_node(struct dll_node *node)
{
    struct dll_node *start = node, *result = node;
    int maximum = node->data;
    do
    {
        if (maximum < node->data)
        {
            maximum = node->data;
            result = node;
        }
        node = node->next;
    } while (node != start);
    return result;
};

struct dll_node *find_next_node(struct dll_node *node, int data)
{
    node = find_max_node(node);
    struct dll_node *start = node;
    do
    {
        if (node->data < data)
            break;
        node = node->next;
    } while (node != start);
    return node;
};

void insert_node(struct dll_node *node, int data)
{
    if (NULL == node)
        return;

    struct dll_node *new_node = (struct dll_node *)
        malloc(sizeof(struct dll_node));
    if (NULL != new_node)
    {
        new_node->data = data;
        node = find_next_node(node, data);
        new_node->next = node;
        new_node->prev = node->prev;
        node->prev->next = new_node;
        node->prev = new_node;
    }
}

struct dll_node *delete_node(struct dll_node *node, int data)
{
    if (NULL == node)
        return NULL;

    node = find_next_node(node, data);
    node = node->prev;
    if (node->data == data)
    {
        if (node == node->next)
        {
            free(node);
            return NULL;
        }
        else
        {
            struct dll_node *next = node->next;
            node->prev->next = node->next;
            node->next->prev = node->prev;
            free(node);
            node = next;
        }
    }
    return node;
}

void print_list(struct dll_node *node)
{
    if (NULL == node)
        return;

    node = find_max_node(node);
    struct dll_node *start = node;
    do
    {
        printf("%d ", node->data);
        node = node->next;
    } while (node != start);
    printf("\n");
}

void remove_list(struct dll_node **node)
{
    if (NULL == *node)
        return;

    struct dll_node *start = *node;
    do
    {
        struct dll_node *next = (*node)->next;
        free(*node);
        *node = next;
    } while (*node != start);
    *node = NULL;
}

void usun_rek(struct dll_node **ptr,struct dll_node *poczatek)
{
    if (*ptr)
    {
        if((*ptr)->next!=poczatek)
            usun_rek(&((*ptr)->next),poczatek);

        *ptr = delete_node(*ptr,(*ptr)->data);
    }
}

int main()
{
    struct dll_node *dlcl = create_list(1);
    int i;

    for (i=2; i<5; i++)
        insert_node(dlcl, i);
    for (i=6; i<10; i++)
        insert_node(dlcl, i);
    printf("List elements:\n");
    print_list(dlcl);

    insert_node(dlcl, 0);
    printf("List elements after insertion of 0:\n");
    print_list(dlcl);
    insert_node(dlcl, 5);
    printf("List elements after insertion of 5:\n");
    print_list(dlcl);
    insert_node(dlcl, 7);
    printf("List elements after insertion of 7:\n");
    print_list(dlcl);
    insert_node(dlcl, 10);
    printf("List elements after insertion of 10:\n");
    print_list(dlcl);

    dlcl = delete_node(dlcl, 0);
    printf("List elements after deletion of 0:\n");
    print_list(dlcl);
    dlcl = delete_node(dlcl, 1);
    printf("List elements after deletion of 1:\n");
    print_list(dlcl);
    dlcl = delete_node(dlcl, 1);
    printf("List elements after deletion of 1:\n");
    print_list(dlcl);
    dlcl = delete_node(dlcl, 5);
    printf("List elements after deletion of 5:\n");
    print_list(dlcl);
    dlcl = delete_node(dlcl, 7);
    printf("List elements after deletion of 7:\n");
    print_list(dlcl);
    dlcl = delete_node(dlcl, 10);
    printf("List elements after deletion of 10:\n");
    print_list(dlcl);

    usun_rek(&dlcl,dlcl);
    puts("aaa");
    print_list(dlcl);

    remove_list(&dlcl);
    return 0;
}