#include <iostream>
#include<vector>
using namespace std;
//vector<int>c;
vector<int>u;

struct DNode
{
    int info;
    DNode *prev,*next;
    DNode(int el,DNode *n=0,DNode *p=0)
    {
        next=n;
        prev=p;
        info=el;
    }
};


class doublelinked
{
public:
    DNode *head,*tail;

    doublelinked()
    {
        head=tail=0;
    }
    void addtohead(const int &el);
    void addtotail(const int &el);
    int  deletefromhead();
    int   deletefromtail();
    int    findel(const int & el);
    int    firsel();
    void cleardata();
    int size();
};
int doublelinked::size()
{
    int counter=0;
    DNode *tmp=head;
    for(tmp=head; tmp!=0; tmp=tmp->next)
    {
        counter++;
    }

    return counter;
}
void doublelinked::addtohead(const int &el)
{
    if(head == 0)
    {
        head=tail=new DNode(el);
    }
    else
    {
        head=new DNode(el,head,0);
        head->next->prev=head;
    }
}
void doublelinked::addtotail(const int &el)
{
    if(head==0)
    {
        head=tail=new DNode(el);
    }
    else
    {
        tail=new DNode(el,0,tail);
        tail->prev->next=tail;
    }
}
int doublelinked::deletefromhead()
{
    int el=head->info;
    if(head==tail)
    {
        delete head;
        head=tail=0;
    }
    else
    {
        head=head->next;
        delete head->prev;
        head->prev=0;
    }
    return el;
}
int doublelinked::deletefromtail()
{
    int el=tail->info;
    if(head==tail)
    {
        delete tail;
        head=tail=0;
    }
    else
    {
        tail=tail->prev;
        delete tail->next;
        tail->next=0;
    }
}
int doublelinked::findel(const int & el)
{
    DNode *tmp;
    for(tmp=head; tmp!=0&&(tmp->info!=el); tmp=tmp->next)
        if(tmp==0)
        {
            return 0;
        }
        else
            return el;
}
int doublelinked::firsel()
{
    return head->info;
}
void doublelinked::cleardata()
{
    for(DNode *tmp; head!=0;)
    {
        tmp=head;
        head=head->next;
        delete tmp;
    }
}

void intersection(doublelinked &a,doublelinked &b)  //complexity o(n^3)
{
    //vector<int>c;
    doublelinked *c;
    c=new doublelinked();

    if((a.head==0)||(b.head==0))
    {
        cout<<"there is no intersection"<<endl;
    }
    else
    {
        DNode*tmp=a.head;
        DNode*current=b.head;
        for(tmp=a.head; tmp!=0; tmp=tmp->next)
        {
            for(current=b.head; current!=0; current=current->next)
            {
                if(tmp->info==current->info)
                {
                    bool flag = false;
                    for(int i : c)
                    {
                        if(i==tmp->info)
                            flag =true;
                    }
                    if (flag==false)
                        //   c.push_back(tmp->info);
                        c->addtohead(tmp->info);

                }
            }
        }
        /*for(int i=0;i<c.size();i++){
            cout<<c[i]<<endl;
        }*/
        for (Node*tmp =c->head; tmp != 0; tmp = tmp->next)
        {
            cout << tmp->info << " ";
            cout << endl;
        }
    }
}

/*void uniondouble(doublelinked &a,doublelinked &b){ // complexity o(n^2)
DNode*tmp=a.head;
DNode*current=b.head;
vector<int>u;
for(tmp=a.head;tmp!=0;tmp=tmp->next){

            bool flag = false;
            for(int i : u) {
                if(i==tmp->info)
                    flag =true;
            }
            if (flag==false)
                        u.push_back(tmp->info);


}
    for(current=b.head;current!=0;current=current->next){

            bool flag = false;
            for(int i : u) {
                if(i==current->info)
                    flag =true;
            }
            if (flag==false)
                        u.push_back(current->info);

          }
    for(int i=0;i<u.size();i++){
    cout<<u[i]<<endl;
}

}*/
int main()
{
    doublelinked a,b,p;
    a.addtohead(45);
    a.addtohead(45);
    a.addtohead(78);
    b.addtohead(45);
    b.addtotail(78);
    b.addtotail(80);
    intersection(a,b);
    return 0;
}