6 Fast Steps to a C++ template class List

[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: [Select]

// 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();
}


[David]

Step 2 ... 


Please see comments at top of code ...

Code: [Select]

// 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();

}


[David]

Step 3 ...


Please see comments at top of code ...

Code: [Select]

// 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();

}


[David]

Step 4 ...


Please see comments at top of code ...

Code: [Select]

// 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();

}


[David]

Step 5 ... (2 files)


Please see comments at top of code ...


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

Code: [Select]

// 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();
}


Now the .h file ...

Code: [Select]

// 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



[David]

And here is step 6 ...

the template class List (with iterators) ...

Firstly the test program and then the .h file ...
(but see next page, at bottom, for this demo using the, there, added const_iterator)

Code: [Select]

// List_step6.cpp //  // 2013-05-08 //

// Here we have upgraded our (int) class List to NOW be a template class
// so that it can NOW handle any type of data (NOT just int data)

// We have also added a nested iterator class so that we can traverse the list
// and access the elements in the list ... i.e. the data in any Node in the list
// i.e can read the (const) data ... or change (update) the data in a node

// Note: the data could be another data struct or class

// Also note, that HERE we have NOW moved our 'io' print functions
// to NOW be defined *outside* our class ...
// See the overloaded << operator in the template function def'n right below ...
// that uses the iterators (added here) ...
// for the class to traverse AND to access the elements in the class
// Note that the iterators behave also as a 'wrapper class' that 'wrap' a Node
// to permit access to a Node and the data in a Node ...
// as facilitating traversing the elements in the List ...
// (from the head element ... to the tail element)

#include  "template_class_List_SLL.h"

#include <iostream>
#include <fstream> // re. ostream

using namespace std;

template < typename T >
ostream& operator << ( ostream& os, List < T > & lst )
{
    typename List < T > ::iterator it;
    for( it = lst.begin(); it != lst.end(); ++ it )
         os << *it << ", ";
   
    return os << "size now is " << lst.size() << endl;
}



