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

using namespace std;
typedef int TipoDato;
struct nodo{
            TipoDato Info;
            struct nodo *Liga;
};

typedef struct nodo *TipoLista;

void InicializarLista(TipoLista &P){
    P=NULL;
}

bool ListaVacia(TipoLista P){
    return (P==NULL);
}

void CrearInicio( TipoLista &P ){
    TipoLista Q;
    int Res;

    if ( ListaVacia(P) ) {
        P= new nodo;
        cout << "Escriba un valor del nodo: ";
        cin >> P-> Info;
        P->Liga=NULL;
    } else {
        Q=new nodo;
        cout << "Escriba valor del nodo: ";
        cin >> Q ->Info;
        Q->Liga=P;
        P=Q;
    }
    cout << "Desea anexar mas nodos a la lista? 1=Si 2=No " << endl;
    cin >>Res;

    while(Res==1){
        Q=new nodo;
        cout << "Escriba valor del nodo: ";
        cin >> Q ->Info;
        Q->Liga=P;
        P=Q;

        cout << "Desea anexar mas nodos a la lista? 1=Si 2=No " << endl;
        cin >>Res;
    }
}

void Recorre_iterativo(TipoLista P){

TipoLista Q=P;

while(Q!=NULL){
    cout<< Q->Info << " ";
    Q=Q->Liga;
}
}

void Recorre_recursivo(TipoLista P){
if(P!=NULL){
    cout<< P->Info << " ";
    Recorre_recursivo(P->Liga);
}
}

void InsertarInicio ( TipoLista &P, TipoDato Dato ){

    TipoLista Q;
    Q = new nodo;
    Q -> Info = Dato;
    Q -> Liga = P;
    P = Q;
}

void InsertarFinal ( TipoLista &P, TipoDato Dato ){

    TipoLista Q, T;

    Q = new nodo;
    Q -> Info = Dato;
    Q -> Liga = NULL;

    if ( !ListaVacia( P ) ) {

        T = P;
        while ( T -> Liga != NULL )
        T = T -> Liga;
        T -> Liga = Q;
    } else P = Q;
}

void InsertarAntes ( TipoLista &P, TipoDato Dato, TipoDato Ref ) {

    if( !ListaVacia(P) ){

        TipoLista Q = P, T;

        while( Q != NULL && Q -> Info != Ref ){
            T = Q;
            Q = Q -> Liga;
        }

        if( Q != NULL){
            TipoLista X = new nodo;
            X-> Info = Dato;
            if( Q == P ){
                X->Liga = P;
                P = X;
            } else{
                T->Liga = X;
                X->Liga = Q;
            }
        } else cout << "\n\tLa referencia "<< Ref << " no existe!\n" << endl;
    } else cout << "\n\tLista vacia, ingrese datos\n";
}


void InsertarDespues ( TipoLista &P, TipoDato Dato, TipoDato Ref ){


    if ( !ListaVacia(P) ){

        TipoLista Q = P;

        while ( Q != NULL && Q -> Info != Ref ) Q = Q -> Liga;

            if ( Q -> Liga != NULL ){

                TipoLista X = new nodo;
                X -> Info = Dato;
                X -> Liga = Q -> Liga;
                Q -> Liga = X;
            } else cout << "\n\tLa referencia " << Ref << " no existe!\n"; 
    } else cout << "\n\tLista vacia, ingrese datos\n";
}

void EliminarInicio( TipoLista &P){

    if ( !ListaVacia(P) ){

        TipoLista Q = P;
        P = P -> Liga;
        delete Q;
    } else cout << "\n\tLista vacia. \n";
}

void EliminarUltimo( TipoLista &P ){

    if ( !ListaVacia(P) ){

        if ( P -> Liga == NULL ) delete P;
        else {
            TipoLista Q = P, T;
            while (Q->Liga != NULL){
                T = Q;
                Q = Q->Liga;
            } T->Liga = NULL; delete Q;
        }
    } else cout << "\n\tLista vacia. \n";
}

void EliminarNodo( TipoLista &P, TipoDato X ){

    if( !ListaVacia(P) ){

        TipoLista Q = P, T;

        while ( Q != NULL && Q -> Info != X ){

            T = Q;
            Q = Q -> Liga;
        }
            if ( Q != NULL ){

                if ( P == Q ) P = Q -> Liga;
                else T -> Liga = Q -> Liga;
                delete Q;
            } else cout << "\n\tLa referencia "<< X << " no existe!\n" << endl;
    } else cout << " \n\tLista vacia. \nNo existe " << X << endl;
}

void EliminarAntes( TipoLista &P, TipoDato X ){

    if( !ListaVacia(P) ){

        TipoLista Q = P, T, R;

        while( Q != NULL && Q -> Info != X ){
            R = T;
            T = Q;
            Q = Q -> Liga;
        }

        if( Q != NULL){
            if( T != NULL ){
                if( R == NULL ) P = T->Liga;
                else R->Liga = T->Liga;
                delete T;
            } else cout << "\nNo existe nodo antes del nodo con la referencia " << X << " (es el primer nodo).\n"<< endl;
        } else cout << "\n\tLa referencia "<< X << " no existe!\n" << endl;
    } else cout << "\n\tLista vacia, ingrese datos. \n";
}

