Desktop Programming > C/C++ & Visual C++

6 Fast Steps to a C++ template class List

(1/3) > >>

David:
Update:  please see this next link:

http://developers-heaven.net/forum/index.php/topic,2636.0.html

FREE homework help NOW available ...

You can contact me via:
http://sites.google.com/site/andeveryeyeshallseehim/home/he-comes
http://developers-heaven.net/forum/index.php/topic,2587.0.html

This section is designed to help new C++ students 'to see something of' ...

the progression in coding ...

from a simple struct Node, 

that has a data element and a pointer to the next Node element ...

to code for a functioning template class list

with iterators to traverse the list and access the data in a Node ...


Please see the comments in each of the 6 programming steps below.

In the 5th and 6th steps the code for the List class is in its own .h file

(these .h files follow the respective test programs, for programming steps 5 and 6 ... )


You may also like to see these steps ...
http://developers-heaven.net/forum/index.php/topic,2629.0.html


OK ... here is step one ...


--- Code: ---// List_step1.cpp //  // 2013-05-08 //

// design a struct to hold data and a 'next' address i.e. a link to 'next' Node
// here, at step 1, we will just be holding, for the data, an int ...
// NOTE how C++ facilites, via a constructor, assigning initial values ...

#include <iostream>

using namespace std;

struct Node
{
    int data;
    Node* next;

    // ctor ... handles both cases of default ctor and value passed ctor ...
    // if call Node myNode; in your program, default value for int data is 0
    // if call Node myNode(7); in your program, default value for int data is 7
    // Note that the value assigned to next is NULL in both of the above cases
    Node( int dt = 0 ) : data(dt), next(NULL) {}

};

void print( const Node* cur )
{
    cout << cur->data;
}



// NOTE below that head is a pointer to Node
// AND updated by being passed in (and back) by C++ reference style passing
void push_back( Node*& head, int n )
{
Node* newNode = new Node( n );
Node* cur = head;

    if( cur ) // not first node
    {
        while( cur )
        {
            if( cur->next == NULL )
            {
                cur->next = newNode;
                return;
            }
            else cur = cur->next;
        }
    }
    else head = newNode;
}

//delete specific item ...
void deleteItem( Node*& head, int item )
{
    Node* cur = head; // get copy
    Node* prev = NULL;


    while( cur )
    {
        if( cur->data == item ) break;
        prev = cur;
        cur = cur->next;
    }

    // test end conditions ...

    if( cur ) // was found
    {
        if( prev ) // was not first node, so prev and cur exist
        {
            prev->next = cur->next; // skip over cur ...
            delete cur;
        }
        else // was first node
        {
            head = head->next;
            delete cur;
        }

    }
    else cout << "\nNot found ...\n";
}

void printAll( const Node* cur )
{
    if( !cur )
    {
        cout << "\nThe list is empty ... so can't print anything ...\n";
        return;
    }

    while( cur )
    {
        print( cur );
        cout << " ";
        cur = cur->next;
    }
    cout << endl;
}

void clean( Node*& cur ) // updated head to NULL when done
{
    while( cur )
    {
        Node* delNode = cur;
        cur = cur->next;
        delete delNode;
    }
}



int main()
{

    // NOTE!  'head' MUST be initialled to NULL for push_back etc to work ... //
    Node* head = NULL;

    push_back( head, 10 );
    push_back( head, 30 );
    push_back( head, 20 );
    push_back( head, 40 );

    printAll( head );

    cout << "\ndeleting 20 ... \n";
    deleteItem( head, 20 );
    printAll( head );

    cout << "\ndeleting 10 ... \n";
    deleteItem( head, 10 );
    printAll( head );

    cout << "\nclean list ... \n";
    clean( head );
    printAll( head );

    cout << "\nPress 'Enter' to continue/exit ... " << flush;
    cin.get();
}

--- End code ---

David:
Step 2 ... 


Please see comments at top of code ...



--- Code: ---// List_step2.cpp //  // 2013-05-08 //

// Note that here we add a struct 'List' to hold (to track)
// the head and tail addresses ... (of the Node struct's in our List)

// we also track the size (i.e the length of the List)

// NOTE that we have moved our functions that work on our List to now being
// inside the C++ struct List (namespace)

// And since we have data members head, tail and size declared inside our List,
// we do NOT have to pass these values (back and forth now) to the List
// member functions ... since these List member functions have access to these
// data mambers as if they were 'global valiables' ...
// but with the 'global scope of access limited now' ... to just be available
// to things inside a 'List::' scoped namespace


#include <iostream>

using namespace std;

struct Node
{
    int val;
    Node* next;

    // default ctor ...and value passed in ...ctor(s)...
    // (this code handles both)
    // Note initialization list and how default values are handled here...
    Node( int vl = 0 ) : val( vl ), next( NULL ) {}