int main()
{
    List < int > myLst;

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

    cout << "Showing myLst ...\n" << myLst;

    List < int > myLst2 = myLst;

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

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

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

    cout << "\nShowing myLst2 ...\n"  << myLst2;

    cout << "\nShowing myLst2 ...\n";


    List< int >::iterator it;
    for( it = myLst2.begin(); it != myLst2.end(); ++ it )
         cout << *it << endl;


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

And the .h file ...

Code: [Select]

// template_class_List_SLL.h //  // 2013-05-08 //


#ifndef TEMPLATE_CLASS_LIST_SLL_H
#define TEMPLATE_CLASS_LIST_SLL_H

template < typename T >
class List
{
// this section is private by default (for a class)
// we are putting this private Node definition at the top so that it is 'known'
// inside our 'nested' interator class that follows here ...
    struct Node
    {
        T 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( const T& value = 0 ) : val( value ), next( 0 ) {}
    } ;

    Node* head;
    Node* tail;
    int len;

public:

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

    ~List() { clear() ; }

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

    void push_back( const T& val );
    void push_front( const T& val );

    // erase FIRST node with this val (if it exists in list)
    bool erase( const T& val );

    void clear();

    int size() const { return len; }

    class iterator
    {
        friend class List< T >; // to give class List access to private ptr
    public:
        iterator& operator ++ () { ptr = ptr->next; return *this; }
        iterator& operator ++ ( int ) { ptr = ptr->next; return *this; }
        bool operator != (const iterator& ) const;
        T operator * () const;
        T& operator * ();
    private:
        Node* ptr;
    };

    iterator begin();
    iterator end();

} ;

template < typename T >
List< T >::List( const List& old )
{
    head = tail = 0;
    len = 0;
    Node* cur = old.head;
    while( cur ) {  push_back( cur->val ); cur = cur->next; }

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

template < typename T >
void List< T >::push_back( const T& val )
{
    Node* newNode = new Node( val );

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

    ++ len;
}

template < typename T >
void List< T >::push_front( const T& val )
{
    Node* newNode = new Node( val );
    newNode->next = head;
    head = newNode; // can now update head ...

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

// erase FIRST node with this val (if it exists in list)
template < typename T >
bool List< T >::erase( const T& val )
{
    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;

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

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

// Compares two iterators and returns true or false depending on whether
// or not ...  they are referencing the same Node.
template < typename T >
bool List< T >::iterator::operator != (
    const typename List< T >::iterator& it ) const
{
return  ptr != it.ptr;
}

// Returns the value of the Node that the iterator is referencing.
template < typename T >
T List< T >::iterator::operator * () const
{
    return ptr->val;
}
// Permits assigning a Node a new value, via an iterator.
template < typename T >
T& List< T >::iterator::operator * ()
{
    return ptr->val;
}

template < typename T >
typename List< T >::iterator List< T >::begin()
{
    typename List< T >::iterator it;
    it.ptr = head;
    return it;
}

template < typename T >
typename List< T >::iterator List< T >::end()
{
    typename List< T >::iterator it;
    it.ptr = 0;
    return it;
}

#endif



[David]

You also might like to see these related links ...

Lists, template class List, single & double link, insert sort, merge sort, iters 

http://developers-heaven.net/forum/index.php?topic=310.0


Clist Insertion Sort Tutorial ... and also see a recursive merge sort of a list

http://developers-heaven.net/forum/index.php?topic=2440.0


Ok ... now, below, with const_iterator ...

Code: [Select]

// template_class_List_SLL.h //  // 2018-03-23 //


#ifndef TEMPLATE_CLASS_LIST_SLL_H
#define TEMPLATE_CLASS_LIST_SLL_H

template < typename T >
class List
{
// this section is private by default (for a class)
// we are putting this private Node definition at the top so that it is 'known'
// inside our 'nested' interator class that follows here ...
    struct Node
    {
        T 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( const T& value, Node* next = 0 ) : val( value ), next( next ) {}
    } ;

    Node* head;
    Node* tail;
    int len;

public:

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

    ~List() { clear() ; }

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

    void push_back( const T& val );
    void push_front( const T& val );

    // erase FIRST node with this val (if it exists in list)
    bool erase( const T& val );

    void clear();

    int size() const { return len; }

    class iterator
    {
        friend class List< T >; // to give class List access to private ptr
    public:
        iterator& operator ++ () { ptr = ptr->next; return *this; }
       
        bool operator != ( const iterator& ) const;
        T operator * () const;
        T& operator * ();
    private:
        Node* ptr;
    };

    iterator begin();
    iterator end();

} ;

template < typename T >
List< T >::List( const List& old )
{
    head = tail = 0;
    len = 0;
    Node* cur = old.head;
    while( cur ) {  push_back( cur->val ); cur = cur->next; }

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

template < typename T >
void List< T >::push_back( const T& val )
{
    if( len ) // then newNode not first node
    {
        tail->next = new Node( val );
        tail = tail->next;
    }
    else head = tail = new Node( val );

    ++ len;
}

template < typename T >
void List< T >::push_front( const T& val )
{
    head = new Node( val, head );

    if( ++len == 1 ) tail = head;
}

// erase FIRST node with this val (if it exists in list)
template < typename T >
bool List< T >::erase( const T& val )
{
    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;

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

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

// Compares two iterators and returns true or false depending on whether
// or not ...  they are referencing the same Node.
template < typename T >
bool List< T >::iterator::operator != (
    const typename List< T >::iterator& it ) const
{
return  ptr != it.ptr;
}

// Returns the value of the Node that the iterator is referencing.
template < typename T >
T List< T >::iterator::operator * () const
{
    return ptr->val;
}
// Permits assigning a Node a new value, via an iterator.
template < typename T >
T& List< T >::iterator::operator * ()
{
    return ptr->val;
}

template < typename T >
typename List< T >::iterator List< T >::begin()
{
    typename List< T >::iterator it;
    it.ptr = head;
    return it;
}

template < typename T >
typename List< T >::iterator List< T >::end()
{
    typename List< T >::iterator it;
    it.ptr = 0;
    return it;
}

#endif

And now the test program that uses the const_iterator

Code: [Select]

// List_step6.cpp //  // 2018-03-23 //

// Here we have upgraded our (int) class List to NOW be a template class
// so that it can NOW handle any type of data (NOT just int data)

// We have also added a nested iterator class so that we can traverse the list
// and access the elements in the list ... i.e. the data in any Node in the list
// i.e can read the (const) data ... or change (update) the data in a node

// Note: the data could be another data struct or class

// Also note, that HERE we have NOW moved our 'io' print functions
// to NOW be defined *outside* our class ...
// See the overloaded << operator in the template function def'n right below ...
// for the class to traverse AND to access the elements in the class
// Note that the iterators behave also as a 'wrapper class' that 'wrap' a Node
// to permit access to a Node and the data in a Node ...
// as facilitating traversing the elements in the List ...
// (from the head element ... to the tail element)

// that uses the iterators (added here) ...
#include  "template_class_List_SLL.h"

#include <iostream>

using namespace std;

template < typename T >
ostream& operator << ( ostream& os, List < T > & lst )
{
    typename List < T > ::iterator it;
    for( it = lst.begin(); it != lst.end(); ++ it )
         os << *it << ", ";
   
    return os << "size now is " << lst.size() << endl;
}



int main()
{
    List < int > myLst;

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

    cout << "Showing myLst ...\n" << myLst;

    List < int > myLst2 = myLst;

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

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

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

    cout << "\nShowing myLst2 ...\n"  << myLst2;

    cout << "\nShowing myLst2 ...\n";


    List< int >::iterator it;
    for( it = myLst2.begin(); it != myLst2.end(); ++ it )
         cout << *it << endl;


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

[David]

This next series is mostly to demo inserting in sorted order in a DOUBLE LINK linked list ...

1. just using struct

2. using a class

3. using a template class


So firstly ... just using a struct

Code: [Select]

// insertSortedDLLofString.cpp //

#include <iostream>
#include <string>


using namespace std;

struct Node
{
    string str;
    Node* prev;
    Node* next;
   
    Node( const string& str = "" ) : str(str), prev(0), next(0) {}
} ;


struct List
{
    Node* head;
    Node* tail;
    int size;
   
    List() : head(0), tail(0), size(0) {}
   
    ~List() { clear(); }
    void clear()
    {
        while( head )
        {
            Node* del = head;
            head = head->next;
            delete del;
        }
        tail = 0;
        size = 0;
    }

    void push_front( const string& str )
    {
        Node* nNode = new Node( str );
       
        if( size )
        {
            nNode->next = head; // N->A
            head->prev = nNode; // N<-A
            head = nNode;
        }
        else tail = head = nNode;
        ++size;
    }
   

    void push_back( const string& str )
    {
        Node* nNode = new Node( str );

        if( size )
        {
            tail->next = nNode; // B->N
            nNode->prev = tail; // B<-N
            tail = nNode;
        }
        else tail = head = nNode;
        ++size;
    }
   
    void insert_sorted( const string& str)
    {
        Node* nNode = new Node( str );
       
        // case 1 ... NOT inserted as the head node
        if( head  &&  head->str <= str )
        {
            // find Node to insert after
            Node* prev = head;
            Node* cur = head->next;
            while( cur && cur->str <= str )
            {
                prev = cur;
                cur = cur->next;
            }
            // ok found spot ... insert after 'prev'
           
            prev->next = nNode;
            nNode->prev = prev;
           
            if( cur ) // NOT at tail
            {
                cur->prev = nNode;
                nNode->next = cur;
            }
            else // at tail
            {
                tail = nNode;
            }
        }
        else // insert at head ...
        {
            if( size )
            {
                nNode->next = head;
                head->prev = nNode;
                head = nNode;
            }
            else tail = head = nNode;
        }
       
        ++ size;
    }
   
    void print() const
    {
        Node* cur = head;
        while( cur )
        {
            cout << cur->str << ' ';
            cur = cur->next;
        }
    }

    void printReversed() const
    {
        Node* cur = tail;
        while( cur )
        {
            cout << cur->str << ' ';
            cur = cur->prev;
        }
    }
} ;






int main()
{
    List myLst;

    cout << "Now testing push_front:\n";
    myLst.push_front( "Sam" );
    myLst.push_front( "Joe" );
    myLst.push_front( "Anne" );
   
    myLst.print();
   
    cout << "\nPrinting reversed:\n";
    myLst.printReversed();
   
    myLst.clear();
   
   
    cout << "\n\nNow testing push_back:\n";

    myLst.push_back( "Sam" );
    myLst.push_back( "Joe" );
    myLst.push_back( "Anne" );

    myLst.print();

    cout << "\nPrinting reversed:\n";
    myLst.printReversed();

    myLst.clear();
   

    cout << "\n\nNow testing insert_sorted:\n";
    myLst.insert_sorted( "Billy" );
    myLst.insert_sorted( "Sam" );
    myLst.insert_sorted( "Joe" );
    myLst.insert_sorted( "Anne" );
    myLst.insert_sorted( "Jill" );

    myLst.print();

    cout << "\nPrinting reversed:\n";
    myLst.printReversed();
   
    cout << "\n\nPress 'Enter' to continue/exit ..." << flush;
    cin.get();
}


[David]

Now using a class (instead of a struct) ...

Code: [Select]

// insertSortedDLLofString2.cpp //

#include <iostream>
#include <string>


using namespace std;



class List
{
public:
    List() : head(0), tail(0), size(0) {}
   
    ~List() { clear(); }
    void clear()
    {
        while( head )
        {
            Node* del = head;
            head = head->next;
            delete del;
        }
        tail = 0;
        size = 0;
    }

    void push_front( const string& str )
    {
        Node* nNode = new Node( str );
       
        if( size )
        {
            nNode->next = head; // N->A
            head->prev = nNode; // N<-A
            head = nNode;
        }
        else tail = head = nNode;
        ++size;
    }
   

    void push_back( const string& str )
    {
        Node* nNode = new Node( str );

        if( size )
        {
            tail->next = nNode; // B->N
            nNode->prev = tail; // B<-N
            tail = nNode;
        }
        else tail = head = nNode;
        ++size;
    }
   
    void insert_sorted( const string& str)
    {
        Node* nNode = new Node( str );
       
        // case 1 ... NOT inserted as the head node
        if( head  &&  head->str <= str )
        {
            // find Node to insert after
            Node* prev = head;
            Node* cur = head->next;
            while( cur && cur->str <= str )
            {
                prev = cur;
                cur = cur->next;
            }
            // ok found spot ... insert after 'prev'
           
            prev->next = nNode;
            nNode->prev = prev;
           
            if( cur ) // NOT at tail
            {
                cur->prev = nNode;
                nNode->next = cur;
            }
            else // at tail
            {
                tail = nNode;
            }
        }
        else // insert at head ...
        {
            if( size )
            {
                nNode->next = head;
                head->prev = nNode;
                head = nNode;
            }
            else tail = head = nNode;
        }
       
        ++ size;
    }
   
    void print() const
    {
        Node* cur = head;
        while( cur )
        {
            cout << cur->str << ' ';
            cur = cur->next;
        }
    }

    void printReversed() const
    {
        Node* cur = tail;
        while( cur )
        {
            cout << cur->str << ' ';
            cur = cur->prev;
        }
    }
   
private:
   struct Node
    {
        string str;
        Node* prev;
        Node* next;

        Node( const string& str = "" ) : str(str), prev(0), next(0) {}
    } ;

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






int main()
{
    List myLst;

    cout << "Now testing push_front:\n";
    myLst.push_front( "Sam" );
    myLst.push_front( "Joe" );
    myLst.push_front( "Anne" );
   
    myLst.print();
   
    cout << "\nPrinting reversed:\n";
    myLst.printReversed();
   
    myLst.clear();
   
   
    cout << "\n\nNow testing push_back:\n";

    myLst.push_back( "Sam" );
    myLst.push_back( "Joe" );
    myLst.push_back( "Anne" );

    myLst.print();

    cout << "\nPrinting reversed:\n";
    myLst.printReversed();

    myLst.clear();
   

    cout << "\n\nNow testing insert_sorted:\n";
    myLst.insert_sorted( "Billy" );
    myLst.insert_sorted( "Sam" );
    myLst.insert_sorted( "Joe" );
    myLst.insert_sorted( "Anne" );
    myLst.insert_sorted( "Jill" );

    myLst.print();

    cout << "\nPrinting reversed:\n";
    myLst.printReversed();
   
    cout << "\n\nPress 'Enter' to continue/exit ..." << flush;
    cin.get();
}


[David]

And finally ... using a template class ...

Code: [Select]

// insertSortedDLL.cpp //  // 2016-02-12 //
 
// Note: still need to code copy ctor... and overloaded operator =
// But these are not needed in the short 'test code' used in 'main' below. //

#include <iostream>
#include <string>


using namespace std;


template< typename T >
class List
{
public:
    List() : head(0), tail(0), len(0) {}
   
    ~List() { clear(); }
    void clear()
    {
        while( head )
        {
            Node* del = head;
            head = head->next;
            delete del;
        }
        tail = 0;
        len = 0;
    }

    void push_front( const T& val )
    {
        Node* nNode = new Node( val );
       
        if( len )
        {
            nNode->next = head; // N->A
            head->prev = nNode; // N<-A
            head = nNode;
        }
        else tail = head = nNode;
        ++len;
    }
    void push_back( const T& val )
    {
        Node* nNode = new Node( val );

        if( len )
        {
            tail->next = nNode; // B->N
            nNode->prev = tail; // B<-N
            tail = nNode;
        }
        else tail = head = nNode;
        ++len;
    }
   
    void insert_sorted( const T& val)
    {
        Node* nNode = new Node( val );
       
        // case 1 ... NOT inserted as the head node
        if( head  &&  head->val <= val )
        {
            // find Node to insert after
            Node* prev = head;
            Node* cur = head->next;
            while( cur && cur->val <= val )
            {
                prev = cur;
                cur = cur->next;
            }
            // ok found spot ... insert after 'prev'
           
            prev->next = nNode;
            nNode->prev = prev;
           
            if( cur ) // NOT at tail
            {
                cur->prev = nNode;
                nNode->next = cur;
            }
            else // at tail
            {
                tail = nNode;
            }
        }
        else // insert at head ...
        {
            if( len )
            {
                nNode->next = head;
                head->prev = nNode;
                head = nNode;
            }
            else tail = head = nNode;
        }
       
        ++ len;
    }
   
    void print( ostream& os = cout ) const
    {
        Node* cur = head;
        while( cur )
        {
            os << cur->val << ' ';
            cur = cur->next;
        }
    }

    void print_reversed() const
    {
        Node* cur = tail;
        while( cur )
        {
            cout << cur->val << ' ';
            cur = cur->prev;
        }
    }
   
    size_t size() const { return len; }
   
private:
   struct Node
    {
        T val;
        Node* prev;
        Node* next;

        Node( const T& val = T() ) : val(val), prev(0), next(0) {}
    } ;

    Node* head;
    Node* tail;
    size_t len;
} ;






int main()
{
    List< string > my_lst;

    cout << "Now testing push_front:\n";
    my_lst.push_front( "Sam" );
    my_lst.push_front( "Joe" );
    my_lst.push_front( "Anne" );
   
    my_lst.print();
   
    cout << "\nPrinting reversed:\n";
    my_lst.print_reversed();
   
    my_lst.clear();
   
   
    cout << "\n\nNow testing push_back:\n";
    my_lst.push_back( "Sam" );
    my_lst.push_back( "Joe" );
    my_lst.push_back( "Anne" );

    my_lst.print();

    cout << "\nPrinting reversed:\n";
    my_lst.print_reversed();

    my_lst.clear();
   

    cout << "\n\nNow testing insert_sorted:\n";
    my_lst.insert_sorted( "Billy" );
    my_lst.insert_sorted( "Sam" );
    my_lst.insert_sorted( "Joe" );
    my_lst.insert_sorted( "Anne" );
    my_lst.insert_sorted( "Jill" );

    my_lst.print();

    cout << "\nPrinting reversed:\n";
    my_lst.print_reversed();

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

[David]

And here is a fairly complete Single Link Linked-List that you might like to try ...


Firstly a little test program ... (then followed by the .h file.)

Code: [Select]

// test_List_SLL.cpp //  // 2018-02-12 //

// Here we have upgraded our (int) class List to NOW be a template class
// so that it can NOW handle any type of data (NOT just int data)

// We have also added a nested iterator class so that we can traverse the list
// and access the elements in the list ... i.e. the data in any Node in the list
// i.e can read the (const) data ... or change (update) the data in a node

// Note: the data could be another data struct or class

// Also note, that HERE we have NOW moved our 'io' print functions
// to NOW be defined outside our class ...
// See the overloaded << operator in the template function def'n right below ...
// that uses the iterators (added here) ...
// for the class to traverse AND to access the elements in the class
// Note that the iterators behave also as a 'wrapper class' that 'wrap' a Node
// to permit access to a Node and the data in a Node ...
// as facilitating traversing the elements in the List ...
// (from the head element ... to the tail element)


[code]#include  "List_SLL.h"

#include <iostream>
#include <fstream> // re. ostream


template < typename T >
std::ostream& operator << ( std::ostream& os, const List < T > & lst )
{
    typename List < T >::const_iterator it;
    for( it = lst.begin(); it != lst.end(); ++ it )
        os << *it << ", ";

    return os << "size now is " << lst.size() << std::endl;
}



int main()
{
    using std::cout;
    using std::cin;
   
    List < int > myLst;

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

    cout << "Showing myLst ...\n" << myLst;

    List < int > myLst2 = myLst; // test copy ctor //

    cout << "\ndeleting 50 ... \n";
    if( !myLst.erase( 50 ) ) cout << "50 was NOT found ... ";
    cout << "Showing myLst ...\n"  << myLst;

    cout << "\ndeleting 40 ... \n";
    List< int >::iterator it;
    if( (it = myLst.find( 40 )) != myLst.end() )
        myLst.erase( it );
    else cout << "40 was NOT found ... ";
    cout << "Showing myLst ...\n"  << myLst;

    cout << "\ndeleting 20 ... \n";
    if( (it = myLst.find( 20 )) != myLst.end() )
        myLst.erase( it );
    else cout << "20 was NOT found ... ";
    cout << "Showing myLst ...\n"  << myLst;

    cout << "\ndeleting 10 ... \n";
    if( (it = myLst.find( 10 )) != myLst.end() )
        myLst.erase( it );
    else cout << "10 was NOT found ... ";
    cout << "Showing myLst ...\n"  << myLst;

    cout << "\ndeleting 30 ... \n";
    if( (it = myLst.find( 30 )) != myLst.end() )
        myLst.erase( it );
    else cout << "30 was NOT found ... ";
    cout << "Showing myLst ...\n"  << myLst;

    cout << "\ndeleting 30 ... \n";
    if( (it = myLst.find( 30 )) != myLst.end() )
        myLst.erase( it );
    else cout << "30 was NOT found ... ";
    cout << "Showing myLst ...\n"  << myLst;

    myLst.push_back( 30 );

    cout << "\nAfter push_back(30) and clear list ... \n";
    myLst.clear();
    cout << "Showing myLst ...\n"  << myLst;

    myLst.push_front( 30 );

    cout << "\nAfter push_front(30) and clear list ... \n";
    myLst.clear();
    cout << "Showing myLst ...\n"  << myLst;

    cout << "\nShowing myLst2 ...\n"  << myLst2;

    cout << "\nShowing myLst2 ...\n";
    for( it = myLst2.begin(); it != myLst2.end(); ++ it )
        cout << *it << ' ';


    cout << "\n\nTesting push_front, pop_front, etc... \n";
    myLst.push_front( 10 );
    myLst.push_front( 20 );
    myLst.push_front( 30 );
    myLst.push_front( 40 );

    // testing front and pop_front ...
    while( !myLst.empty() )
    {
        cout << myLst.front() << ' ';
        myLst.pop_front();
    }

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


[David]

And now the .h file ...

Code: [Select]

// List_SLL.h //  // 2018-02-12 //


#ifndef LIST_SLL_H
#define LIST_SLL_H


#include <iostream> // re. size_t //


template < typename T >
class List
{
    // This section is private by default (for a class)
    // we are putting this private Node definition at the top so that it is 'known'
    // inside our 'nested' interator class that follows here ...
    struct Node
    {
        T 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( const T& value = 0 ) : val( value ), next( 0 ) {}
    } ;

    Node* head;
    Node* tail;
    size_t len;

public:

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

    ~List() { clear() ; }

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

    void push_back( const T& val );
    void push_front( const T& val );

    // erase FIRST node with this val (if it exists in list)
    bool erase( const T& val );

    void clear();

    size_t size() const { return len; }

    class iterator
    {
        Node* ptr;
        friend class List< T >; // to give class List access to private ptr
    public:
        iterator& operator ++ () { ptr = ptr->next; return *this; }
        iterator& operator ++ ( int ) { ptr = ptr->next; return *this; }
        bool operator != ( const iterator& ) const;
        const T& operator * () const;
        T& operator * ();
    } ;

    iterator begin();
    iterator end();
   
   
    typedef iterator const_iterator;
   
    const_iterator begin() const;
    const_iterator end() const;
   
    iterator find( const T& val );
    bool erase( iterator it );
   
   
    // These added so can use List as a stack using push_front, pop_front and empty //
   
    T front() const { return head->val; }
    T back() const { return tail->val; }
   
    void pop_front()
    {
        if( len )
        {
            Node* tmp = head;
            head = head->next;
            delete tmp;
            -- len;
            if( len <= 1 ) tail = head;
        }
    }
   
    bool empty() const { return len == 0; }
} ;

template < typename T >
List< T >::List( const List& old )
{
    head = tail = 0;
    len = 0;
    for( Node* cur = old.head; cur; cur = cur->next )
        push_back( cur->val );
}
template < typename T >
List< T >& List< T >::operator = ( const List& old )
{
    if( this != &old )
    {
        clear(); // also does // head = tail = 0; len = 0; //
        for( Node* cur = old.head; cur; cur = cur->next )
            push_back( cur->val );
    }
    return *this;
}

template < typename T >
void List< T >::push_back( const T& val )
{
    Node* newNode = new Node( val );
   
    if( len ) // then newNode not first node
        tail->next = newNode;
    else
        head = newNode;
    tail = newNode;
    ++ len;
}

template < typename T >
void List< T >::push_front( const T& val )
{
    Node* newNode = new Node( val );
   
    newNode->next = head;
    head = newNode; // can now update head ...

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

// erase FIRST node with this val (if it exists in list)
template < typename T >
bool List< T >::erase( const T& val )
{
    Node* prev = 0;
    Node* cur = head; // get copy
    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;

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

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

// Compares two iterators and returns true or false depending on whether
// or not ...  they are referencing the same Node.
template < typename T >
bool List< T >::iterator::operator != (
    const typename List< T >::iterator& it ) const
{
return  ptr != it.ptr;
}

// Returns the value of the Node that the iterator is referencing.
template < typename T >
const T& List< T >::iterator::operator * () const
{
    return ptr->val;
}
// Permits assigning a Node a new value, via an iterator.
template < typename T >
T& List< T >::iterator::operator * ()
{
    return ptr->val;
}

template < typename T >
typename List< T >::iterator List< T >::begin()
{
    List< T >::iterator it;
    it.ptr = head;
    return it;
}

template < typename T >
typename List< T >::iterator List< T >::end()
{
    List< T >::iterator it;
    it.ptr = 0;
    return it;
}


template < typename T >
typename List< T >::const_iterator List< T >::begin() const
{
    List< T >::const_iterator it;
    it.ptr = head;
    return it;
}

template < typename T >
typename List< T >::const_iterator List< T >::end() const
{
    List< T >::const_iterator it;
    it.ptr = 0;
    return it;
}

template < typename T >
typename List< T >::iterator List< T >::find( const T& val )
{
    List< T >::iterator it;
    for( it.ptr = head; it.ptr; it.ptr = it.ptr->next )
    {
        if( *it == val ) return it;
    }
    return end();
}

template < typename T >
bool List< T >::erase( iterator it )
{
    Node* prev = 0;
    Node* cur = head;
    for( ; cur && cur != it.ptr; cur = cur->next )
    {
        prev = cur;
    }
    // check end conditions //
    if( cur ) // found //
    {
        if( prev )
            prev->next = cur->next;
        else
            head = head->next;

        if( cur == tail ) tail = prev;

        delete cur;
        -- len;
        return true;
    }
    // NOT found //
    return false;
}

#endif