#include<iostream>

using namespace std;

template <class T>
class LinearList
{
public:
    LinearList()   
    {
        head=NULL;
        T x;
        cout<<"input the num:";
        cin>>x;
        Node*tail;
        while(x!=0)
        {
            Node*p=new Node;
            p->num=x;
            p->next=NULL;
            if(head==NULL)
                head=p;
            else
                tail->next=p;
            tail=p;
            cin>>x;
        }
    }
    ~LinearList()
    {
        delete head;
    }
    LinearList(const LinearList&s);
    LinearList& operator=(const LinearList&s)
    {
        while(head!=NULL)
        {
            Node*p=head;
            head=head->next;
            delete p;
        }

        Node*p1=head,*p2=s.head;
        while(p2!=NULL)
        {
            p1->num=p2->num;
            p1=p1->next;
            p2=p2->next;
        }
        return *this;

    }
    void dispaly();
    void sort();
    void insert(const int x);
    void del(const int x);
private:

    struct Node
    {
        T num;
        Node*next;
    };
    Node*head;
};

template <class T>
LinearList<T>::LinearList(const LinearList<T>&s)
{
    Node*p0=s.head;
    head=NULL;
    Node*tail;
    while(p0->num!=0)
    {
        Node*p=new Node;
        p->num=p0->num;
        p->next=NULL;
        if(head==NULL)
            head=p;
        else
            tail->next=p;
        tail=p;
        p0=p0->next;
    }
}


template <class T>
void LinearList<T>::dispaly()
{
    Node*p=head;
    while(p!=NULL)
    {
        cout<<p->num<<" ";
        p=p->next;
    }
    cout<<endl;
}

template <class T>
void LinearList<T>::sort()
{
    for(Node*p1=head;p1->next!=NULL;p1=p1->next)
        for(Node*p2=p1->next;p2!=NULL;p2=p2->next)
            if(p1->num>p2->num)
            {
                T temp=p1->num;
                p1->num=p2->num;
                p2->num=temp;
            }
}

template <class T>
void LinearList<T>::insert(int x)
{

    Node*p1=head,*p2;
    Node*p0=new Node;
    p0->num=(T)x;
    if (head==NULL)
    {
        p0->next=head;
        head=p0;
    }
    if (p0->num<=head->num)
    {
        p0->next=head;
        head=p0;
    }
    for(;p1!=NULL;p1=p1->next)
    {
        if(p1->num>=p0->num)
            break;
        p2=p1;
    }
    if (p1==NULL)
    {
        p2->next=p0;
        p0->next=NULL;
    }
    else
    {
        p2->next=p0;
        p0->next=p1;
    }
}

template <class T>
void LinearList<T>::del(int x)
{
    Node*p1=head,*p2;
    if(head==NULL)
    {
        cout<<"the link is empty!"<<endl;
        exit(-1);
    }
    if (p1->num==(T)x)
    {
        head=head->next;
        delete p1;
    }
    for(;p1!=NULL;p1=p1->next)
    {
        if(p1->num>=(T)x)
            break;
        p2=p1;
    }
    if (p1==NULL)
    {
        cout<<"no the jiedian!"<<endl;
    }
    else
    {
        p2->next=p1->next;
        delete p1;
    }
}

int main()
{
    LinearList<int> a;
    a.dispaly();
    a.sort();
    a.dispaly();
    a.insert(4);
    a.dispaly();
    a.del(3);
    a.dispaly();


    LinearList<double> d;
   
    d.sort();
    d.dispaly();
    d.insert(4.0);
    d.dispaly();
    d.del(3.0);
    d.dispaly();
   
    LinearList<double> e(d);
    e.dispaly();
   

    return 0;
}