#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;
??? }