In_depth

#include <iostream>
using namespace std;

struct node{
    node(string , node*); //this is the ctor function. Note:only data types are required
    string st;
    node* next;
};

/*
node* NewNode(string s){
    node* np = new node;
    np->st = s;
    np->next = 0;
    return np;
}
*/
//better to set ctor

node::node(string s, node* np=0){
    st = s;
    next = np;
}

void walk(node* nd){
/*  cout<< nd->st <<" "; //segfaults if nd=0
    if ( nd == 0 ) return;

    if (nd->next  !=0 )
        walk(nd->next);
*/
    //alternate better solution

    if (nd==0) return;
    cout<< nd->st <<" ";
    walk(nd->next);

}
/*
void length(node* nd, int& count){
    count += 1;
    if (nd->next != 0)
        length(nd->next, count);
    return;
}
*/

//better length function which returns int
int length(node* nd ){
    if (nd == 0) return 0;
    return 1 + length(nd->next);
}


//Must pass nd by ref or seg fault. We must change root node address in main.
void pushfront(node* &nd, string s){
    //usage: pushfront(root, "bill");

    //node* nwn = NewNode(s);
    //nwn->next = nd;
    //nd = nwn;

    //alternate using node ctor: better
    nd = new node(s,nd);

    //node* nwn = new node(s, nd);
    //nd=nwn;
}
/*
//alternate pushfront without by ref
node* pushfront(node* nd, string s){
    //creates new node and returns that node pointer
    // usage: root=pushfront(root, "bill");
    return ( new node(s, nd));
}
*/


void popfront(node* &nd){
    //usage: popfront(root)
    if (nd != 0) //can't popfront if nothing to pop
    {
        node* temp = nd->next;
        delete nd;
        nd = temp;
    }
}

//alternate popfront. Same usage but not by ref. Ok in C
/*
void popfront(node** ndp){ //instead of passing by ref
    //usage: popfront(&root)
    if (*ndp != 0)
    {
        node* temp = (*ndp)->next;
        delete *ndp;
        *ndp = temp;
    }

}
*/

//alternate popfront. Different usage: not by ref.
/*
node* popfront(node* nd){
    //usage: root = popfront(root)
    if (nd != 0)
    {
        node* temp = nd->next;
        delete nd;
        nd=0; //not necessary because nd not by ref
        return temp;
    }

}
*/


/*can't pushback on root=0 since no node exists yet. So must check for it.
copy ctor called for nd pointer so root in main not changed. This is
okay if one node already exists since we just add to the end of it.
But if no node exists yet (root=0) then we must change root addr so we
have to pass by ref also.

void pushback(node* &nd, string s){
    if (nd == 0)
    {
        nd = NewNode(s);
        return;
    }
    node* root = nd;
    while (nd->next != 0)
        nd = nd->next;
    nd->next = NewNode(s);
    nd = root; //must set nd back to root as we passed it by ref

}
*/
//better pushback

void pushback(node* &nd, string s){
    // better to pass string by ref so we do not copy s every recursive call
    if (nd == 0){ // or !nd
        nd = new node(s); //call new directly for defined struct ctor
        return;
    }
    pushback(nd->next, s);
}


void popback(node* &nd){
    if (nd == 0) return; //can't delete nothing

    /*
    if (nd->next == 0)
    {
        delete nd;
        nd = 0;
    }
    else
    {
        popback(nd->next);
    }
    */
    //better way
    if (nd->next == 0)
    {
        delete nd;
        nd = 0; //important
        return;
    }
    popback(nd->next);


}


/* must pass nd by ref since we may need to insert at the
root node and hence change the root addr */
void insert(node* &nd, string s){
    /*
    if (nd == 0)
    {
        nd = NewNode(s);
        return;
    }
    if (s < nd->st)
    {
        pushfront(nd, s);
        return;
    }
    else
    {
        insert(nd->next, s);
        return;
    }
    */

    //better alternative

    if (nd == 0 || (s <= nd->st)) // !nd is the same as nd == 0
    //note: compound if statement order matters. Second comparison is skipped if first is true.
    //this is called "short circuit evaluation" which is necessary to prevent runtime error
    // of derefencing null pointer with nd->st  when nd == 0

    {
        pushfront(nd, s); // works because pushfront is by ref
        // equivalent nd = new node(s, nd); //when node ctor is overloaded
        return;
    }
    insert(nd->next, s);
}


void lfree(node* nd){
    /*
    if (nd == 0) return; //don't crash if nothing in linked list
    if (nd->next != 0)
        lfree(nd->next);
    delete nd;
    nd = 0; //sets all linked list pointers to zero (including the first one, root=0)
    */
    //alternate better solution: recurses down to the null pointer
    if (nd == 0) return;
    lfree(nd->next); //recursion first
    cout<<"free node with string: "<< nd->st <<endl;
    delete nd;
    nd = 0;

}


int main(){

    const char* sarray[6] = {"b","d","a","e","f","c"};
    node* root=0;

    int x;
    for (x=0; x<6 ; x++)
    {
        //pushback(root, sarray[x]);
        //pushfront(root, sarray[x]);
        cout<<"insert: "<<sarray[x]<<endl;
        insert(root, sarray[x]);
        cout<<"walk"<<endl;
        walk(root);
        cout<<endl;
    }
    for (x=0; x<3 ; x++)
    {
        cout<<"popfront"<<endl;
        popfront(root);
        cout<<"walk"<<endl;
        walk(root);
        cout<<endl;
    }
    cout<<"insert: z "<<endl;
    insert(root, "z");
    cout<<"walk"<<endl;
    walk(root);
    cout<<endl;
    for (x=0; x<3 ; x++)
    {
        cout<<"popback"<<endl;
        popback(root);
        walk(root);
        cout<<endl;
    }
    cout<<"pushback aaa"<<endl;
    pushback(root, "a");
    cout<<"walk"<<endl;
    walk(root);
    cout<<endl;
    cout<<"free memory"<<endl;
    lfree(root);
    return 0;
}