void EliminarDespues( TipoLista &P, TipoDato X ){

    if( !ListaVacia(P) ){

        TipoLista Q = P, T;

        while ( Q != NULL && Q->Info != X ) {
            T = Q;
            Q = Q->Liga;
        }
        if( Q != NULL ){
            if( Q->Liga != NULL ){
                if ( P == Q ) {
                    T = P->Liga;
                    P->Liga = T->Liga;
                } else {
                    T = Q->Liga;
                    Q -> Liga = T -> Liga;
                }
                delete T;
            } else cout << "\n\tLa referencia " << X << " no tiene nodo siguiente!\n" << endl;
        } else cout << "\n\tLa referencia " << X << " no existe!\n" << endl;
    } else cout << "\n\tLista vacia, primero ingrese datos.\n";
}

void menuPrincipal(){

    TipoDato X, Ref, Opc;
    TipoLista P;
    InicializarLista (P);
    do {

    system ("cls");
    cout << " \n\t>> Listas simplemente enlasadas <<" << endl;
    cout << "\t\tby Neftali Leobardo Vazquez Castillo\n" << endl;
    cout << "\t\tMenu\n" << endl;
    cout << "1. Introducir valores manualmente, insertando al inicio. " << endl;
    cout << "2. Introducir valores impares del 1 al 99 insertando al inicio." << endl;
    cout << "3. Introducir valores impares del 1 al 99 insertando al final.\n" << endl;
    cout << "4. Mostrar Arreglo Recursivo. " << endl;
    cout << "5. Mostrar Arreglo Iterativo. " << endl;

    cout << "\n6. Limpiar Lista. " << endl;

    cout << "\n\tInsercion\n" << endl;
    cout << "7. Insertar al inicio. " << endl; 
    cout << "8. Insertar al final. " << endl;
    cout << "9. Insertar antes de la referencia. " << endl;
    cout << "10. Insertar despues de la referencia. " << endl;

    cout << "\n\tEliminacion\n" << endl;
    cout << "11. Eliminar al inicio. " << endl;
    cout << "12. Eliminar al final. " << endl;
    cout << "13. Eliminar nodo. " << endl;
    cout << "14. Eliminar antes de la referencia" << endl;
    cout << "15. Eliminar despues de la referenccia" << endl;

    cout << "\n\t0. Salir" << endl;

    cout << "\n\tOpcion: "; cin >> Opc;

    switch(Opc){

    case 1: CrearInicio(P); break;
    case 2: for (int i=1; i<=100; i=i+2) InsertarInicio( P,  i);
        Recorre_recursivo(P); cout << endl; system("pause"); break;
    case 3: for (int i=1; i<=100; i=i+2) InsertarFinal( P,  i);
        Recorre_recursivo(P); cout<< endl; system("pause"); break;
    case 4: Recorre_recursivo(P); cout<< endl; system("pause"); break;
    case 5: Recorre_iterativo(P); cout<< endl; system("pause"); break;
    case 6: while ( P != NULL ) EliminarInicio(P); break;
    case 7: cout<< "Ingrese dato a insertar: "; cin >> X; InsertarInicio(P, X); Recorre_recursivo(P); cout << endl; system("pause"); break;
    case 8: cout<< "Ingrese dato a insertar: "; cin >> X; InsertarFinal(P, X); Recorre_recursivo(P); cout << endl; system("pause"); break;
    case 9: cout<< "Ingrese dato a insertar: "; cin >> X; cout<< "Ingrese referencia: "; cin>>Ref; InsertarAntes(P, X, Ref); Recorre_recursivo(P); cout << endl; system("pause"); break;
    case 10: cout<< "Ingrese dato a insertar: "; cin >> X; cout << "Ingrese referencia: "; cin>>Ref; InsertarDespues(P, X, Ref); Recorre_recursivo(P); cout << endl; system("pause"); break;
    case 11: EliminarInicio(P); Recorre_recursivo(P); cout<< endl; system("pause"); break;
    case 12: EliminarUltimo(P); Recorre_recursivo(P); cout<< endl; system("pause"); break;
    case 13: cout<< "Ingrese dato a eliminar: "; cin >> X; EliminarNodo(P, X); Recorre_recursivo(P); cout << endl; system("pause"); break;
    case 14: cout<< "Ingrese referencia: "; cin>>X; EliminarAntes(P, X); Recorre_recursivo(P); cout << endl; system("pause"); break;
    case 15: cout<< "Ingrese referencia: "; cin>>X; EliminarDespues(P, X); Recorre_recursivo(P); cout << endl; system("pause"); break;

    }
    } while (Opc != 0);
    system("cls");
    cout << "\n\n\tGracias por usar mi programa, puedes usarlo cuando gustes!\n" << endl;
    cout << "\t\t\t\tby ImNot Leo :D\n\n" << endl;
}

int main()
{
    menuPrincipal();
    return 0;
}