    // can define functions inside a C++ struct (or class)
    // to work on 'this' data inside 'this' Node ... if we wish
    void print() const
    {
        cout << val;
    }
} ;


struct List
{
    Node* head;
    Node* tail;
    int size;


    // default ctor with initialization list ...
    List() : head( NULL ), tail( NULL ), size( 0 ) {}
    ~List() { clear() ; }


    void push_back( int val );
    void push_front( int val );

    // erase FIRST node with this val (if it exists in list)
    bool erase( int val );
    void print() const ;
    void clear();

    int get_size() const { return size; }
} ;


void List::push_back( int val )
{
    Node* newNode = new Node( val );

    if( size ) // then newNode not first node
    {
        tail->next = newNode;
        tail = newNode;
    }
    else head = tail = newNode;

    ++ size;
}
void List::push_front( int val )
{
    Node* newNode = new Node( val );
    newNode->next = head;
    head = newNode; // can now update head ...

    if( ++size == 1 ) tail = newNode;
}

bool List::erase( int val ) // erase FIRST node with this val (if it exists in list)
{
    Node* cur = head; // get copy
    Node* prev = NULL;

    while( cur )
    {
        if( cur->val == val ) break;
        prev = cur;
        cur = cur->next;
    }

    // test end conditions ...

    if( cur ) // was found
    {
        if( prev ) // was not first node, so prev and cur exist
            prev->next = cur->next; // skip over cur ...

        else // was first node
            head = head->next;

        if( cur == tail ) tail = prev;

        delete cur;

        -- size;
        return true; // was erased ...
    }
    // else cout << "\nNot found ...\n";
    return false;
}

void List::print() const
{
    if( !head )
    {
        cout << "\nThe list is empty ... so can't print anything ...\n";
        return;
    }

    Node* cur = head;
    while( cur )
    {
        cur->print();
        cout << " ";

        cur = cur->next;
    }
    cout << endl;
}

void List::clear()
{
    Node* cur;
    while( head )
    {
        cur = head;
        head = head->next; // head set to NULL at end of loop //
        delete cur;
    }
    tail = NULL;
    size = 0;
}




int main()
{

    List myLst;

    myLst.push_back( 10 );
    myLst.push_back( 30 );
    myLst.push_back( 20 );
    myLst.push_back( 40 );

    myLst.print();

    cout << "\ndeleting 20 ... \n";
    myLst.erase( 20 );
    myLst.print();

    cout << "\ndeleting 40 ... \n";
    myLst.erase( 40 );
    myLst.print();

    cout << "\nclear list ... \n";
    myLst.clear();
    myLst.print();

    cout << "\nPress 'Enter' to continue/exit ... " << flush;
    cin.get();

}

--- End code ---

David:
Step 3 ...


Please see comments at top of code ...



--- Code: ---// List_step3.cpp //  // 2013-05-08 //

// Note: here we have moved our struct Node inside
// NOW using class List (instead of struct list ...

// Note: public and private labels and sections ...
// to limit public access to public parts ...

// So here ... struct Node is defined inside List (and as) private wrt List ...
// So access to Node is, NOW HERE, limited to inside the List:: scope ...

// Note: public access is available by (and linmited by) ...  the ...
// List public member functions

// Note also, that here we have moved our definitions to all be inside ...
// the List declaration ... just to show this alternative coding style ...
// so that, now by default ... we ask ...
// the compuler to generate 'inline function calls' ...
// for all these function calls,
// whenever they are called now, from our program


#include <iostream>

using namespace std;


class List
{
public:

    // default ctor with initialization list ...
    List() : head( 0 ), tail( 0 ), size( 0 ) {}

    ~List() { clear() ; }

    void push_back( int val )
    {
        Node* newNode = new Node( val );

        if( size ) // then newNode not first node
        {
            tail->next = newNode;
            tail = newNode;
        }
        else head = tail = newNode;

        ++ size;
    }
    void push_front( int val )
    {
        Node* newNode = new Node( val );
        newNode->next = head;
        head = newNode; // can now update head ...

        if( ++size == 1 ) tail = newNode;
    }

    bool erase( int val ) // erase FIRST node with this val (if it exists in list)
    {
        Node* cur = head; // get copy
        Node* prev = 0;

        while( cur )
        {
            if( cur->val == val ) break;
            prev = cur;
            cur = cur->next;
        }

        // test end conditions ...

        if( cur ) // was found
        {
            if( prev ) // was not first node, so prev and cur exist
                prev->next = cur->next; // skip over cur ...

            else // was first node
                head = head->next;

            if( cur == tail ) tail = prev;

            delete cur;

            -- size;
            return true; // was erased ...
        }
        // else cout << "\nNot found ...\n";
        return false;
    }

