#include <iostream>
#include <stdlib.h>
using namespace std;

struct node
{
    int data;
    node* link;
    node* trace;
};

void check(node* h);
void checkback(node* t);
int menu(node* h,node* t);
int pozicija(node*& h,node*& t);
int prepozicija(node*& h,node*& t);
int newlist(node*& h,node*& t);
void change (node* h);
int trint (node*& h,node*& t);
void ieskot(node* h,node*t);
void cls()
{
system ("CLS");
}
int main()
{
node* h=NULL;
node* t=NULL;
menu(h,t);
    return 0;
}
void check(node* h)
{
    int i=1;
    node* temp;
    temp=h;
    if (h!=NULL) {
while(temp->link!=NULL){
    cout<<"Saraso skaicius "<<i<<": "<<temp->data<<endl;
    temp=temp->link;
    i++;
}
cout<<"Saraso skaicius "<<i<<": "<<temp->data<<endl<<endl<<endl;
}
else
{   cls();
    cout<<"Sarasas neegzistuoja\n\n";
}
}
int menu(node* h,node* t)
{
int i=0;
    cout<<"pasirinkite funkcija: \n\nSkaiciu ne is saraso) Isjungti programa\n1) atspausdinti sarasa\n2) Perziureti saraso nuo galo\n3) iterpti nauja elementai nurodyta pozicija\n4) Iterpti skaiciu pries tam tikra pozicija\n5) iterpti elementa vietoj tam tikro elemento\n6) Sukurti nauja sarasa\n7) Istrinti dabartini sarasa"<<endl;
    cin>>i;
    if (i==0) {exit(0);}
    if (i==1) {cls();check(h);menu(h,t);}
    if (i==2) {cls();checkback(t);menu(h,t);}
    if (i==3) {cls();check(h);pozicija(h,t);menu(h,t);}
    if (i==4) {cls();check(h);prepozicija(h,t);menu(h,t);}
    if (i==5) {cls();check(h);change(h);menu(h,t);}
    if (i==6) {cls();newlist(h,t);menu(h,t);}
    if (i==7) {cls();trint(h,t);menu(h,t);}
    if (i==8) {cls();ieskot(h,t);menu(h,t);}
}
int pozicija(node*& h, node*& t)
{
    int a,b,i,tikr=0;
    cout<<"Pasirinkite i kuria pozicija norite iterpti skaiciu: ";cin>>a;
    cout<<"Iveskite savo skaiciu: ";cin>>b;
    node* temp=h;
    node* l;
if (a==1)
{
node* temp1=new node;
temp1->data=b;
temp1->link=h;
temp1->trace=NULL;
h->trace=temp1;
h=temp1;
tikr=1;
}
for (i=2;i<=a && temp!=NULL;i++)
{
    l=temp;
    temp=temp->link;
    if (a==i)
    {
        if(temp==t)
        {
        node* temp1=new node;
        temp1->data=b;
        temp1->link=temp;
        temp1->trace=l;
        l->link=temp1;
        temp->trace=temp1;
        tikr=1;
        }
        else if(l==t)
        {
        node* temp1=new node;
        temp1->data=b;
        temp1->link=NULL;
        temp1->trace=l;
        t=temp1;
        l->link=temp1;
        tikr=1;
        }
        else
        {
        node* temp1=new node;
        temp1->data=b;
        temp1->link=temp;
        temp1->trace=l;
        l->link=temp1;
        temp->trace=temp1;
        tikr=1;
        }
    }
}
cls();
if (tikr==1){cout<<"Skaicius "<<b<<" iterptas i pozicija "<<a<<endl;}
else {cout<<"Skaiciaus iterpti nepavyko....\n";}
}
int prepozicija(node*& h, node*& t)
{
    int a,b,i,tikr=0;
    cout<<"Pasirinkite pozicija pries kuria norite iterpti skaiciu: ";cin>>a;
    cout<<"Iveskite savo skaiciu: ";cin>>b;
    node* temp=h;
    node* l;
if (temp->data==a)
{
    cout<<"rastas skaicius";
node* temp1=new node;
temp1->data=b;
temp1->link=h;
temp1->trace=NULL;
h->trace=temp1;
h=temp1;
tikr=1;
}
for (;temp->link!=NULL;)
{
    l=temp;
    temp=temp->link;
    if (temp->data==a)
    {
        if(temp==t)
        {
        node* temp1=new node;
        temp1->data=b;
        temp1->link=temp;
        temp1->trace=l;
        l->link=temp1;
        temp->trace=temp1;
        tikr=1;
        }
        else if(l==t)
        {
        node* temp1=new node;
        temp1->data=b;
        temp1->link=NULL;
        temp1->trace=l;
        t=temp1;
        l->link=temp1;
        tikr=1;
        }
        else
        {
        node* temp1=new node;
        temp1->data=b;
        temp1->link=temp;
        temp1->trace=l;
        l->link=temp1;
        temp->trace=temp1;
        tikr=1;
        }
    }
}
cls();
if (tikr==1){cout<<"Skaicius "<<b<<" iterptas pries pozicija "<<a<<endl;}
else {cout<<"Skaiciaus iterpti nepavyko....\n";}
}
int newlist(node*& h,node*& t)
{
    int i,ii;
node* l;
if (h==NULL){
//node* temp=new node;
node* l;
cout<<"Iveskite kiek bus skaiciu sarase: ";cin>>ii;
for(i=0;i<ii;i++)
{
node* temp1=new node;
    cout<<"iveskite "<<i+1<<" skaiciu: ";
    cin>>temp1->data;
    temp1->link=NULL;
    if (i==0)
    {
        h=temp1;
        t=temp1;
        temp1->trace=NULL;
        temp1->link=NULL;
    }
    else
    {
        l->link=temp1;
        temp1->trace=l;
        t=temp1;
    }
l=temp1;
}
cls();
}else{cout<<"Sarasas jau egzistuoja, pirmiausia reikia ji istrinti\n\n}";}
}
void change(node* h)
{
int a,b,c=0;
cout<<"Iveskite skaiciu kuri norite pakeisti: ";cin>>a;
cout<<"Iveskite skaiciu kuriuo norite pakeisti: ";cin>>b;
cls();
    int i=1;
    node* temp;
    temp=h;
    if (h!=NULL)
    {
        while(temp->link!=NULL)
        {
            if (a==temp->data)
            {
            temp->data=b;
            c=1;
            cout<<"Rastas skaicius "<<a<<" jis pakeistas skaiciu: "<<temp->data<<endl;
            }
        temp=temp->link;
        i++;
        }
    if (a==temp->data)
    {
    temp->data=b;
    c=1;
    cout<<"Rastas skaicius "<<a<<" jis pakeistas skaiciu: "<<temp->data<<endl;
    }
    }
    if (h==NULL)
    {
    cls();
    cout<<"Sarasas neegzistuoja"<<endl;
    }
    if (c==0)
    {
    cout<<"Skaicius nerastas...\n"<<endl;
    }
}
int trint(node*& h,node*& t)
{
    node* kitas;
    node* temp=h;
    temp=h;
    while (temp->link!=NULL)
    {
        kitas=temp->link;
        delete temp;
        temp=kitas;
    }
    delete temp;
    h=NULL;
    t=NULL;
}
void checkback(node* t)
{
    int i=1;
    node* temp;
    temp=t;
    if (t!=NULL) {
cout << "pirmas loop atliktas, i=" << i << endl;
while(temp->trace!=NULL)
{
i++;
temp=temp->trace;
cout<<"pirmas loop atliktas, i="<<i<<endl;
}
temp=t;
while (i!=0)
{cout<<"Saraso skaicius "<<i<<": "<<temp->data<<endl;
    temp=temp->trace;
i--;
}
}
else
{   cls();
    cout<<"Sarasas neegzistuoja\n\n";
}
}
void ieskot(node* h,node*t)
{
node* temp;
int a,i;
cout<<"Iveskite skaiciu kurio norite ieskoti: ";
cin>>a;
cls();
for (temp=h,i=1;temp!=t;temp=temp->link,i++)
{
    if(temp->data==a)
    {
        cout<<"Rastas #"<<i<<" skaicius "<<a<<endl;
    }



}
if(temp->data==a)
    {
        cout<<"Rastas #"<<i<<" skaicius "<<a<<endl;
    }
cout<<endl;
}