#include<iostream>
using namespace std;

class chain;
class node{
public:
    friend class chain;
private:
    char  _data;
    node* _next;
};

class chain{
public:
    chain();
//    ~chain();
    bool find(int n, node*& nd);   //get node n when find
    bool insert(int n, char& x);
    node* search(char& x);     //return pre node when find x, else return 0
    bool remove(char& x);          //search x, if x in chain than delete
    void display(ostream& out);
friend ostream& operator<< ( ostream& out, chain& nd);

private:
    node* _init_node;
    int   _length;
    int   _index;
};

chain::chain(){
    _init_node= new node;
    _length = 0;
    _index = -1;
}

bool chain::find(int n, node*& x){
    if(n<0 || n>_length){
    cout << "cann't find..." << endl;
    return false;
    }
    else{
    while(n--) x = x->_next;
    }
    return true;
}

bool chain::insert(int n, char& x){
    node* ahead_node=_init_node;
    if(find(n, ahead_node)){
    node* new_node = new node;
    new_node->_next = ahead_node->_next;    
    ahead_node->_next = new_node;
    new_node->_data = x;
    _length++;
    return true;
    }
    return false;
}

node* chain::search(char &x){
    node* tmp=_init_node;
    for( int i=0; i<_length; i++){
    if(tmp->_next->_data==x) return tmp;
    tmp = tmp->_next;
    }
    return 0;
}

bool chain::remove(char& x){
    node* front;
    front= search(x);
    if(front==0) {cout<< x << " not found...\n"; return false;}
    else{
    node* tmp = front->_next;
    front->_next = tmp->_next;
    delete tmp;
    _length--;
    }
    return true;
}   

void chain::display(ostream& out){
    node* tmp= _init_node->_next;
    for(int i=0; i<_length; i++){
    out << tmp->_data;
    tmp = tmp->_next;
    }
}

ostream& operator<< ( ostream& out, chain& nd){
    nd.display(out);
    return out;
}

int main(){
    chain chain1;
    char str[]="1Happy 2Mid-Autumn 3Festiavl~~";
    for(int i=0; str[i]!=0; i++){
    chain1.insert(i, str[i]);
    }
    cout << chain1 << endl;
    for(int k=0; str[k]!=0; k++){
    if(str[k] <= '9'&& str[k]>='0') chain1.remove(str[k]);
    }
    char tmp = '2'; chain1.remove(tmp);
    cout << chain1 << endl;
    return 0;
}