    void print() const
    {
        if( !head )
        {
            cout << "\nThe list is empty ... so can't print anything ...\n";
            return;
        }

        Node* cur = head;
        while( cur )
        {
            cur->print();
            cout << ", ";

            cur = cur->next;
        }
        cout << "the size now is " << size << endl;
    }

    void clear()
    {
        Node* cur;
        while( head )
        {
            cur = head;
            head = head->next; // head set to 0 at end of loop //
            delete cur;
        }
        tail = 0;
        size = 0;
    }

    int get_size() const { return size; }

private:

    struct Node
    {
        int val;
        Node* next;

        // default ...and value passed in ...ctor(s)... (this code handles both)
        // Note initialization list and how default values are handled here...
        Node( int vl = 0 ) : val( vl ), next( 0 ) {}

        void print() const
        {
            cout << val;
        }
    } ;

    Node* head;
    Node* tail;
    int size;
} ;



int main()
{

    List myLst;

    myLst.push_back( 10 );
    myLst.push_back( 30 );
    myLst.push_back( 20 );
    myLst.push_back( 40 );

    myLst.print();

    cout << "\ndeleting 20 ... \n";
    myLst.erase( 20 );
    myLst.print();

    cout << "\ndeleting 40 ... \n";
    myLst.erase( 40 );
    myLst.print();

    cout << "\nclear list ... \n";
    myLst.clear();
    myLst.print();
    cout << "\nNow myLst.get_size() = " << myLst.get_size();

    cout << "\n\nPress 'Enter' to continue/exit ... " << flush;
    cin.get();

}

--- End code ---

David:
Step 4 ...


Please see comments at top of code ...



--- Code: ---// List_step4.cpp //  // 2013-05-08 //

// Note that here we have added a copy constructor and overloaded operator =

#include <iostream>

using namespace std;


class List
{
public:

    // default ctor with initialization list ...
    List() : head( 0 ), tail( 0 ), size( 0 ) {}

    ~List() { clear() ; }

    List( const List& old )
    {
        head = tail = 0;
        size = 0;
        Node* cur = old.head;
        while( cur ) {  push_back( cur->val ); cur = cur->next; }
    }

    List& operator = ( const List& old )
    {
        if( this != &old )
        {
            clear();
            //head = tail = 0;
            //size = 0;
            Node* cur = old.head;
            while( cur ) {  push_back( cur->val ); cur = cur->next; }
        }
        return *this;
    }

    void push_back( int val )
    {
        Node* newNode = new Node( val );

        if( size ) // then newNode not first node
        {
            tail->next = newNode;
            tail = newNode;
        }
        else head = tail = newNode;

        ++ size;
    }
    void push_front( int val )
    {
        Node* newNode = new Node( val );
        newNode->next = head;
        head = newNode; // can now update head ...

        if( ++size == 1 ) tail = newNode;
    }

    bool erase( int val ) // erase FIRST node with this val (if it exists in list)
    {
        Node* cur = head; // get copy
        Node* prev = 0;

        while( cur )
        {
            if( cur->val == val ) break;
            prev = cur;
            cur = cur->next;
        }

        // test end conditions ...

        if( cur ) // was found
        {
            if( prev ) // was not first node, so prev and cur exist
                prev->next = cur->next; // skip over cur ...

            else // was first node
                head = head->next;

            if( cur == tail ) tail = prev;

            delete cur;

            -- size;
            return true; // was erased ...
        }
        // else cout << "\nNot found ...\n";
        return false;
    }

    void print() const
    {
        if( !head )
        {
            cout << "\nThe list is empty ... so can't print anything ...\n";
            return;
        }

        Node* cur = head;
        while( cur )
        {
            cur->print();
            cout << " ";

            cur = cur->next;
        }
        cout << endl;
    }

    void clear()
    {
        Node* cur;
        while( head )
        {
            cur = head;
            head = head->next; // head set to 0 at end of loop //
            delete cur;
        }
        tail = 0;
        size = 0;
    }

    int get_size() const { return size; }

private:

    struct Node
    {
        int val;
        Node* next;

        // default ...and value passed in ...ctor(s)... (this code handles both)
        // Note initialization list and how default values are handled here...
        Node( int value = 0 ) : val( value ), next( 0 ) {}

        void print() const
        {
            cout << val;
        }
    } ;

    Node* head;
    Node* tail;
    int size;
} ;



int main()
{

    List myLst;

    myLst.push_back( 10 );
    myLst.push_back( 30 );
    myLst.push_back( 20 );
    myLst.push_back( 40 );


    cout << "Showing myLst ...\n";
    myLst.print();
    List myLst2 = myLst;

    cout << "\ndeleting 20 ... \n";
    myLst.erase( 20 );
    cout << "Showing myLst ...\n";
    myLst.print();

    cout << "\ndeleting 40 ... \n";
    myLst.erase( 40 );
    cout << "Showing myLst ...\n";
    myLst.print();

    cout << "\nclear list ... \n";
    myLst.clear();
    cout << "Showing myLst ...\n";
    myLst.print();

    cout << "\nShowing myLst2 ...\n";
    myLst2.print();

    cout << "\nPress 'Enter' to continue/exit ... " << flush;
    cin.get();

}

