#include <iostream>
#include <string>
using namespace std; template <class T>
class List
{
private:
T data;
List<T> * next;
static List<T> * tail; //指向最后一个结点
static List<T> * h; //指向头结点
public:
List():next(NULL) //构造头结点
{
h = tail = this;
}
List(T newnode):data(newnode),next(NULL) //构造新结点
{}
void append(T node)
{
tail->next=new List<T>(node);
tail=tail->next;
}//往后面添加结点
bool insert(T node, T posnode)
{
List<T> *cur,*flag;
cur=h;
while(cur->data!=posnode&&cur!=tail->next)//遇到第一个数值相等的就跳出循环，保证是第一个
{
cur=cur->next;
}
if(cur!=NULL)//防止是因为循环到尾部而跳出循环
{
if(cur->next!=NULL)//如果是尾部就按append函数的方式插入
{
List<T> *p=new List<T>(node);
flag=cur->next;
cur->next=p;
p->next=flag;
}
else//如果是链表中间就改变下前面一个和加入节点的next
{
cur->next=new List<T>(node);
tail=cur->next;
}
return true;
}
return false;
}//在结点posnode第一次出现的后面插入新结点node, 插入成功返回true，否则false
void deleteNode(T node)
{
List<T> *now;
now=h->next;
if(now->data==node)
{
if(tail==h->next)//如果b链表尾在头节点后两个节点，tail不太好写，所以拆开来写
{
h->next=NULL;
tail=h;
}
else if(tail==h->next->next)
{
h->next=h->next->next;
tail=h->next;
}
}
while(now->next!=NULL)
{
if(now->next->data==node)
now->next=now->next->next;
else
now=now->next;
}
}//删除结点,注意可能有多个值相同的结点需要删除
void delList()
{
h->next=NULL;
tail=h;
}//删除整个链表
void dispList()
{
List<T> *now;
if(h->next!=NULL)//链表不为空
{
now=h->next;
while(now!=tail->next)
{
cout<<now->data<<" ";
now=now->next;
}
}
cout<<endl;
}//显示链表
friend void print(List<T> *now);
};
template<class T>
List<T>*List<T>::tail=NULL;
template<class T>
List<T>*List<T>::h=NULL;