#include <conio.h>
#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
struct lista
  {
   int info;
   lista *der;
   lista *izq;
  };

lista *creainicio(lista *p);
lista *creafinal(lista *p);
lista *insertainicio(lista *p);
lista *insertafinal(lista *p);
lista *inserta_antes(lista *p);
lista *eliminaprimero(lista *p);
lista *eliminaultimo(lista *p);
lista *eliminax(lista *p);
void recorreder(lista *p);
void recorreizq(lista *p);

main()
{
  int opc=0;
  lista *puntero=NULL;
  while(opc!=9)
  {
   cout<<"\n\t\t MENU PRINCIPAL DE LISTAS DOBLEMENTE LIGADAS"<<endl<<endl;
   cout<<"1.-Crear la lista al final"<<endl;
   cout<<"2.-Crear la lista al inicio"<<endl;
   cout<<"3.-Inserta un dato al inicio "<<endl;
   cout<<"4.-Inserta al final"<<endl;
   cout<<"5.-Inserta antes de x dato"<<endl;
   cout<<"6.-Elimina primero "<<endl;
   cout<<"7.-Elimina ultimo"<<endl;
   cout<<"8.-Elimina x"<<endl;
   cout<<"9.-Salir"<<endl<<endl;
   cout<<"Selecciona una pocion:"<<endl;
   cin>>opc;
  switch(opc)
  {
   case 1: cout<<"\tCREA AL FINAL"<<endl;
           puntero=creafinal(puntero);
           break;
   case 2: cout<<"\tCREA AL INICIO"<<endl;
           puntero=creainicio(puntero);
           break;
   case 3: cout<<"\tINSERTA AL INICIO"<<endl;
           puntero=insertainicio(puntero);
           break;
   case 4: cout<<"\tINSERTA UN DATO AL FINAL"<<endl;
           puntero=insertafinal(puntero);
           break;
   case 5: cout<<"\tINSERTA UN DATO ANTES DE ALGUN DATO"<<endl;
           puntero=inserta_antes(puntero);
           break;
   case 6: cout<<"\tELIMINA EL PRIMER DATO  "<<endl;
           puntero=eliminaprimero(puntero);
           break;
   case 7: cout<<"\tELIMINA EL ULTIMO DATO  "<<endl;
           puntero=eliminaultimo(puntero);
           break;
   case 8:
            cout<<"\tELIMINA CUALQUIER DATO"<<endl;
            puntero=eliminax(puntero);
            break;
   case 9: exit (0);

  }
 }
}
lista *creafinal(lista *p)
{
 int n,j=0;
 char x;
 lista *q,*f;
 p=new lista;
 cout<<"Da un numero entero : "<<endl;
 cin>>p->info;
 p->der=NULL;
 p->izq=NULL;
 f=p;
 cout<<"Desea agregar mas datos <s/n> "<<endl;
 cin>>x;
 while(x=='s')
  {
   cout<<"Cuantos datos vas a agregar: "<<endl;

   cin>>n;
   do
    {
     q=new lista;
     cout<<"Da un numero entero"<<endl;
     cin>>q->info;
     q->der=NULL;
     q->izq=f;
     f->der=q;
     f=q;
     j++;
  }while(j!=n);
  cout<<"Desea agregar mas datos <s/n> "<<endl;
  cin>>x;
 }
   recorreder(p);
   recorreizq(f);
 return p;
}
 void recorreder(lista *p)
{
 lista *q;
 q=p;
 while(q!=NULL)
  {
   cout<< q->info<<"=>";
   q=q->der;
  }
 cout<< "NULL"<<endl;
 getch();
}