--- End code ---

David:
Step 5 ... (2 files)


Please see comments at top of code ...


Firstly the test program ... then following ... the .h file


--- Code: ---// List_step5.cpp //  // 2013-05-08 //

// Note that here we have moved out class List (of int) code
// ... into a separate .h file

#include "classList_SLL.h"

#include <iostream>
#include <fstream>

using namespace std;


int main()
{
    List myLst;

    myLst.push_back( 10 );
    myLst.push_back( 30 );
    myLst.push_back( 20 );
    myLst.push_back( 40 );

    cout << "Showing myLst ...\n";
    myLst.print();
    List  myLst2 = myLst;

    cout << "\ndeleting 20 ... \n";
    myLst.erase( 20 );
    cout << "Showing myLst ...\n";
    myLst.print();

    cout << "\ndeleting 40 ... \n";
    myLst.erase( 40 );
    cout << "Showing myLst ...\n";
    myLst.print();

    cout << "\nclear list ... \n";
    myLst.clear();
    cout << "Showing myLst ...\n";
    myLst.print();

    cout << "\nShowing myLst2 ...\n";
    myLst2.print();

    cout << "\nPress 'Enter' to continue/exit ... " << flush;
    cin.get();
}

--- End code ---


Now the .h file ...


--- Code: ---// classList_SLL.h //  // 2013-05-07 //


#ifndef CLASSLIST_SLL_H
#define CLASSLIST_SLL_H

#include <iostream>

class List
{
public:

    // default ctor with initialization list ...
    List() : head( NULL ), tail( NULL ), size( 0 ) {}

    ~List() { clear() ; }

    List( const List& old ); // copy ctor ...
    List& operator = ( const List& old ); // overloaded =

    void push_back( int val );
    void push_front( int val );
 
    bool erase( int val ); // erase FIRST node with this val (if it exists in list)

    void print() const ;

    void clear();

    int get_size() const { return size; }

private:

    struct Node
    {
        int val;
        Node* next;

        // default ...and value passed in ...ctor(s)... (this code handles both)
        // Note initialization list and how default values are handled here...
        Node( int vl = 0 ) : val( vl ), next( NULL ) {}

        void print() const
        {
            std::cout << val;
        }
    } ;

    Node* head;
    Node* tail;
    int size;
} ;




List::List( const List& old )
{
    head = tail = NULL;
    size = 0;
    Node* cur = old.head;
    while( cur ) {  push_back( cur->val ); cur = cur->next; }
}

List& List::operator = ( const List& old )
{
    if( this != &old )
    {
        clear();
        //head = tail = NULL;
        //size = 0;
        Node* cur = old.head;
        while( cur ) {  push_back( cur->val ); cur = cur->next; }
    }
    return *this;
}

void List::push_back( int val )
{
    Node* newNode = new Node( val );

    if( size ) // then newNode not first node
    {
        tail->next = newNode;
        tail = newNode;
    }
    else head = tail = newNode;

    ++ size;
}
void List::push_front( int val )
{
    Node* newNode = new Node( val );
    newNode->next = head;
    head = newNode; // can now update head ...

    if( ++size == 1 ) tail = newNode;
}

bool List::erase( int val ) // erase FIRST node with this val (if it exists in list)
{
    Node* cur = head; // get copy
    Node* prev = NULL;

    while( cur )
    {
        if( cur->val == val ) break;
        prev = cur;
        cur = cur->next;
    }

    // test end conditions ...

    if( cur ) // was found
    {
        if( prev ) // was not first node, so prev and cur exist
            prev->next = cur->next; // skip over cur ...

        else // was first node
            head = head->next;

        if( cur == tail ) tail = prev;

        delete cur;

        -- size;
        return true; // was erased ...
    }
    // else cout << "\nNot found ...\n";
    return false;
}

void List::print() const
{
    if( !head )
    {
        std::cout << "\nThe list is empty ... so can't print anything ...\n";
        return;
    }

    Node* cur = head;
    while( cur )
    {
        cur->print();
        std::cout << " ";

        cur = cur->next;
    }
    std::cout << std::endl;
}

void List::clear()
{
    Node* cur;
    while( head )
    {
        cur = head;
        head = head->next; // head set to NULL at end of loop //
        delete cur;
    }
    tail = NULL;
    size = 0;
}


#endif


--- End code ---

Navigation

[0] Message Index

[#] Next page