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

    typedef struct no
    {
            int dado;
            struct no *proximo;
            struct no *anterior;     // Imagina aquele quadrado, eh o ponteiro apontado pro endereco do no anterior;
    } tno;

    typedef struct lista
    {
            tno *fim;   // ponteiro para o primeiro no da lista;
    } tlista;

    void inicia_lista (tlista *l)
    {
        l->fim= NULL;
    }

    tno *alocano (int dado)
    {
            tno *p;
            p = malloc(sizeof(tno));
            if(p)
            {
                    p->dado = dado;
                    p->proximo = NULL;
                    p->anterior = NULL;
            }
            return p;
    }

    void insereno (tlista *l, int dado)
    {
            tno *aux, *ant, *no;        // tno *ant = eh o no anterior ao novo no que voce ira colocar;
            no = alocano(dado);
            if(no)
            {
                    aux = l->fim->proximo;                       // ******
                    ant = NULL;
                    while(aux && aux->dado < dado)      // Esse while eh para procurar onde vai ser inserido o elemento; se aux == NULL(pode ser porque a lista ta vazia ou) eh porque vai ser o ultimo elemento;
                    {
                            ant = aux;
                            aux = aux->proximo;
                    }
                    if(!ant)
                    {
                            no->proximo = l->fim;
                            if(l->fim){
                                l->fim->proximo = no;    // Para colocar um novo no no começo da lista;

                            }
                            l->fim->proximo = no;

                    }
                    else
                    {
                            no->proximo = aux;         // para colocar um elemnto no fim da lista;
                            no->anterior = ant;
                            ant->proximo = no;
                            l->fim = no;                        // ******
                            l->fim->proximo = l->com->anterior; // ******
                            if(aux) aux->anterior = no;  // nao eh o ultimo elemento;
                    }
            }
    }

    int retiralista (tlista *l, int dado)
    {
            int r;
            tno *aux, *ant;
            // 1 = removeu
        //  //0 = nao achou
        //  //-1 = lista vazia
            aux = l->com;
            ant = NULL;
            if(!aux) return -1; // lista vazia
            while(aux && aux->dado != dado)
            {
                    ant = aux;
                    aux = aux->proximo;
            }
            if(!aux) return 0; // não achou
            r = aux->dado;
            if(!ant) // !(l->com->ant)
            {
                    if(aux->proximo) aux->proximo->anterior = l->fim->proximo;  // ******
                    l->com = aux->proximo;
                    l->com->anterior = l->com->fim; // ******
            }
            else
            {
                    ant->proximo = aux->proximo;
                    if(aux->proximo) aux->proximo->anterior = aux->anterior;
            }
            free(aux);
            return r;
    }

    void mostralista (tlista l)
    {
            tno *aux;
            aux = l.com;
            while(aux)
            {
                    printf("%d ", aux->dado);
                    aux = aux->proximo;
            }
            printf("\n");
    }

    void mostralistainvertida (tlista l)
    {
            tno *aux, *ant;
            aux = l.com;
            ant = NULL;
            while(aux)
            {

                if(aux->proximo == NULL){
                    ant = aux;
                    while(ant){
                        printf("%d ",ant->dado);
                        ant = ant->anterior;
                    }
                }
                ant = aux;
                aux = aux->proximo;
            }

            printf("\n");
    }

    int main()
    {
            tlista l;
            tno no;
            int i, dado, x, y;
            inicia_lista(&l);
            printf("qtde de elementos da lista: ");
            scanf("%d", &x);
            printf("digite os elementos:\n");
            for(i=0; i<x; i++)
            {
                    scanf("%d", &dado);
                    insereno(&l, dado);
            }
            printf("lista: ");
            mostralista(l);
            printf("digite um elemento para retirar: ");
            scanf("%d", &y);
            y = retiralista(&l, y);
            printf("o elemento %d foi retirado da lista.\n", y);
            printf("lista: ");
            mostralista(l);
            printf("lista invertida: ");
            mostralistainvertida(l);
            return 0;
    }