#include<iostream>
using namespace std;
typedef int T;

class Node{
      T data;
      Node *next;
public:
       Node(T t):data(t),next(NULL){}
       friend class List;     
       };
     
class List{
      Node * head;
      int len;
public:
        List(int len=0):len(len),head(NULL){}
        ~List(){clear();}
        Node* & getp( int pos );　
        void insert( T d, int pos=0 );//插入
        int size();
        bool empty();
        void travel();//遍历
        void clear();
        int find( T d );//查找
        bool update( T d1, T d2 );//更新
        bool erase( T d );//删除
        T getHead();
        T getTail();
        void reverse();
      };
void List::insert(T d,int pos){
     Node *p=new Node(d);
     Node *&pn=getp(pos);
     p->next=pn;
     pn=p;
     ++len;
     }
    
Node*& List::getp(int pos){//返回一个引用而不是一个复制的数据
     if(pos<0||pos>len)
            pos=len;                  
     if(pos==0)
             return head;
       Node*p=head;     
     for(int i=0;i<pos-1;i++)
            p=p->next;
     return p->next;
     }
int List::size(){
    return len;
    }
bool List::empty(){
     return head==NULL;
     } 
      
void List::clear(){
      while(head!=NULL){
     Node *p =head->next;
     delete head;
     head=p;
     }  
     len=0 ;               
     }
void List::travel(){
     Node*p=head;
     while(p!=NULL){
     cout<<p->data<<' ';
     p=p->next;              
     }
     cout<<endl;  
     }
int List::find( T d ){
     Node*p=head;
     int pos=0;
    
     while(p!=NULL){
        if(d==p->data)
            return pos;
        p=p->next;
        ++pos;               
     }    
           return -1;
     }
bool List::update( T d1, T d2 ){
     int t=find(d1);
     if(t==-1)
       return false;
     Node*&p=getp(t);
     p->data=d2;
     return true;
     }
bool List:: erase(T d){
     int t=find(d);
     if(t==-1)
       return false;
      Node*&pn=getp(t);
      Node*p=pn;
      pn=pn->next;
      delete p;
      --len;     
     return true;
     }
 void List:: reverse(){
      Node *ph=head;
      Node *p=NULL;
      head=NULL;
      while(ph!=NULL){
        p=ph;
        ph=ph->next;
       
        p->next=head;
        head=p;
     }
    
      }
     
T List::getHead(){
      if(empty())
          return T();          
        return head->data;         
      }
T  List::getTail(){
      if(empty())
           return T();
       return getp(len-1)->data;            
      }
int main(){
    List obj;
 obj.reverse();
 obj.travel();
 obj.insert(1,-1);
 obj.insert(2,-1);
 obj.insert(3,-1);
 obj.insert(4,-1);
 obj.insert(5);
 obj.insert(6);
 obj.insert(7);
 obj.insert(8);
 obj.insert(60,6);
 obj.insert(40,4);
 obj.insert(20,2);
 obj.travel();
 obj.reverse();
 obj.travel();
    cout<<obj.find(60)<<endl;
 obj.update(20,600);
 obj.travel();
 obj.erase(600);
 obj.travel();
 cout<<obj.getHead()<<' '<<obj.getTail()<<endl;
 int t;
 cin>>t;
 return 0;
    }