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

struct lista
{
  int info;
  lista *der,*izq,*sig;
};

lista *elimina_x(lista *p);
lista *elimina_ultimo(lista *p);
lista *elimina_primero(lista *p);
lista *inserta_antes(lista *p);
lista *crea_al_final(lista *p,lista *f);
lista *crea_al_inicio(lista *p,lista *f);
lista *inserta_inicio(lista *p);
lista *inserta_f(lista *p);
void recorre_iterativo(lista *P);
void recorre_iterativo1(lista *f);
void recorre_recursivo(lista *p);
void recorre_recursivo1(lista *f);

main()
{
  int opc=0;
  lista *p=NULL,*f=NULL;
  clrscr();
  while (opc!=11)
  {
    cout<<"\n\n\n MENU\n\n\n";
    cout<<"1) Crea al Final"<<endl;
    cout<<"2) Crea al Inicio"<<endl;
    cout<<"3) Recorre Iterativo"<<endl;
    cout<<"4) Recorre Recursivo"<<endl;
    cout<<"5) Inserta al Inicio"<<endl;
    cout<<"6) Inserta al Final"<<endl;
    cout<<"7) Inserta en la Posicion Anterior a:"<<endl;
    cout<<"8) Eliminar al Inicio"<<endl;
    cout<<"9) Eliminar al Final"<<endl;
    cout<<"10) Elimina en la Posicion: "<<endl;
    cout<<"11) Salir\n\n";
    cout<<"                     Elige la Opcion a Realizar: ";
    cin>>opc;

    if(opc==1)p=crea_al_final(p,f);
    if(opc==2)p=crea_al_inicio(p,f);
    if(opc==3)
    {
       recorre_iterativo(p);
       recorre_iterativo1(f);
    }
    if(opc==4)
    {
      recorre_recursivo(p);
      cout<<"NULL";
      recorre_recursivo1(f);
      cout<<"NULL";
    }
    if(opc==5)p=inserta_inicio(p);
    if(opc==6)p=inserta_f(p);
    if(opc==7)p=inserta_antes(p);
    if(opc==8)p=elimina_primero(p);
    if(opc==9)p=elimina_ultimo(p);
    if(opc==10)p=elimina_x(p);
  }
}

lista *crea_al_final(lista *p,lista *f)
{
  lista *q;
  char opc;
  p=new lista;
  cout<<" Da un Numero Entero: ";
  cin>>p->info;
  p->der=NULL;
  p->izq=NULL;
  f=p;
  cout<<" Deseas Insetar Otro Nodo <s/n>: ";
  cin>>opc;
  while(opc=='s')
  {
    q=new lista;
    cout<<" Da un Numero Entero: ";
    cin>>q->info;
    q->izq=f;
    f->der=q;
    f=q;
    q->der=NULL;
    cout<<" Deseas Insetar Otro Nodo <s/n>: ";
    cin>>opc;
  }
  return p;
}


lista *crea_al_inicio(lista *p,lista *f)
{
  lista *q;
  char opc;
  p=new lista;
  cout<<" Da un Numero Entero: ";
  cin>>p->info;
  p->sig=NULL;
  cout<<" Deseas Insetar Otro Nodo <s/n>: ";
  cin>>opc;
  while(opc=='s')
  {
    q=new lista;
    cout<<" Da un Numero Entero: ";
    cin>>q->info;
    q->sig=p;                            
    p=q;
    cout<<" Deseas Insetar Otro Nodo <s/n>: ";
    cin>>opc;
  }
  return p;
}


void recorre_iterativo(lista *p)
{
  lista *q;
  q=p;
  while(q!=NULL)
  {
    cout<<q->info<<"->";
    q=q->der;
  }
  cout<<"NULL";
}
void recorre_iterativo1(lista *f)
{
  lista *q;
  q=f;
  while(q!=NULL)
  {
    cout<<q->info<<"->";
    q=q->izq;
  }
  cout<<"NULL";
}


void recorre_recursivo(lista *p)
{
  lista *q;
  q=p;
  if(q!=NULL)
  {
    cout<<q->info<<"->";
    recorre_recursivo(q->der);
  }
}

void recorre_recursivo1(lista *f)
{
  lista *q;
  q=f;
  if(q!=NULL)
  {
    cout<<q->info<<"->";
    recorre_recursivo(q->izq);
  }
}

lista *inserta_inicio(lista *p)
{
  lista *q;
  q=new lista;
  cout<<" Da un Numero Entero: ";
  cin>>q->info;
  q->sig=p;
  p=q;
  return p;
}

lista *inserta_f(lista *p)
{
  lista *q,*r;
  q=p;
  while(q->sig!=NULL)
  {
    q=q->sig;
  }
  r=new lista;
  cout<<" Da un Numero Entero: ";
  cin>>r->info;
  r->sig=NULL;
  q->sig=r;
  return p;
}

lista *inserta_antes(lista *p)
{
  lista *q,*t,*r;
  char b='t';
  int dato;
  cout<<" Da el Numero a Buscar ";
  cin>>dato;
  q=p;
  while(q->info!=dato && b=='t')
  {
    if(q->sig!=NULL)
    {
      t=q;
      q=q->sig;
    }
    else
    {
      b='f';
    }
  }
  if(b=='t')
  {
    r=new lista;
    cout<<"Da el Numero  Insertar Antes de... "<<dato<<" : ";
    cin>>dato;
    r->info=dato;
    if(p==q)
    {
      r->sig=p;
      p=r;
    }
    else
    {
      t->sig=r;
      r->sig=q;
    }
  }
  return p;
}

lista *elimina_primero(lista *p)
{
  lista *q;
  q=p;
  if(q->sig!=NULL)
  {
    p=q->sig;
  }
  else
  {
    p=NULL;
  }
  return p;
}

lista *elimina_ultimo(lista *p)
{
  lista *q,*r;
  if(p->sig==NULL)
  {
    delete p;
    p=NULL;
  }
  else
  {
    q=p;
    while(q->sig!=NULL)
    {
      r=q;
      q=q->sig;
    }
    r->sig=NULL;
    delete q;
  }
  return p;
}

lista *elimina_x(lista *p)
{
  int dato;
  lista *q,*r;
  char b='t';
  cout<<" Escribe el elemento a eliminar: ";
  cin>>dato;
  q=p;
  while(q->info!=dato && b=='t')
  {
    if(q->sig!=NULL)
    {
      r=q;
      q=q->sig;
    }
    else
    {
      b='f';
    }
  }
  if(b=='f')
  {
    cout<<" El Elemento No Existe en la Lista ";
  }
  else
  {
    if(p==q)
    {
      p=q->sig;
    }
    else
    {
      r->sig=q->sig;
    }
  }
  delete q;
  return p;
}