#include <iostream>
#include <conio.h>
#include <time.h>
using namespace std;

class No
{
    private:
        int dado;
        No* prox;
    friend class Lista;
};

class Lista
{
    private:
        No* inicio;
        No* ultimo;
    public:
        Lista(); //Construtor - equivale à função "criar".
        ~Lista(); //Destrutor - equivale à função "eliminar".
        void inserir(int elemento);
        void inserirOrdenado(int elemento);
        void remover(int elemento);
        void mostrar();
};

Lista :: Lista()
{
    inicio = NULL;
    ultimo = NULL;
}

Lista :: ~Lista()
{
    No* aux;
    ultimo->prox = NULL;

    while(inicio != NULL)
    {
        aux = inicio;
        inicio = inicio->prox;
        delete aux;
    }
}

void Lista :: inserir(int elemento)
{
    No* novo = new No;
    novo->dado = elemento;

    if(inicio == NULL)
    {
        novo->prox = novo;
        ultimo = novo;
    }
    else
    {
        novo->prox = inicio;
        ultimo->prox = novo;
    }

    inicio = novo;
}

void Lista :: inserirOrdenado(int elemento)
{
    No* aux;
    No* ant = NULL;
    No* novo = new No;
    novo->dado = elemento;

    for(aux = inicio; aux != NULL && novo->dado > aux->dado; aux = aux->prox)
    {
        if(ant == ultimo)
            break;

        ant = aux;
    }

    if(aux == NULL) //lista vazia
    {
        novo->prox = novo;
        inicio = novo;
        ultimo = novo;
        return;
    }

    if(ant == NULL) //inserir no começo
    {
        novo->prox = inicio;
        inicio = novo;
        ultimo->prox = novo;
        return;
    }

    if(ant == ultimo)
        ultimo = novo;

    ant->prox = novo; //inserir no meio ou no final
    novo->prox = aux;
}

void Lista :: remover(int elemento)
{
    No* aux;
    No* ant = NULL;

    for(aux = inicio; aux != NULL && aux->dado != elemento; aux = aux->prox)
    {
        if(aux == ultimo) //elemento não existente
            return;

        ant = aux;
    }

    if(aux == NULL) //lista vazia
        return;

    if(ant == NULL) //primeiro elemento da lista
    {
        inicio = aux->prox;
        ultimo->prox = inicio;
    }
    else //elemento do meio ou do final
    {
        ant->prox = aux->prox;

        if(aux == ultimo) //se o nó a ser deletado for o último, o nó anterior passará a ser o novo último
            ultimo = ant;
    }

    delete aux;
}

void Lista :: mostrar()
{
    No* aux;

    for(aux = inicio; aux != NULL; aux = aux->prox)
    {
        cout << aux->dado << endl;

        if(aux == ultimo)
            return;
    }
}

int main()
{
    Lista teste;

    teste.inserirOrdenado(4);
    teste.inserirOrdenado(0);
    teste.inserirOrdenado(2);
    teste.inserirOrdenado(1);
    teste.inserirOrdenado(3);
    teste.inserirOrdenado(5);
    teste.inserirOrdenado(10);
    teste.inserirOrdenado(8);

    teste.remover(10);

    teste.inserirOrdenado(11);

    teste.mostrar();

    return 0;
}