?????????????????????????У???????????????????????????
?????????????????洢????
????[cpp] view plain copy print?
????typedef struct Node 
????{ 
????DataType _data; 
????struct Node *_next; 
????struct Node *_front; 
????}Node; 
?????????????洢?????????????????????????????????? ?????????????????任??????????????п?????????????????????????????????????????????????????????????????????????????????????????????????????
?????????????????

??????????????????

????C++?????????????????
????[cpp] view plain copy print?
????typedef int DataType; 
????class LinkList; 
????class Node 
????{ 
????friend LinkList; 
????friend ostream &operator<<(ostream &os??Node &n); 
????friend ostream& operator<<(ostream &os??LinkList &list); 
????public: 
????Node(DataType x) 
????:_data(x) 
??????_next(NULL) 
??????_front(NULL) 
????{} 
????private: 
????DataType _data; 
????Node *_next; 
????Node *_front; 
????}; 
????ostream &operator<<(ostream &os??Node &n) 
????{ 
????os<<n._data; 
????return os; 
????} 
????class LinkList 
????{ 
????friend ostream& operator<<(ostream &os??LinkList &list); 
????public: 
????LinkList() 
????:_head(NULL) 
??????_tail(NULL) 
????{} 
????LinkList(const LinkList &list) 
????:_head(NULL) 
??????_tail(NULL) 
????{ 
????Node *cur=list._head; 
????while(cur) 
????{ 
????Node *tmp=new Node(cur->_data); 
????if(_tail) 
????{ 
????_tail->_next=tmp; 
????tmp->_front=_tail; 
????_tail=tmp; 
????} 
????else       //?????? 
????{ 
????_head=tmp; 
????_tail=tmp; 
????} 
????cur=cur->_next; 
????} 
????} 
????~LinkList() 
????{ 
????Node *cur=_head; 
????while(cur) 
????{ 
????Node *del=cur; 
????cur=cur->_next; 
????delete del; 
????del=NULL; 
????} 
????} 
????public: 
????void PushBack(DataType x) 
????{ 
????Node *NewNode=new Node(x); 
????if(_tail) 
????{ 
????_tail->_next=NewNode; 
????NewNode->_front=_tail; 
????_tail=NewNode; 
????} 
????else 
????{ 
????_head=NewNode; 
????_tail=NewNode; 
????} 
????} 
????void PopBack() 
????{ 
????if(!_head && !_tail)    //?????? 
????{ 
????cout<<"??????????β?"<<endl; 
????return ; 
????} 
????else if(_head == _tail)     //????????? 
????{ 
????delete _tail; 
????_head=NULL; 
????_tail=NULL; 
????} 
????else      //?????????????? 
????{ 
????Node *tmp=_tail; 
????_tail=tmp->_front; 
????_tail->_next=NULL; 
????delete tmp; 
????tmp=NULL; 
????} 
????} 
????void PushFront(DataType x) 
????{ 
????Node *NewNode=new Node(x); 
????if(_head) 
????{ 
????Node *tmp=_head; 
????NewNode->_next=tmp; 
????tmp->_front=NewNode; 
????} 
????else 
????{ 
????_tail=NewNode; 
????} 
????_head=NewNode;    //????? 
????} 
????void PopFront() 
????{ 
????if(!_head && !_tail)     //?????? 
????{ 
????cout<<"????????????"<<endl; 
????return ; 
????} 
????else if(_head == _tail)    //????????? 
????{ 
????delete _head; 
????_head=NULL; 
????_tail=NULL; 
????} 
????else        //?????????????? 
????{ 
????Node *del=_head; 
????_head=del->_next; 
????_head->_front=NULL; 
????delete del; 
????del=NULL; 
????} 
????} 
????Node *FindNum(DataType x) 
????{ 
????Node *cur=_head; 
????while(cur) 
????{ 
????if(cur->_data == x) 
????return cur; 
????cur=cur->_next; 
????} 
????return NULL; 
????} 
????void Insert(Node *pos??DataType x)    //?????λ?ú?? 
????{ 
????Node *NewNode=new Node(x); 
????if(pos->_next) 
????{ 
????NewNode->_front=pos; 
????NewNode->_next=pos->_next; 
????pos->_next->_front=NewNode; 
????pos->_next=NewNode; 
????} 
????else    //??????????壬????PushBack 
????{ 
????pos->_next=NewNode; 
????NewNode->_front=pos; 
????_tail=NewNode;    //????β 
????} 
????} 
????void Insert(int??Node *pos??DataType x)   //?????λ????? 
????{ 
????Node *NewNode=new Node(x); 
????if(pos->_front) 
????{ 
????NewNode->_next=pos; 
????pos->_front->_next=NewNode; 
????NewNode->_front=pos->_front; 
????pos->_front=NewNode; 
????} 
????else   //????????????壬????PushFront 
????{ 
????NewNode->_next=pos; 
????pos->_front=NewNode; 
????_head=NewNode;    //????? 
????} 
????} 
????void Remove(DataType &x) 
????{ 
????Node *pos=this->FindNum(x); 
????if(pos != NULL) 
????{ 
????if((!(pos->_front)) && pos->_next)    //??????????? 
????{ 
????Node *tmp=pos->_next; 
????tmp->_front=NULL; 
????_head=tmp; 
????} 
????else if(pos->_front && (!(pos->_next)))   //??????????? 
????{ 
????Node *tmp=pos->_front; 
????tmp->_next=NULL; 
????_tail=tmp; 
????} 
????else             //????м??? 
????{ 
????Node *front=pos->_front; 
????Node *next=pos->_next; 
????next->_front=front; 
????front->_next=next; 
????} 
????delete pos; 
????pos=NULL; 
????} 
????} 
????void RemoveAll(DataType &x) 
????{ 
????Node *cur=_head; 
????Node *ret=this->FindNum(x); 
????if(ret != _head)    //???????????????????????? 
????{ 
????while(cur) 
????{ 
????Remove(x); 
????cur=cur->_next; 
????} 
????} 
????} 
????void Sort() 
????{ 
????int flag=1; 
????Node *cur=_head; 
????Node *tail=NULL; 
????while(cur != tail) 
????{ 
????while(cur->_next != tail) 
????{ 
????if(cur->_data > cur->_next->_data) 
????{ 
????DataType tmp=cur->_data; 
????cur->_data=cur->_next->_data; 
????cur->_next->_data=tmp; 
????flag=0; 
????} 
????cur=cur->_next; 
????} 
????if(flag == 1) 
????break; 
????tail=cur; 
????cur=_head; 
????} 
????} 
????void Erase(Node *pos) 
????{ 
????if((!(pos->_front)) && pos->_next)    //??????????? 
????{ 
????Node *tmp=pos->_next; 
????tmp->_front=NULL; 
????_head=tmp; 
????} 
????else if(pos->_front && (!(pos->_next)))   //??????????? 
????{ 
????Node *tmp=pos->_front; 
????tmp->_next=NULL; 
????_tail=tmp; 
????} 
????else             //????м??? 
????{ 
????Node *front=pos->_front; 
????Node *next=pos->_next; 
????next->_front=front; 
????front->_next=next; 
????} 
????delete pos; 
????pos=NULL; 
????} 
????private: 
????Node *_head; 
????Node *_tail; 
????}; 
????ostream& operator<<(ostream &os??LinkList &list) 
????{ 
????Node *cur=list._head; 
????while(cur) 
????{ 
????os<<(*cur)<<" "; 
????cur=cur->_next; 
????} 
????return os; 
????}