#include <iostream>

using namespace std;

template<typename tip>
struct Cvor
{
    tip element;
    Cvor* pok;
};
template <typename tip> class Lista
{
protected:
public:
    Lista() {};
    virtual ~Lista() {};
    virtual int brojElemenata () const=0;
    virtual tip& trenutni()=0;
    virtual bool prethodni()=0;
    virtual bool sljedeci()=0;
    virtual void pocetak()=0;
    virtual void kraj()=0;
    virtual void obrisi()=0;
    virtual void dodajIspred(const tip& el)=0;
    virtual void dodajIza(const tip& el)=0;
    virtual tip &operator[](tip el)=0;
    virtual tip operator[](tip el) const=0;
};
template<typename tip> class NizLista: public Lista<tip>
{
    tip* pok;
    tip* tren;
    int vel;
public:
    NizLista(): vel(0), pok(nullptr), tren(nullptr) {}
    NizLista(int n)
    {
        tren=new tip [n];
        pok=tren;
        vel=n;
    }
    ~NizLista()
    {
        delete [] pok;
    }
    int brojElemenata() const
    {
        return vel;
    }
    tip& trenutni()
    {
        return *tren;
    }
    bool prethodni()
    {
        if(tren==pok) return false;
        tren--;
        return true;
    }
    bool sljedeci()
    {
        if(tren==&pok[vel-1]) return false;
        tren++;
        return true;
    }
    void pocetak()
    {
        tren=&pok[0];
    }
    tip& DajPocetak()
    {
        return pok;
    }
    tip& DajKraj()
    {
        return pok[vel-1];
    }
    void kraj()
    {
        tren=&pok[vel-1];
    }
    void obrisi()
    {
        if(vel==1)
        {
            vel=0;
            delete [] pok;
            pok==nullptr;
            tren=nullptr;
        }
        else
        {
            tip* pom=new tip[vel-1];
            bool test(false), jelzadnji(tren==&pok[vel-1]);
            for(int i(0); i<vel; i++)
            {
                if((pok[i]==this->trenutni() && !(test)))
                {
                    if(jelzadnji)
                    {
                        tren=&pom[i-1];
                        continue;
                    }
                    test=true;
                    tren=&pom[i];
                    pom[i]=pok[i+1];
                    continue;
                }
                if(!test)pom[i]=pok[i];
                else pom[i]=pok[i+1];
            }
            delete[] pok;
            pok=pom;
            vel--;
        }

    }
    void dodajIza(const tip& el)
    {
        if(vel==0)
        {
            pok=new tip (el);
            tren=pok;
            vel++;
        }
        else
        {
            tip* pom=new tip[vel+1];
            bool test(false);
            for(int i(0); i<vel+1; i++)
            {
                if(tren==&pok[i])
                {
                    test=true;
                    tren=&pom[i];
                    pom[i]=pok[i];
                    pom[i+1]=el;
                    i++;
                    continue;
                }
                if(!test) pom[i]=pok[i];
                else pom[i]=pok[i-1];
            }
            delete[] pok;
            pok=pom;
            vel++;
        }
    }
    void dodajIspred(const tip& el)
    {
        if(vel==0)
        {
            pok=new tip (el);
            tren=pok;
            vel++;
        }
        else
        {
            tip* pom=new tip[vel+1];
            bool test1(false), test2(false);
            for(int i(0); i<vel+1; i++)
            {
                if(tren==&pok[i+1])
                {
                    test1=true;
                    tren=&pom[i+2];
                    pom[i+1]=el;
                    pom[i]=pok[i];
                    i++;
                    continue;
                }
                if(tren==&pok[i])
                {
                    test2=true;
                    tren=&pom[i+1];
                    pom[i]=el;
                    pom[i+1]=pok[i];
                    break;
                }
                if(!test1) pom[i]=pok[i];
                else pom[i]=pok[i-1];
            }
            delete[] pok;
            pok=pom;
            vel++;
        }
    }
    tip &operator[](int n)
    {
        if(n<0 || n>vel) throw "nesta";
        return pok[n];
    }
    tip operator[](int n) const
    {
        if(n<0 || n>vel) throw "nesta";
        return pok[n];
    }
};
template<typename tip> class JednostrukaLista: public Lista<tip>
{
    int vel;
    Cvor<tip>* p;
    Cvor<tip>* t;
    Cvor<tip>* k;

public:
    JednostrukaLista(): vel(0), p(nullptr), t(nullptr) {}
    ~JednostrukaLista()
    {
        for(int i(0); i<vel; i++)
        {
            delete p;
        }
        p=nullptr;
        t=nullptr;
        vel=0;
    }
    int brojElemenata () const
    {
        return vel;
    }
    tip& trenutni()
    {
        return t->element;
    }
    bool prethodni()
    {
        if(p==t) return false;
        int br;
        Cvor<tip>* pom(p);
        for(br=0; br<t-p-1; br++)
        {
            pom=pom->pok;
        }
        t=pom;
    }
    bool sljedeci()
    {
        if(t==k) return false;
        t=t->pok;
        return true;
    }
    void pocetak()
    {
        t=p;
    }
    void kraj()
    {
        t=k;
    }
    void obrisi()
    {
        if(vel==1)
        {
            delete t;
        }
        else
        {
            if(t!=p)
            {
                Cvor<tip>* pom(p);
                while(pom->pok!=t)
            {
                pom=pom->pok;
            }
            pom->pok=t->pok;
            delete t;
            t=pom;
            }
            else
            {
                k->pok=t->pok;
                p=t->pok;
                delete t;
                t=p;
            }
        }
        vel--;
    }
    void dodajIspred(const tip& el)
    {
        if(vel==0)
        {
            p=new Cvor<tip>;
            p->element=el;
            t=p;
            k=p;

        }
        else
        {
            Cvor<tip>* pocetni;
            if(vel==1)
            {
                pocetni=new Cvor<tip>;
                pocetni->pok=p;
                pocetni->element=el;
                p=pocetni;
                k->pok=p;
            }
            else
            {
                pocetni=p;
                while(p->pok!=t)
                {
                    p=p->pok;
                }
                p->pok=new Cvor<tip>;
                p->element=el;
                p->pok->pok=t;
                p=pocetni;

            }
        }
        vel++;
    }
    void dodajIza(const tip& el)
    {
        if(vel==0)
        {
            p=new Cvor<tip>;
            p->element=el;
            t=p;
            k=p;
        }
        else
        {
            Cvor<tip>* trenutak=new Cvor<tip>;
            trenutak->element=el;
            trenutak->pok=t->pok;
            t->pok=trenutak;
            if(k==p || k==t)
            {
                k=t->pok;
            }
        }
        vel++;
    }
    tip &operator[](int el)
    {
        Cvor<tip>* kretanje(p);
        for(int i(0); i<el; i++)
        {
            kretanje=kretanje->pok;
        }
        return kretanje->element;
    }
    tip operator[](int el) const
    {
        Cvor<tip>* kretanje(p);
        for(int i(0); i<el; i++)
        {
            kretanje=kretanje->pok;
        }
        return kretanje->element;
    }
};
int main()
{

}