#include <iostream>

using namespace std;
typedef int adresa; //rebotezare tip int cu numele adresa pentru deosebire intre informatia propriu-zisa si adresa unui nod
struct nod //declarare nod
    {int info; //informatia nodului
    adresa urm; //adresa catre nodul urmator
};
nod L[1000]; //declarare vector cu elemente de tip nod cu maxim 1000 elemente
int nr_elem; //nr de noduri din lista la un moment dat
adresa ocupat[1000],sf,v; //1 daca elementul e ocupat si 0 altfel

int Exista_spatiu() //testeaza dacaexista spatiu disponibil pentru alocarea unui nod
 {
     return nr_elem<1000;
 }

 void Aloca(adresa &x)//alocare spatiu pentru un nod, pe prima componenta libera gasita
 {
     adresa i=1;
     while(ocupat[i]) i++;
     x=i;
     ocupat[i]=1;
     nr_elem++;
 }

 void Elibereaza(adresa x) //eliberare spatiu la stergerea unui nod
 {
     ocupat[x]=0;
     nr_elem--;
 }

 void Adaugare(adresa &v,int val)
 {
     int c;
     if(!v)//daca v=0, lista e vida si se creeaza primul nod, ce primeste info val si adresa v
     {
         Aloca(v);
         L[v].info=val;
         L[v].urm=0;
         sf=v; //ultimul nod al listei e sf
     }
     else
        if(Exista_spatiu)
     { //se adauga la sfarsitul unei liste nevide un element
         Aloca(c);
         L[sf].urm=c;
         L[c].info=val;
         L[c].urm=0;
         sf=c;
     }
     else cout<<"lipsa spatiu"<<endl;
 }

 void Inserare_dupa(adresa v,int val, int val1) //insereaza nodul cu info val1 dupa nodul cu info val
 {
     adresa c,d;
     if(Exista_spatiu())
     {
         c=v;
         while(L[c].info!=val) c=L[c].urm; //se cauta nodul cu info val
         Aloca(d);//se aloca spatiu pentru noul nod
         L[d].info=val1;
         L[d].urm=L[c].urm;
         L[c].urm=d;
         if(L[d].urm==0) sf=d;
     }
     else cout<<"lipsa spatiu"<<endl;
 }

 void Inserare_inainte(adresa &v,int val, int val1)//insereaza nodul cu info val1 inainte de nodul cu info val
 {
     adresa c,d;
     if(Exista_spatiu())
        if(L[v].info==val)
     {
         Aloca(d);
         L[d].info=val1;
         L[d].urm=v;
         v=d;
    }
         else
         {
             c=v;
             while(L[L[c].urm].info!=val) c=L[c].urm;
             Aloca(d);
             L[d].info=val1;
             L[d].urm=L[c].urm;
             L[c].urm=d;
         }
         else cout<<"nu e spatiu "<<endl;
 }

 void Sterg(adresa &v, int val) //sterge nodul cu informatia val
 {
     adresa c,man;
     if(L[v].info==val)
     {
         man=v;
         v=L[v].urm;
     }
     else
     {
         c=v;
         while(L[L[c].urm].info!=val) c=L[c].urm;
         man=L[c].urm;
         L[c].urm=L[man].urm;
         if(man==sf) sf=c;
    }
    Elibereaza(man);
 }

 void Afisare(adresa v)
 {
     adresa c=v;
     while(c)
     {
         cout<<L[c].info<<"  ";
         c=L[c].urm;
     }
     cout<<endl;
 }

 int Cautare(int x)
 {
     int p;
     while(p && L[p].info!=x)
        p=L[p].urm;
     return(p);
 }
int main()
{
    int i;         vvv
    for(i=1;i<=10;i++)
        Adaugare(v,i);
    Afisare(v);
    Inserare_dupa(v,1,15); Afisare(v);
    Inserare_dupa(v,10,25); Afisare(v);
    Inserare_inainte(v,3,29);Afisare(v);
    Sterg(v,5);Afisare(v);
    cout<<"nodul cu info 25 se afla pe pozitia "<<Cautare(25);
    return 0;
}