#include <stdio.h>
#include <stdlib.h>
#define INSERTAR_CABEZA 1
#define INSERTAR_ANTES 2
#define INSERTAR_DESPUES 3
#define INSERTAR_FINAL 4
#define SALIR 5
 
typedef struct nodo
{
    int elemento;
    struct nodo *sig;
    struct nodo *ant;
}Nodo;
 
Nodo *crearNodo(int insertable);
void insertarCabeza(int insertable,Nodo **cabeza);
void insertar_antes(Nodo *anterior,int insertable);
void insertar_despues(Nodo *posterior,int insertable);
void insertarFinal(Nodo *ultimo,int insertable);
Nodo *buscarElemento(int elementoBuscado,Nodo *cabeza);
void imprimirLista(Nodo *cabeza);
Nodo *ultimoElemento(Nodo *cabeza);
Nodo *Anterior(Nodo *p);
 
int main()
{
    Nodo *cabeza,*anterior,*posterior,*p,*ultimo;
    cabeza = NULL;
    int continuar = 1,opcion,numElementos,insertable,elementoBuscado,i;
    printf("Lista Doblemente Enlazada!\n\n");
    do
    {
        printf("\nMenu\n");
        printf("1) Insertar cabeza de Lista\n");
        printf("2) Insertar antes de elementento\n");
        printf("3) Insertar despues de elemento\n");
        printf("4) Insertar final de Lista\n");
        printf("5) Salir\n");
        scanf("%d",&opcion);
        switch(opcion)
        {
            case INSERTAR_CABEZA:
               printf("Dame el numero de elementos de la lista: ");
               scanf("%d",&numElementos);
               for(i=0;i < numElementos;i++)
               {
                   printf("Dame el elemento a insertar: ");
                   scanf("%d",&insertable);
                   insertarCabeza(insertable,&cabeza);
                   system("cls");
               }
               imprimirLista(cabeza);
               break;
            case INSERTAR_ANTES:
               printf("Antes de que elemento se quiere insertar: ");
               scanf("%d",&elementoBuscado);
               if((p = buscarElemento(elementoBuscado,cabeza))!=NULL)
               {
                   printf("Dame el elemento a insertar: ");
                   scanf("%d",&insertable);
                   anterior = Anterior(p);
                   insertar_antes(anterior,insertable);
               }
               else
                  printf("No se encontro elemento!\n");
               imprimirLista(cabeza);
               break;
            case INSERTAR_DESPUES:
               printf("Despues de que elemento deseas insertar: ");
               scanf("%d",&elementoBuscado);
               if((posterior = buscarElemento(elementoBuscado,cabeza))!=NULL)
               {
                   printf("Dame el elemento a insertar: ");
                   scanf("%d",&insertable);
                   insertar_despues(posterior,insertable);
               }
               else
                  printf("No se encontro elemento!\n");
               imprimirLista(cabeza);
               break;
            case INSERTAR_FINAL:
               printf("Dame el numero de elementos de la lista: ");
               scanf("%d",&numElementos);
               if(estaVacia(cabeza))
               {
                   printf("Dame el elemento a insertar: ");
                   scanf("%d",&insertable);
                   cabeza = crearNodo(insertable);
                   numElementos--;
               }
               for(i = 0;i < numElementos;i++)
               {
                   ultimo = ultimoElemento(cabeza);
                   printf("Dame el elemento a insertar: ");
                   scanf("%d",&insertable);
                   insertarFinal(ultimo,insertable);
               }
               imprimirLista(cabeza);
               break;
            case SALIR:
               continuar = 0;
               break;
        }
        if(continuar)
            system("pause");
    }while(continuar);
    return 0;
}
 
Nodo *crearNodo(int insertable)
{
    Nodo *p;
    p = (Nodo*)malloc(sizeof(Nodo));
    p->elemento = insertable;
    p->sig = NULL;
    p->ant = NULL;
    return p;
}
 
void insertarCabeza(int insertable,Nodo **cabeza)
{
    Nodo *nuevo;
    nuevo = crearNodo(insertable);
    nuevo->sig = *cabeza;
    nuevo->ant = NULL;
    *cabeza = nuevo;
}
 
void insertar_antes(Nodo *anterior,int insertable)
{
    Nodo *nuevo;
    nuevo = crearNodo(insertable);
    anterior->sig->ant = nuevo;
    nuevo->ant = anterior;
    nuevo->sig = anterior->sig;
    anterior->sig = nuevo;
}
 
void insertar_despues(Nodo *posterior,int insertable)
{
    Nodo *nuevo;
    nuevo = crearNodo(insertable);
    posterior->sig->ant = nuevo;
    nuevo->ant = posterior;
    nuevo->sig = posterior->sig;
    posterior->sig = nuevo;
}
 
void insertarFinal(Nodo *ultimo,int insertable)
{
    ultimo->sig = crearNodo(insertable);
    ultimo->sig->sig = NULL;
    ultimo->sig->ant = ultimo;
}
 
void imprimirLista(Nodo *cabeza)
{
    Nodo *ptr;
    for(ptr = cabeza;ptr!=NULL;ptr = ptr->sig)
       printf("%d\t",ptr->elemento);
}
 
Nodo *buscarElemento(int elementoBuscado,Nodo *cabeza)
{
    Nodo *ptr;
    for(ptr = cabeza;ptr!=NULL;ptr = ptr->sig)
    {
        if(ptr->elemento == elementoBuscado)
           return ptr;
    }
    return NULL;
}
 
Nodo *ultimoElemento(Nodo *cabeza)
{
    Nodo *ptr;
    ptr = cabeza;
    while(ptr->sig!=NULL)
       ptr = ptr->sig;
    return ptr;
}
 
int estaVacia(Nodo *cabeza)
{
    if(cabeza == NULL)
       return 1;
    else
       return 0;
}
 
Nodo *Anterior(Nodo *p)
{
    return p->ant;
}