lista *creainicio(lista *p)
{
  int n,j=0;
 char x;
 lista *q,*f;
 p=new lista;
 cout<<"Da un numero entero ; "<<endl;
 cin>>p->info;
 p->der=NULL;
 p->izq=NULL;
 f=p;
 cout<<"Desea agregar mas datos <s/n> "<<endl;
 cin>>x;
 while(x=='s')
  {
   cout<<"Cuantos datos vas a agregar: "<<endl;
   cin>>n;
   do
    {
     q=new lista;
     cout<<"Da un numero entero"<<endl;
     cin>>q->info;
     q->der=p;
     p->izq=q;
     p=q;
     q->izq=NULL;
     j++;
  }while(j!=n);
  cout<<"Desea agregar mas datos <s/n> "<<endl;
  cin>>x;
 }
 recorreder(p);
 recorreizq(f);
 return p;
}
 void recorreizq(lista *p)
{
 lista *q;
 q=p;
 while(q!=NULL)
  {

   cout<< q->info<<"=>";
   q=q->izq;
  }
 cout<< "NULL"<<endl;
 getch();
}

lista *insertainicio(lista *p)
{
lista *q,*f;
 q=new lista;
 cout<<"Da el numero entero"<<endl;
 cin>>q->info;
 q->der=p;
 p->izq=q;
 p=q;
 q->izq=NULL;
 f=p;
 while(f->der!=NULL)
 {
 f=f->der;
 }
 recorreder(p);
 recorreizq(f);
 return p;
 }

lista *insertafinal(lista *p)
{
  lista *q,*r;
  q=p;
  while(q->der!=NULL)
  {
    q=q->der;
  }
  r=new lista;
  cout<<"Escribe un numero entero: ";
  cin>>r->info;
  r->izq=q;
  q->der=r;
  r->der=NULL;
  recorreder(p);
  recorreizq(r);
  return p;
}

lista *inserta_antes(lista *p)
{
  lista *q,*t,*r,*f;
  char b='t';
  int dato;
  cout<<"Escribe el dato a buscar: ";
  cin>>dato;
  q=p;
  while(q->info!=dato && b=='t')
  {
    if(q->der!=NULL)
    {
      t=q;
      q=q->der;
    }
    else
    {
      b='f';
    }
  }
  if(b=='t')
  {
    r=new lista;
    cout<<"Escribe el elemento a escribir antes de "<<dato<<" : ";
    cin>>dato;
    r->info=dato;
    r->der=NULL;
    r->izq=NULL;
    if(p==q)
    {
      r->der=q;
      q->izq=r;
      q->der=NULL;
      r->izq=NULL;
      p=r;
    }
    else
    {
      t->der=r;
      r->izq=t;
      r->der=q;
      q->izq=r;
    }
  }
  f=p;
  while(f->der!=NULL)
  {
  f=f->der;
  }
  recorreder(p);
  recorreizq(f);
  return p;
}

lista *eliminaprimero(lista *p)
{
  lista *q,*f;
  q=p;
 if(q->der!=NULL)
  {
    p=q->der;
  }
  else
  {
    p=NULL;
  }
  delete q;
  p->izq=NULL;
  f=p;
  while(f->der!=NULL)
  {
   f=f->der;
  }
  recorreder(p);
  recorreizq(f);
  return p;
}

lista *eliminaultimo(lista *p)
{
  lista *q,*r;
  if(p->der==NULL)
  {
    delete p;
    p=NULL;
  }
  else
  {
    q=p;
    while(q->der!=NULL)
    {
      r=q;
      q=q->der;
    }
    r->der=NULL;
    delete q;
  }
 recorreder(p);
 recorreizq(r);
  return p;
}

lista *eliminax(lista *p)
{
  int dato;
  lista *q,*r,*f,*pu;
  char b='t';
  cout<<"Escribe el elemento a eliminar: ";
  cin>>dato;
  q=p;
  while(q->info!=dato && b=='t')
  {
    if(q->der!=NULL)
    {
      r=q;
      q=q->der;
      pu=q;
    }
    else
    {
      b='f';
    }
  }
  pu=q->der;
  if(b=='f')
  {
    cout<<"El elemento no existe en la lista ";
    exit (1);
  }
  else
  {
    if(p==q)
    {
      p=q->der;
    }
    else
    {
      r->der=q->der;
    }
  }
  delete q;
  pu->izq=r;
  f=p;
  while(f->der!=NULL)
    {
     f=f->der;
    }
  recorreder(p);
  recorreizq(f);
  return p;
}