#include <iostream>
using namespace std;
const unsigned NMAX=100;
typedef unsigned adr;
struct nod
{
    int info;
    adr urm;
};
nod lista[NMAX+1];
adr pr,ul,p, nrel,liber[NMAX];
int vida(adr pr)
{
    cout<<"vida\n";
    return pr==0;
}
int plina()
{
    cout<<"plina";
    return nrel == NMAX;
}
void init(adr &pr, adr &ul)
{
    cout<<"init\n";
    nrel=0;
    for (adr p=1; p<=NMAX; p++) liber[p]=1;
    //ul=pr=0;
}
adr aloc()
{
    cout<<"aloc\n";
    adr p=1;
    while( liber[p]==0)
        p++;
    liber[p]=0;
    nrel++;
    return p;
}
void adaugPr(adr &pr, adr &ul, int n)
{
    cout<<"adaugPr\n";
    adr p=aloc();// cauta prima poz din lista libera
    lista[p].info=n;// copiere info
    lista[p].urm=0;//
    ul=p;
    pr=p;// ul si pr retin pozitia primului elem din lista
}
void adaugInaintePr(adr &pr, adr &ul, int n)
{
    adr p;
    cout<<"vadaugInaintePr\n";
    p=aloc(); // cauta prima poz libera
    lista[p].info=n;
    lista[p].urm=pr; //nodul p se leagă de nodul prim
    if (vida(pr)) ul=p;
    pr=p;
}
void adaugDupaUl(adr pr, adr &ul, int n)
{
    adr p;
    cout<<"adaugDupaUl\n";
    p=aloc();
    lista[p].info=n;
    lista[p].urm=0; //nodul p nu se leagă de nimic
    lista[ul].urm=p; //nodul ultim se leagă de nodul p
    //if (vida(pr)) pr=p;
    ul=p;
}
void adaugaDupa(adr q, adr &ul, int n)
{
    adr p;
    cout<<"adaugDupa\n";
    p=aloc(); // nodul q este copiat in lista dupa nodul p
    lista[p].info=n;
    lista[p].urm=lista[q].urm;
    lista[q].urm=p;
    if (lista[p].urm=0) ul=p;
}
void parcurge(adr q,adr u)
{
    for (adr p=q; p!=0; p=lista[p].urm)
        cout<<lista[p].info<<' '<<lista[p].urm<<";   ";
}
int main()
{
    init(pr,ul);
    adaugPr(pr,ul,88);
    int n;
    adaugDupaUl(pr,ul,5);
    adaugDupaUl(pr,ul,345);
    adaugDupaUl(pr,ul,123);
    cout<<nrel<<endl;
    for(int i=1; i<=5; i++)
        if(i%2==1)
            adaugDupaUl(pr,ul,i);
        else
            adaugInaintePr(pr,ul,i);
    parcurge(pr,ul);  cout<<endl;
    for(int i=1;i<=100;i++)
        cout<<lista[i].info<<' '<<lista[i].urm<<"\n";
    return 0;
}