#include <iostream>
#include <ctime>
#include <cstdlib>
#include <cstring>

using namespace std;

struct elem
{
    int st;
    elem *linkPre;
    elem *linkAf;
};
int br;
elem *first;
elem *last;

void init()
{
    br=0;
    first=NULL;
    last=NULL;
}

void addfirst(int el)
{
    elem *p=new elem;
    p->st=el;
    if(!first)
    {
        p->linkPre=NULL;
        p->linkAf=NULL;
        br++;
        first=p;
        last=p;
        return;
    }
    p->linkAf=first;
    p->linkPre=NULL;
    first=p;
    br++;
}

void addlast(int el)
{
    elem *p=new elem;
    p->st=el;
    if(!first)
    {
        p->linkPre=NULL;
        p->linkAf=NULL;
        br++;
        first=p;
        last=p;
        return;
    }
    p->linkPre=last;
    p->linkAf=NULL;
    last=p;
    br++;
}

void addposition(int el,int pos)
{
    elem *p=new elem;
    p->st=el;
    if(!first)
    {
        p->linkPre=NULL;
        p->linkAf=NULL;
        br++;
        first=p;
        last=p;
        return;
    }
    if(pos<=1)
    {
        addfirst(el);
        return;
    }
    if(pos>br)
    {
        addlast(el);
        return;
    }
    int i=2;
    elem *q=first;
    while(i<pos)
    {
        q=q->linkAf;
        i++;
    }
    p->linkAf=q->linkAf;
    p->linkPre=q;
    q->linkAf=p;
    q=p->linkAf;
    q->linkPre=p;
    br++;
}

void delfirst(int *el)
{
    if(!first)
    {
        return;
    }
    elem *p=first;
    *el=p->st;
    first=first->linkAf;
    first->linkPre=NULL;
    delete p;
    br--;
}

void dellast(int *el)
{
    if(!first)
    {
        return;
    }
    elem *p=last;
    *el=p->st;
    last=last->linkPre;
    last->linkAf=NULL;
    delete p;
    br--;
}

void delposition(int *el,int pos)
{
    if(!first)
    {
        return;
    }
    if(pos<=1)
    {
        delfirst(el);
        return;
    }
    if(pos>=br)
    {
        dellast(el);
        return;
    }
    elem *p=first;
    int i=2;
    while(i<=pos)
    {
        p=p->linkAf;
        i++;
    }
    *el=p->st;
    elem *q=p->linkAf;
    q->linkPre=p->linkPre;
    p=p->linkPre;
    p->linkAf=q;
    delete p;
    br--;
}

void delstruct()
{
    if(!first)
    {
        return;
    }
    elem *p=first;
    while(p)
    {
        first=first->linkAf;
        delete p;
        p=first;
    }
    first=NULL;
    last=NULL;
    br=0;
}

int main()
{
    int el;
    addlast(5);
    addlast(7);
    addlast(1);
    dellast(&el);
    cout<<el<<' ';
    dellast(&el);
    cout<<el<<' ';
    dellast(&el);
    cout<<el<<' ';
    delstruct();
    return 0;
}