Lists ... examples of steps to a SLL (Single-Link Linked List) and a DLL ...

[David]

For students wanting to learn about several commonly used data container structures, and data handling algorithms, such as a linear search of the container to see if an element is there or not, and other methods such as erase, sort, etc...

the following pages may be, for you,

JUST what the Dr. has ordered

to help get you beyond the long start-up learning curve, for the linked-list type data structure, both single-linked and double-linked ...

Please see the following demo code progressions, beginning with a quite bare SLL ... and progressing to a fairly full featured DLL.

Update: 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

You may also like to see 6 Fast Steps to a C++ template class List ...
http://developers-heaven.net/forum/index.php/topic,2606.0.html


What follows, is a bare-bones list with an insert sorted method ...

Code: [Select]

// bareBonesListInsetSorted.cpp //  // 2017-02-11 //

#include <iostream>
#include <string>

using std::ostream;
using std::string;


template < typename T >
struct Node
{
    T data;
    Node* next;
   
    // ctors...
    Node( const T& data= T(), Node* next = 0 ) : data(data), next(next) {}

    // def'n for overloaded << for Node< T > objects ,,,
    friend ostream& operator << ( ostream& os, const Node* nd )
    {
        return os << nd->data;
    }
} ;


template< typename T >
struct List
{
    Node< T >* head;
   
    // default ctor...
    List() : head(0) {}
    // dtor...
    ~List() { clear(); }
   
    void clear()
    {
        Node< T >* del;
        while( head )
        {
            del = head;
            head = head->next;
            delete del;
        }
        // Note that head is set to 0 when done //
    }
   
    /*
    void push_front( const T& data )
    {
        // Note that this also sets the next to 'head' //
        Node< T >* newNode = new Node< T >( data, head );
        head = newNode; // update the head pointer //
    }
    */
   
    // insert sorted by <= def'n of objects ...
    void insert( const T& data )
    {
        Node< T >* nNode = new Node< T > (data); // recall next set to 0 //
       
        // case 1 : NOT inserted as the head node
        if( head != 0  &&  head->data <= data )
        {
            // find Node to insert after
            Node< T >* prev = head;
            Node< T >* cur = head->next;
            while( cur != 0 && cur->data <= data )
            {
                prev = cur;
                cur = cur->next;
            }
            // ok found spot ... insert after 'prev'

            prev->next = nNode;

            //if( cur ) // NOT at end
            nNode->next = cur; // link next to 'next' //
        }
        else // case 2 : insert at head ...
        {
            nNode->next = head;
            head = nNode; // update head //
        }
    }
   
   
    // def'n of overloaded << for List objects ...
    friend ostream& operator << ( ostream& os, const List< T >& lst )
    {
        for( Node< T >* cur = lst.head; cur != 0; cur = cur->next )
        {
            os << cur << '\n'; //uses overloaded << for Node above //
        }
        return os;
    }
} ;


struct Student
{
    string name;
    int id;
   
    // ctors...
    Student( string name = "", int id = 0 ) : name(name), id(id) {}
   
    // for insert sorted method ...
    bool operator <= ( const Student& st ) const
    {
        return id <= st.id;
    }
   
    friend ostream& operator << ( ostream& os, const Student& st )
    {
        return os << st.name << ' ' << st.id;
    }
} ;






int main()
{
    using std::cout;
    using std::cin;
   
    List< Student > studs;
   
    studs.insert( Student("Sam", 3) );
    studs.insert( Student("James", 1) );
    studs.insert( Student("Annie", 4) );
    studs.insert( Student("Jill", 2) );
   
   
    cout << "studs now are: \n" << studs;
   
   
    cout << "\nPress 'Enter' to continue/exit ... ";
    cin.get();
}

Same as above ... but class version ...

Code: [Select]

// bareBonesListInsetSorted_classVersion.cpp //  // 2017-02-11 //

#include <iostream>
#include <string>

using std::ostream;
using std::string;

template < typename T > class List; // forward declaration //

template < typename T >
class Node
{
public:
    // ctors...
    Node( const T& data= T(), Node* next = 0 ) : data(data), next(next) {}

private:
    T data;
    Node* next;
   
    // def'n for overloaded << for Node< T > objects ,,,
    friend ostream& operator << ( ostream& os, const Node* nd )
    {
        return os << nd->data;
    }
    friend class List < T >;
} ;



template< typename T >
class List
{
public:
    // default ctor...
    List() : head(0) {}
    // dtor...
    ~List() { clear(); }
   
    void clear()
    {
        while( head )
        {
            Node< T >* del = head;
            head = head->next;
            delete del;
        }
        // Note that head is set to 0 when done //
    }
   
    void push_front( const T& data )
    {
        // Note that this alos sets the next to 'head' //
        Node< T >* newNode = new Node< T >( data, head );
        head = newNode; // update the head pointer //
    }
   
    // insert sorted by <= def'n of objects ...
    void insert( const T& data )
    {
        Node< T >* nNode = new Node< T > (data); // recall next set to 0 //
       
        // case 1 : NOT inserted as the head node
        if( head != 0  &&  head->data <= nNode->data )
        {
            // find Node to insert after
            Node< T >* prev = head;
            Node< T >* cur = head->next;
            while( cur != 0 && cur->data <= nNode->data )
            {
                prev = cur;
                cur = cur->next;
            }
            // ok found spot ... insert after 'prev'

            prev->next = nNode;

            //if( cur ) // NOT at end
            nNode->next = cur; // link next to 'next' //
        }
        else // case 2 : insert at head ...
        {
            nNode->next = head;
            head = nNode; // update head //
        }
    }
    void print( ostream& os ) const
    {
        Node< T >* cur = head;
        for( ; cur != 0 ; cur = cur->next )
            os << cur << '\n'; //uses overloaded << for Node above //
    }
   
private:
    Node< T >* head;
   
} ;

// def'n of overloaded << for List objects ...
template < typename T >
ostream& operator << ( ostream& os, const List< T >& lst )
{
    lst.print( os );
    return os;
}



class Student
{
public:
    // ctors...
    Student( string name="", int id=0 ) : name(name), id(id) {}
   
    // for insert sorted method ...
    bool operator <= ( const Student& st ) const
    {
        return id <= st.id;
    }
   
private:
    string name;
    int id;
   
    friend ostream& operator << ( ostream& os, const Student& st )
    {
        return os << st.name << ' ' << st.id;
    }
} ;






int main()
{
    using std::cout;
    using std::cin;
   
    List< Student > studs;
   
    studs.insert( Student("Sam", 3) );
    studs.insert( Student("James", 1) );
    studs.insert( Student("Annie", 4) );
    studs.insert( Student("Jill", 2) );
   
   
    cout << "studs now are: \n" << studs;
   
   
    cout << "\nPress 'Enter' to continue/exit ... ";
    cin.get();
}

Same as above ... but with a nested Node class/struct ...

Code: [Select]

// bareBonesListInsetSorted_classVersion_nestedNode.cpp //  // 2017-02-11 //

#include <iostream>
#include <string>

using std::ostream;
using std::string;



template< typename T >
class List
{
public:
    // default ctor...
    List() : head(0) {}
    // dtor...
    ~List() { clear(); }
   
    void clear()
    {
        while( head )
        {
            Node* del = head;
            head = head->next;
            delete del;
        }
        // Note that head is set to 0 when done //
    }
   
    void push_front( const T& data )
    {
        // Note that this alos sets the next to 'head' //
        Node* newNode = new Node( data, head );
        head = newNode; // update the head pointer //
    }
   
    // insert sorted by <= def'n of objects ...
    void insert( const T& data )
    {
        Node* nNode = new Node( data ); // recall next set to 0 //
       
        // case 1 : NOT inserted as the head node
        if( head != 0  &&  head->data <= nNode->data )
        {
            // find Node to insert after
            Node* prev = head;
            Node* cur = head->next;
            while( cur != 0 && cur->data <= nNode->data )
            {
                prev = cur;
                cur = cur->next;
            }
            // ok found spot ... insert after 'prev'

            prev->next = nNode;

            //if( cur ) // NOT at end
            nNode->next = cur; // link next to 'next' //
        }
        else // case 2 : insert at head ...
        {
            nNode->next = head;
            head = nNode; // update head //
        }
    }
    void print( ostream& os ) const
    {
        Node* cur = head;
        for( ; cur != 0 ; cur = cur->next )
            os << cur->data << '\n';
    }
   
private:
    struct Node
    {
        Node( const T& data= T(), Node* next = 0 ) : data(data), next(next) {}

        T data;
        Node* next;
    } ;
   
    Node* head;
} ;

// def'n of overloaded << for List objects ...
template < typename T >
ostream& operator << ( ostream& os, const List< T >& lst )
{
    lst.print( os );
    return os;
}



class Student
{
public:
    // ctors...
    Student( string name="", int id=0 ) : name(name), id(id) {}
   
    // for insert sorted method ...
    bool operator <= ( const Student& st ) const
    {
        return id <= st.id;
    }
   
private:
    string name;
    int id;
   
    friend ostream& operator << ( ostream& os, const Student& st )
    {
        return os << st.name << ' ' << st.id;
    }
} ;






int main()
{
    using std::cout;
    using std::cin;
   
    List< Student > studs;
   
    studs.insert( Student("Sam", 3) );
    studs.insert( Student("James", 1) );
    studs.insert( Student("Annie", 4) );
    studs.insert( Student("Jill", 2) );
   
   
    cout << "studs now are: \n" << studs;
   
   
    cout << "\nPress 'Enter' to continue/exit ... ";
    cin.get();
}

[David]

Below, we edit up to add a tail and len data member ... also an erase method ...

and we will also, firstly, separate out into its own file, (with guards), the code for a SLL ...

Note, we have NOT added iterators yet, so we are keeping all with public access ...
thus the nested Node class/struct has public access to enable free access to nodes in the SLL ...

Code: [Select]

// insertSortedEraseSLL.h //  // 2017-02-11 //

// Note: still need to code copy ctor... and overloaded operator =
// But these are not needed in the short 'test code' used here. //


#ifndef _insertSortedEraseSLL_H_
#define _insertSortedEraseSLL_H_


template< typename T >
struct List
{
   struct Node
    {
        T val;
        Node* next;

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

    Node* head;
    Node* tail;
    size_t len;
   

    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 )
    {
        head = new Node( val, head );
        ++len;
    }
    void push_back( const T& val )
    {
        Node* nNode = new Node( val );
        if( len )
        {
            tail->next = nNode; // B->N
            tail = nNode;
        }
        else tail = head = nNode;
        ++len;
    }
   
    // insert sorted by <= def'n of objects ...
    void insert_sorted( const T& val )
    {
        Node* nNode = new Node( val ); // recall next set to 0 //

        // case 1 : NOT inserted as the head node
        if( head != 0  &&  head->val <= val )
        {
            // find Node to insert after
            Node* prev = head;
            Node* cur = head->next;
            while( cur != 0 && cur->val <= val )
            {
                prev = cur;
                cur = cur->next;
            }
            // ok found spot ... insert after 'prev'

            prev->next = nNode;

            //if( cur ) // NOT at end
            nNode->next = cur; // link next to 'next' //
            if( !cur ) tail = nNode;
        }
        else // case 2 : insert at head ...
        {
            nNode->next = head;
            head = nNode; // update head //
            if( !len ) tail = head;
        }
       
        ++ len;
    }
   
    // used by method insert_sort() that follows ...
    void insert_sorted( Node* nNode )
    {
        // case 1 : NOT inserted as the head node
        if( head != 0  &&  head->val <= nNode->val )
        {
            // find Node to insert after
            Node* prev = head;
            Node* cur = head->next;
            while( cur != 0 && cur->val <= nNode->val )
            {
                prev = cur;
                cur = cur->next;
            }
            // ok found spot ... insert after 'prev'

            prev->next = nNode;

            // if( cur ) // NOT at end
            nNode->next = cur; // link next to 'next' //
            if( !cur ) tail = nNode;
        }
        else // case 2 : insert at head ...
        {
            nNode->next = head;
            head = nNode; // update head //
            if( !len ) tail = head;
        }
       
        ++ len;
    }

    // calls above method insert_sorted( Node* nNode ) //
    void insert_sort()
    {
        if( len > 1 ) // then head and cur != 0 //
        {
            Node* cur = head; // get copy //
            Node* next = cur->next; // get copy //
            head = tail = 0;
            len = 0;
            for( ; ; )
            {
                insert_sorted( cur );
                cur = next; // UPDATE from COPY //
                if( !cur ) break;
                next = cur->next;
            }
        }
    }
   
    bool erase( Node* ptr )
    {
        Node* prev = 0;
        Node* cur = head;
        for( ; cur && cur != 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;
    }
   
    size_t size() const { return len; }
} ;

#endif

And now a short test program for the above ...

Code: [Select]

// insertSortedEraseSLL.cpp //  // 2017-02-13 //

#include <iostream>
#include <string>

// Note: still need to code copy ctor... and overloaded operator =
// But these are not needed in the short 'test code' used here. //
#include "insertSortedEraseSLL.h"


template< typename T >
void print(  const List< T >& lst, std::ostream& os = std::cout )
{
    typename List< T >::Node* cur;
    cur = lst.head;
    while( cur )
    {
        os << cur->val << ' ';
        cur = cur->next;
    }
    os << "size() = " << lst.size();
}


typedef List< std::string >::Node* MyNode;

MyNode find( List< std::string >& lst, const std::string& val )
{
    MyNode cur = lst.head;
    while( cur )
    {
        if( cur->val == val ) return cur;
        cur = cur->next;
    }
    return 0; // NOT found
}




int main()
{
    using namespace std;
   
    List< string > my_lst;

    cout << "Now testing push_front: ";
    my_lst.push_front( "Billy" );
    my_lst.push_front( "Sam" );
    my_lst.push_front( "Joe" );
    my_lst.push_front( "Anne" );
    my_lst.push_front( "Jill" );
   
    print( my_lst );
   
    my_lst.insert_sort();
    cout << "\nAfter calling my_lst.insert_sort(): ";
    print( my_lst );
    my_lst.clear();
   
    cout << "\n\nNow testing push_back: ";
    my_lst.push_back( "Billy" );
    my_lst.push_back( "Sam" );
    my_lst.push_back( "Joe" );
    my_lst.push_back( "Anne" );
    my_lst.push_back( "Jill" );

    print( my_lst );
   
    my_lst.insert_sort();
    cout << "\nAfter calling my_lst.insert_sort(): ";
    print( my_lst );
    my_lst.clear();
   

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

    cout << "\n\nFind Billy ... ";
    MyNode cur = find( my_lst, "Billy" );
    if( cur )
    {
        cout << "Found ... erasing Billy ...\n";
        my_lst.erase( cur );
    }
    else cout << "NOT Found ... NOT erasing Billy ...\n";

    print( my_lst );
   
   
    cout << "\n\nFind Anne ... ";
    cur = find( my_lst, "Anne" );
    if( cur )
    {
        cout << "Found ... erasing Anne ...\n";
        my_lst.erase( cur );
    }
    else cout << "NOT Found ... NOT erasing Anne ...\n";
    print( my_lst );
   
   
    cout << "\n\nFind Sam ... ";
    cur = find( my_lst, "Sam" );
    if( cur )
    {
        cout << "Found ... erasing Sam ...\n";
        my_lst.erase( cur );
    }
    else cout << "NOT Found ... NOT erasing Sam ...\n";
    print( my_lst );
   
   
    cout << "\n\nFind Jill ... ";
    cur = find( my_lst, "Jill" );
    if( cur )
    {
        cout << "Found ... erasing Jill ...\n";
        my_lst.erase( cur );
    }
    else cout << "NOT Found ... NOT erasing Jill ...\n";
    print( my_lst );
   
   
    cout << "\n\nFind Joe ... ";
    cur = find( my_lst, "Joe" );
    if( cur )
    {
        cout << "Found ... erasing Joe ...\n";
        my_lst.erase( cur );
    }
    else cout << "NOT Found ... NOT erasing Joe ...\n";
    print( my_lst );

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

[David]

And now, similar to the above, but with a DLL ...

Code: [Select]

// insertSortedEraseDLL.h //  // 2017-02-11 //

// Note: still need to code copy ctor... and overloaded operator =
// But these are not needed in the short 'test code' used here. //

#ifndef _insertSortedEraseDLL_H_
#define _insertSortedEraseDLL_H_


template< typename T >
struct List
{
   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;
   

    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 insert_sorted( Node* nNode ) // nNode is a local copy //
    {
        nNode->next = nNode->prev = 0;
       
        // case 1 ... NOT inserted as the head node
        if( head  &&  head->val <= nNode->val )
        {
            // find Node to insert after
            Node* prev = head;
            Node* cur = head->next;
            while( cur && cur->val <= nNode->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;
    }
   
    // calls above method insert_sorted( Node* nNode ) //
    void insert_sort()
    {
        if( len > 1 ) // then head and cur != 0 //
        {
            Node* cur = head; // get copy //
            Node* next = cur->next; // get copy //
            head = tail = 0;
            len = 0;
            for( ; ; )
            {
                insert_sorted( cur );
                cur = next; // UPDATE from COPY //
                if( !cur ) break;
                next = cur->next;
            }
        }
    }
   
    // *** ASSUMPTION here *IS* that p passed in *IS* a *VALID* Node *** //
    void erase( Node* p )
    {
        if( p->prev && p->next )
        {
            p->prev->next = p->next;
            p->next->prev = p->prev;
        }
        else if( p->prev )
        {
            p->prev->next = 0;
            tail = p->prev;
        }
        else if( p->next )
        {
            p->next->prev = 0;
            head = p->next;
        }
        delete p;
        --len;
        if( !len ) head = tail = 0;
    }
   
    size_t size() const { return len; }
} ;


#endif

And a little test program for the above DLL ...

Code: [Select]

// insertSortedEraseDLL.cpp //  // 2017-02-11 //
 
 
#include <iostream>
#include <string>

// Note: still need to code copy ctor... and overloaded operator =
// But these are not needed in the short 'test code' used here. //
#include "insertSortedEraseDLL.h"

template< typename T >
void print(  const List< T >& lst, std::ostream& os = std::cout )
{
    typename List< T >::Node* cur;
    cur = lst.head;
    while( cur )
    {
        os << cur->val << ' ';
        cur = cur->next;
    }
    os << "size() = " << lst.size();
}

template< typename T >
void print_reversed(  const List< T >& lst, std::ostream& os = std::cout )
{
    typename List< T >::Node* cur;
    cur = lst.tail;
    while( cur )
    {
        os << cur->val << ' ';
        cur = cur->prev;
    }
    os << "size() = " << lst.size();
}



typedef List< std::string >::Node* MyNode;

MyNode find( List< std::string >& lst, const std::string& val )
{
    MyNode cur = lst.head;
    while( cur )
    {
        if( cur->val == val ) return cur;
        cur = cur->next;
    }
    return 0; // NOT found
}




int main()
{
    using namespace std;
   
    List< string > my_lst;

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

    cout << "\nPrinting reversed: ";
    print_reversed( my_lst );
    my_lst.clear();
   
    cout << "\n\nNow testing insert_sorted: ";
    my_lst.insert_sorted( "Anne" );
    my_lst.insert_sorted( "Sam" );
    my_lst.insert_sorted( "Zoe" );
    my_lst.insert_sorted( "Ann" );
    my_lst.insert_sorted( "Joe" );
    print( my_lst );

    cout << "\nPrinting reversed: ";
    print_reversed( my_lst );
   
    cout << "\n\nFind Ann ... ";
    MyNode cur = find( my_lst, "Ann" );
    if( cur )
    {
        cout << "Found ... erasing Ann ...\n";
        my_lst.erase( cur );
    }
    else cout << "NOT Found ... NOT erasing Ann ...\n";
    cout << "Printing reversed: ";
    print_reversed( my_lst );
   
   
    cout << "\n\nFind Joe ... ";
    cur = find( my_lst, "Joe" );
    if( cur )
    {
        cout << "Found ... erasing Joe ...\n";
        my_lst.erase( cur );
    }
    else cout << "NOT Found ... NOT erasing Joe ...\n";
    cout << "Printing reversed: ";
    print_reversed( my_lst );
   
   
    cout << "\n\nFind Sam ... ";
    cur = find( my_lst, "Sam" );
    if( cur )
    {
        cout << "Found ... erasing Sam ...\n";
        my_lst.erase( cur );
    }
    else cout << "NOT Found ... NOT erasing Sam ...\n";
    cout << "Printing reversed: ";
    print_reversed( my_lst );
   
   
    cout << "\n\nFind Zoe ... ";
    cur = find( my_lst, "Zoe" );
    if( cur )
    {
        cout << "Found ... erasing Zoe ...\n";
        my_lst.erase( cur );
    }
    else cout << "NOT Found ... NOT erasing Zoe ...\n";
    cout << "Printing reversed: ";
    print_reversed( my_lst );
   
   
    cout << "\n\nFind Anne ... ";
    cur = find( my_lst, "Anne" );
    if( cur )
    {
        cout << "Found ... erasing Anne ...\n";
        my_lst.erase( cur );
    }
    else cout << "NOT Found ... NOT erasing Anne ...\n";
    cout << "Printing reversed: ";
    print_reversed( my_lst );

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

[David]

And now ...

some timed testing of various sorts on a fairly full featured DLL ...


Firstly, the file with the relevant DLL ...

Code: [Select]

// DLLinsertSorted.h //  // revised: 2017-02-13 //

#ifndef DDL_INSERT_SORTED_H
#define DDL_INSERT_SORTED_H

#include <iostream>

template < typename T >
class List
{
    // forward declaration ... so can use inside nested iterator class //
    struct Node;   

public:
    // ctor...
    List() : head(0), tail(0), len(0) {}
   
    //dtor...
    ~List() { clear(); }
   
    void clear()
    {
        Node* del;
        while( head )
        {
            del = head;
            head = head->next;
            delete del;
        }
        tail = 0;
        len = 0;
    }

    // copy ctor...
    List ( const List& other )
    {
        head = tail = 0;
        len = 0;
        for( Node* cur = other.head; cur != 0; cur = cur->next )
            push_back( cur->data );
    }
   
    // overloaded operator =   (the assignment operator) //
    List& operator = ( const List& other )
    {
        if( this != &other )
        {
            clear();
            for( Node* cur = other.head; cur != 0; cur = cur->next )
                push_back( cur->data );
        }
        return *this;
    }
   
   
    size_t size() const { return len; }

    void push_front( const T& data )
    {
        Node* nNode = new Node( data );

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

        if( len )
        {
            tail->next = nNode; // T->N
            nNode->prev = tail; // T<-N
            tail = nNode;
        }
        else tail = head = nNode;
        ++len;
    }
   
   
   
    // (forward iterators) now added here ...
    // so can easily access elements ...
    // and here ... to ease testing of BOTH insert sorted methods //
   
    class iterator
    {
        Node* ptr;
       
    public:
        // ctor(s) ...
        iterator( Node* ptr=0 ) : ptr(ptr) {}
       
        iterator& operator ++ ()     { ptr = ptr->next; return *this; }
        // Note that you canNOT update via this as a COPY returned //
        iterator operator ++ ( int ) { iterator cpy(*this); ptr = ptr->next; return cpy; }
       
        bool operator != ( const iterator& it ) const { return  ptr != it.ptr; }
        bool operator == ( const iterator& it ) const { return  ptr == it.ptr; }
       
        const T& operator * () const  { return ptr->data; }
        T& operator * ()              { return ptr->data; }
       
        const T* operator -> () const { return &ptr->data; }
        T* operator -> ()             { return &ptr->data; }
    } ;

    iterator begin() { return iterator(head); }
    iterator end()   { return iterator(0); }
   
    typedef iterator const_iterator;

    const_iterator begin() const { return iterator(head); }
    const_iterator end() const   { return iterator(0); }

   
   
    void insert_sorted( const T& data )
    {
        Node* nNode = new Node( data );

        // case 1 ... NOT inserted as the head node
        if( head  &&  head->data <= data )
        {
            // find Node to insert after
            Node* prev = head;
            Node* cur = head->next;
            while( cur && cur->data <= data )
            {
                prev = cur;
                cur = cur->next;
            }
            // ok found spot ... insert after 'prev'

            prev->next = nNode;
            nNode->prev = prev;

            if( cur ) // NOT at end
            {
                cur->prev = nNode;
                nNode->next = cur;
            }
            else // at end
            {
                tail = nNode;
            }
        }
        else // insert at head ...
        {
            if( len )
            {
                nNode->next = head;
                head->prev = nNode;
                head = nNode;
            }
            else tail = head = nNode;
        }

        ++ len;
    }
   
    void insert_sort() // uses power of DLL //
    {
        if( len > 1 )
        {
            Node* cur = head->next;
           
            // start with set of just the first 2 elements (if exists) //
            for( ; cur != 0; cur = cur->next )
            {
                // get copy of this new cmp element on each outer loop //
                T cmp = cur->data;
                // get Node of element just to the left of the above 'cmp'
                // to start the comparisons //
                Node* prev = cur->prev;
                while( prev != 0 && cmp < prev->data )
                {
                    // copy element 'up' to open up 'insertion-hole' //
                    prev->next->data = prev->data;
                    // 'decrement' in preparation for next inner loop //
                    prev = prev->prev;
                }
                // insert element at prev->next (since prev was 'decremented' above) //
                if( prev ) prev->next->data = cmp;
                else head->data = cmp;
            }
        }
    }

    void select_sort()
    {
        Node* cur = head;
        while( cur )
        {
            Node* min = cur;
            Node* next = cur->next;
            while( next )
            {
                if( next->data < min->data ) min = next; // update if needed //
                next = next->next;
            }
           
            if( cur != min ) // swap min and cur //
            {
                T tmp = cur->data;
                cur->data = min->data;
                min->data = tmp;
            }
           
            cur = cur->next;
        }
    }

    void bubble_sort()
    {
        if( len > 1 )
        {
            Node* cur = head->next; // start 1 element in //
            int size = len;
            bool swap;
            do
            {
                swap = false;
                // added to speed up the bubble-up to *each decreasing new* top //
                int i = 0;
                //while( cur != 0 )
                // added to speed up the bubble-up to *each decreasing new* top //
                while( ++i < size )
                {
                    if( cur->data < cur->prev->data ) // swap //
                    {
                        T tmp = cur->data;
                        cur->data = cur->prev->data;
                        cur->prev->data = tmp;
                        swap = true;
                    }
                    cur = cur->next;
                }
                --size;
                // get ready ready for next outer (do) loop //
                cur = head->next;
            }
            while( swap );
            //while( size > 1 );
        }
    }
   
   

    // merge sort the whole list in place (a 'divide and sort' recursive sort) //
    void merge_sort()
    {
        Node* p = head;
        merge_sort( p, len ); // p is updated in recursion using pass by ref.
        set_head_tail( p );
    }
   
   
    // 3 utilities used for testing //
    void print( std::ostream& os = std::cout ) const
    {
        Node* cur = head;
        while( cur )
        {
            os << cur->data << ' ';
            cur = cur->next;
        }
    }
    void printReversed( std::ostream& os = std::cout ) const
    {
        Node* cur = tail;
        while( cur )
        {
            os << cur->data << ' ';
            cur = cur->prev;
        }
    }
    bool isSorted() const
    {
        if( len > 1 )
        {
            Node* cur = head;
            while( cur->next )
            {
                if( cur->next->data < cur->data ) return false;
                cur = cur->next;
            }
        }
        return true;
    }
   

private:
   
    struct Node
    {
        T data;
        Node* prev;
        Node* next;
       
        // ctor...
        Node( const T& data = T() ) : data(data), prev(0), next(0) {}
    } ;

    Node* head;
    Node* tail;
    size_t len;
   
   
    // defined below class ...
    void merge_sort( Node*& head, int len ); // returns updated head by ref.

    // merge two sorted lists with heads 'a' and 'b' ... in sorted order
    Node* merge( Node* a, Node* b )
    {
        if( a == 0 ) return b;
        if( b == 0 ) return a;

        Node* sorted;  // now get appropriate new head for merged list
        if( a->data <= b->data )
        {
            sorted = a;
            a = a->next;
        }
        else
        {
            sorted = b;
            b = b->next;
        }

        Node* new_merged_head = sorted;

        // now merge lists ...
        while( a != 0 && b != 0 )
        {
            if( a->data <= b->data )
            {
                sorted->next = a;
                sorted = sorted->next;
                a = a->next;
            }
            else
            {
                sorted->next = b;
                sorted = sorted->next;
                b = b->next;
            }
        }

        // now ... append the ONE part that might have been left-over above ...
        if( a != 0 )
            sorted->next = a;
        else if( b != 0 )
            sorted->next = b;

        return new_merged_head;
    }

    void update()
    {
        tail = head;
        if( tail == 0 ) return;
        Node* prev = 0;
        while( tail->next != 0 )
        {
            prev = tail;
            tail = tail->next;
            tail->prev = prev;
        }
        head->prev = 0;
    }

    void set_head_tail( Node* p ) { head = p; update(); }
   
} ;
   


/////////////////// BEGIN MERGE SORT ///////////////////////
// divide list into two halves and then recursively sort each half ...
// then merge the two sorted halves using the above merge function
// Note: calling 'head' is updated by using 'pass by ref'

template < typename T >
void List< T >::merge_sort( Node*& p1, int len )
{
    if( len < 2 ) return;

    Node* pHead2;
    Node* pEnd1;

    int size2 = len/2;
    int size1 = len - size2;

    // split the list into two lists ... the first half begins with head
    pEnd1 = p1; // first set pEnd1 to the head address ...
    for( int i = 1; i < size1; ++i )
        pEnd1 = pEnd1->next;

    pHead2 = pEnd1->next; // second half begins with pHead2
    pEnd1->next = 0; // breaking the chain here... so we can have two lists

    // merge the lists after recusively merge_sorting them
    merge_sort( p1, size1 );
    merge_sort( pHead2, size2 );

    p1 = merge( p1, pHead2 );
}//////////////////////////////// END MERGE SORT ///////////
#endif


[David]

Now a timed test program so that you can easily compare sorting times ...

Code: [Select]

// 6sorts_timed_all_auto_version.cpp //  // revised: 2017-02-13 //
 

#include "DLLinsertSorted.h"

// include <iostream> // included above //

#include <string>
#include <cstdlib>  // re, rand, srand
#include <ctime>    // re, time clock
#include <climits>  // re. RAND_MAX
#include <cctype>   // re. tolower
#include <cmath>    // re. log

#include <list>     // to compare c++ library 'list sort' times with 'list sort' times //


const int MAX_PRINT = 11;
const int MAX_NxN = 30000;


// 3 utilities to ease coding here ...
template< typename T >
T takeIn( const std::string& msg, const std::string& errMsg = "\nError! Try again.\n\n" )
{
    T val = T();
    while( true )
    {
        std::cout << msg;
        if( std::cin >> val && std::cin.get() == '\n' )
            break;
        else
        {
            std::cout << errMsg;
            std::cin.clear(); // clear error flasgs
            std::cin.sync(); // 'flush' cin stream ...
        }
    }
    return val;
}
char takeInChr( const std::string& msg )
{
    std::cout << msg;
    std::string reply;
    getline( std::cin, reply );
    if( reply.size() )
return reply[0];
    // else ...
    return 0;
}
bool more( const std::string& text = "" )
{
    char reply = takeInChr( "More " + text + "(y/n) ? " );
    if( reply == 'n' || reply == 'N' )
return false;
    // else ...
    return true;
}


// get a List of random ints in range 0..MAX_RAND
void fillUpList( List< int >& lst, int num )
{
    std::cout << "RAND_MIN = " << 0 << ", RAND_MAX = " << RAND_MAX << '\n';
    for( int i = 0; i < num; ++ i )
        lst.push_back( rand() );
}

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




int main()
{
    using std::cout; using std::cin;
    using std::string;
   
    srand( time(0) ); // seed the random generator //
   
    do
    {
        int num = 0;
        for( ; ; )
        {
            num = takeIn< int >( "How many numbers to sort (10..2000000): " );
            if( num >= 10 && num <= 2000000 ) break;
            //else ///
            cout << "\nTry again with a value in range 10..2000000 ...\n\n";
        }
       
        List< int > lstCpy;
        fillUpList( lstCpy, num );
       
        List< int > lst;
        List< int >::const_iterator cit;
        double dt, t1, k;

        if( num <= MAX_NxN )
        {
            lst = lstCpy; // get from a copy //
            t1 = clock();
            lst.insert_sort();
            dt = (clock() - t1)/CLOCKS_PER_SEC;
            cout << "\nTime to insert_sort was " << dt << " seconds "
                 << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
           
            // t = k*n*n;
            // k = t/n/n
            k = dt/num/num;
           
            lst = lstCpy;
            for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                lst.push_back( *cit );
            // Now size is doubled //
           
            t1 = clock();
            lst.insert_sort();
            dt = (clock() - t1)/CLOCKS_PER_SEC;
            cout << "\nTime to insert_sort was " << dt << " seconds "
                 << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
            cout << " Expected: " << 4*k*num*num << '\n';
                 

             

            lst.clear();
            t1 = clock();
            for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                lst.insert_sorted( *cit );
            dt = (clock() - t1)/CLOCKS_PER_SEC;
            cout << "\nTime to insert_sorted was " << dt << " seconds "
                 << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
                 
            k = dt/num/num;

            lst.clear();
            for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                lst.insert_sorted( *cit );
            for( cit = lstCpy.begin(); cit != lstCpy.end(); cit ++ ) // test POST ++ //
                lst.insert_sorted( *cit );
            // Now size is doubled //
     
            dt = (clock() - t1)/CLOCKS_PER_SEC;
           
            cout << "\nTime to insert_sorted was " << dt << " seconds "
                 << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
            cout << " Expected: " << 4*k*num*num << '\n';

                 
                 
                 
                 
            lst = lstCpy; // restore from copy //
            t1 = clock();
            lst.select_sort();
            dt = (clock() - t1)/CLOCKS_PER_SEC;
            cout << "\nTime to select_sort was " << dt << " seconds "
                 << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
                 
            k = dt/num/num;

            lst = lstCpy; // restore from copy //
            for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                lst.push_back( *cit );
            // Now size is doubled //
            t1 = clock();
            lst.select_sort();
            dt = (clock() - t1)/CLOCKS_PER_SEC;
           
            cout << "\nTime to select_sort was " << dt << " seconds "
                 << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
            cout << " Expected: " << 4*k*num*num << '\n';



            lst = lstCpy; // restore from copy //
            t1 = clock();
            lst.bubble_sort();
            dt = (clock() - t1)/CLOCKS_PER_SEC;
            cout << "\nTime to bubble_sort was " << dt << " seconds "
                 << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
                 
            k = dt/num/num;

            lst = lstCpy; // restore from copy //
            for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                lst.push_back( *cit );
            // Now size is doubled //
            t1 = clock();
            lst.bubble_sort();
            dt = (clock() - t1)/CLOCKS_PER_SEC;

            cout << "\nTime to bubble_sort was " << dt << " seconds "
                 << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
            cout << " Expected: " << 4*k*num*num << '\n';
         }
             



        lst = lstCpy; // restore from copy //
        if( num <= MAX_PRINT ) cout << "\nUnsorted: " << lst << '\n';
        t1 = clock();
        lst.merge_sort();
        dt = (clock() - t1)/CLOCKS_PER_SEC;
        cout << "\nTime to merge_sort was " << dt<< " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
             
        if( num <= MAX_PRINT )
        {
            cout << "\nSorted  : " << lst << "\nReversed: ";
            lst.printReversed();
            cout << '\n';
        }
       
        // t = k*n*log(n)
        // k = t/n*/log(n)
       
        k = dt/num/log(num);

        lst = lstCpy; // restore from copy //
        for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
            lst.push_back( *cit );
        // Now size is doubled //
        t1 = clock();
        lst.merge_sort();
        dt = (clock() - t1)/CLOCKS_PER_SEC;

        cout << "\nTime to merge_sort was " << dt << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
        cout << " Expected: " << k*2*num*log(2*num) << '\n';



             
        // compare with C++ library list ...
        std::list< int > cppLst;
        for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
            cppLst.push_back( *cit );
        t1 = clock();
        cppLst.sort();
        dt = (clock() - t1)/CLOCKS_PER_SEC;
        cout << "\nC++ library list sort was " << dt << " seconds.";
       
       
        k = dt/num/log(num);

        cppLst.clear();
        for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
            cppLst.push_back( *cit );
        for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
            cppLst.push_back( *cit );
        // Now size is doubled //
        t1 = clock();
        cppLst.sort();
        dt = (clock() - t1)/CLOCKS_PER_SEC;

        cout << "\nC++ library list sort was " << dt << " seconds.";
        cout << " Expected: " << k*2*num*log(2*num) << '\n';
       

        cout << '\n';
    }
    while( more() );
}

[David]

This next test program is similar to the above, but it is menu driven ...

(Note that it uses the same DLL .h file as was used/provided above.)

Code: [Select]

// 6sorts_timed_all_menu_version.cpp //  // revised: 2016-05-05 //
 

#include "DLLinsertSorted.h"

// include <iostream> // included above //

#include <string>
#include <sstream> // re. istringstream
#include <cstdlib> // re, rand, srand
#include <ctime>   // re, time clock
#include <climits> // re. RAND_MAX
#include <cctype>  // re. tolower
#include <cmath>   // re. log

#include <list>    // to compare c++ library 'list sort' times with 'list sort' times //


const int MAX_PRINT = 5;
const int MAX_NxN = 20000;
const int MAX = 2000000;

const std::string MENU =
    "1) Insert sort\n"
    "2) Insert sorted\n"
    "3) Select sort\n"
    "4) Bubble sort\n"
    "5) Merge sort\n"
    "6) C++ list sort\n"
    "0) Exit program\n"
    "Your choice 0..6 ";


// 2 utilities to ease coding here ...
template< typename T >
T takeIn( const std::string& msg, const std::string& errMsg = "\nError! Try again.\n\n" )
{
    T val = T();
    while( true )
    {
        std::cout << msg;
        if( std::cin >> val && std::cin.get() == '\n' )
            break;
        else
        {
            std::cout << errMsg;
            std::cin.clear(); // clear error flags
            std::cin.sync(); // 'flush' cin stream ...
        }
    }
    return val;
}
char takeInChr( const std::string& msg )
{
    std::cout << msg;
    std::string reply;
    getline( std::cin, reply );
    if( reply.size() )
return reply[0];
    // else ...
    return 0;
}



// get a List of random ints in range 0..MAX_RAND
void fillUpList( List< int >& lst, int num )
{
    std::cout << "RAND_MIN = " << 0 << ", RAND_MAX = " << RAND_MAX << '\n';
    for( int i = 0; i < num; ++ i )
        lst.push_back( rand() );
}

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


char showMenuGetChoice()
{
    return takeInChr( MENU );
}


int main()
{
    using std::cout; using std::cin;
    using std::string; using std::istringstream;
   
    srand( time(0) ); // seed the random generator //
   
    for( ; ; )
    {
        int num = 0;

        List< int > lst, lstCpy;
        List< int >::const_iterator cit;
       
        std::list< int > cppLst; // to compare times //
       
        double dt, t1, k;
       
        char choice = showMenuGetChoice();
        if( choice == '0' )
            break;
           
        int max_size = MAX;
        if( '1' <= choice && choice <= '4' )
            max_size = MAX_NxN;
           
        if( '1' <= choice && choice <= '6' )
        {
            // form prompt ...
            std::ostringstream oss;
            oss << "How many numbers to sort (3.." << max_size << ") : ";

            for( ; ; )
            {
                cout << "To see numbers printed, choose a number <= " << MAX_PRINT << '\n';
                num = takeIn< int >( oss.str() );
                if( num >= 3 && num <= max_size )
                    break;
                // else ...
                cout << "\nTry again with a value in range 3.." << max_size << " ...\n\n";
            }

            fillUpList( lstCpy, num );
        }
       
        switch( choice )
        {
            case '1':
                lst = lstCpy; // get from a copy //
                t1 = clock();
                lst.insert_sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;
                cout << "\nTime to insert_sort was " << dt << " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );

                // t = k*n*n;
                // k = t/n/n
                k = dt/num/num;

                lst = lstCpy;
                for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                    lst.push_back( *cit );
                // Now size is doubled //

                t1 = clock();
                lst.insert_sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;
                cout << "\nTime to insert_sort was " << dt << " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
                cout << " Expected: " << 4*k*num*num << '\n';
            break;
           
            case '2':
                lst.clear();
                t1 = clock();
                for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                    lst.insert_sorted( *cit );
                dt = (clock() - t1)/CLOCKS_PER_SEC;
                cout << "\nTime to insert_sorted was " << dt << " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );

                k = dt/num/num;

                lst.clear();
                for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                    lst.insert_sorted( *cit );
                for( cit = lstCpy.begin(); cit != lstCpy.end(); cit ++ ) // test POST ++ //
                    lst.insert_sorted( *cit );
                // Now size is doubled //

                dt = (clock() - t1)/CLOCKS_PER_SEC;

                cout << "\nTime to insert_sorted was " << dt << " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
                cout << " Expected: " << 4*k*num*num << '\n';
            break;
           
            case '3':
                lst = lstCpy; // restore from copy //
                t1 = clock();
                lst.select_sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;
                cout << "\nTime to select_sort was " << dt << " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );

                k = dt/num/num;

                lst = lstCpy; // restore from copy //
                for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                    lst.push_back( *cit );
                // Now size is doubled //
                t1 = clock();
                lst.select_sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;

                cout << "\nTime to select_sort was " << dt << " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
                cout << " Expected: " << 4*k*num*num << '\n';
            break;
           
            case '4':
                lst = lstCpy; // restore from copy //
                t1 = clock();
                lst.bubble_sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;
                cout << "\nTime to bubble_sort was " << dt << " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );

                k = dt/num/num;

                lst = lstCpy; // restore from copy //
                for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                    lst.push_back( *cit );
                // Now size is doubled //
                t1 = clock();
                lst.bubble_sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;

                cout << "\nTime to bubble_sort was " << dt << " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
                cout << " Expected: " << 4*k*num*num << '\n';
            break;
           
            case '5':
                lst = lstCpy; // restore from copy //
                if( num <= MAX_PRINT ) cout << "\nUnsorted: " << lst << '\n';
                t1 = clock();
                lst.merge_sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;
                cout << "\nTime to merge_sort was " << dt<< " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );

                // t = k*n*log(n)
                // k = t/n/og(n)

                k = dt/num/log(num);

                lst = lstCpy; // restore from copy //
                for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                    lst.push_back( *cit );
                // Now size is doubled //
                t1 = clock();
                lst.merge_sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;

                cout << "\nTime to merge_sort was " << dt << " seconds "
                     << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
                cout << " Expected: " << k*2*num*log(2*num) << '\n';
            break;
               
            case '6':
                // compare with C++ library list ...
                cppLst.clear();
                for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                    cppLst.push_back( *cit );
                t1 = clock();
                cppLst.sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;
                cout << "\nC++ library list sort was " << dt << " seconds.";


                k = dt/num/log(num);

                cppLst.clear();
                for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                    cppLst.push_back( *cit );
                for( cit = lstCpy.begin(); cit != lstCpy.end(); ++ cit )
                    cppLst.push_back( *cit );
                // Now size is doubled //
                t1 = clock();
                cppLst.sort();
                dt = (clock() - t1)/CLOCKS_PER_SEC;

                cout << "\nC++ library list sort was " << dt << " seconds.";
                cout << " Expected: " << k*2*num*log(2*num) << '\n';
            break;
           
            default: cout << "choice '" << choice << "' is NOT implemented here ...\n";
           
        } // end switch //
       
        if( num <= MAX_PRINT )
        {
            if( '1' <= choice && choice <= '5' )
            {
                cout << "\nSorted  : " << lst << "\nReversed: ";
                lst.printReversed();
            }
            else if( choice == '6' )
            {
                cout << "\nSorted  : ";
                std::list< int >::const_iterator ccit;
                for( ccit = cppLst.begin(); ccit != cppLst.end(); ++ ccit  )
                    cout << *ccit << ' ';

                cout << "\nReversed: ";
                std::list< int >::const_reverse_iterator rit;
                for( rit = cppLst.rbegin(); rit != cppLst.rend(); ++ rit  )
                    cout << *rit << ' ';
            }
        }
       
        cout << '\n';
       
    } // end while //
}



[David]

An observation to NOTE about sorting a container that already is mostly sorted ... note the following very quick ways to sort it then ...

Code: [Select]

// DDLsorts.h //  // 2017-02-13 //

#ifndef DDLSORTS_H
#define DDLSORTS_H

#include <iostream>

template < typename T >
class List
{
    struct Node
    {
        T data;
        Node* prev;
        Node* next;

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

    Node* head;
    Node* tail;
    size_t len;

public:
    // ctor...
    List() : head(0), tail(0), len(0) {}
   
    //dtor...
    ~List() { clear(); }
   
    void clear()
    {
        while( head )
        {
            Node* del = head;
            head = head->next;
            delete del;
        }
        tail = 0;
        len = 0;
    }

    // copy ctor...
    List ( const List& other )
    {
        head = tail = 0;
        len = 0;
        for( Node* cur = other.head; cur != 0; cur = cur->next )
            push_back( cur->data );
    }

    // for ... def'n of overloaded (assignment) operator =
    // see def'n below //
    List& operator = ( const List& other ) ;
    /*
    {
        if( this != &other )
        {
            clear();
            for( Node* cur = other.head; cur != 0; cur = cur->next )
                push_back( cur->data );
        }
        return *this;
    }
    */
   
    size_t size() const { return len; }

    void push_front( const T& data )
    {
        Node* nNode = new Node( data );

        if( len )
        {
            nNode->next = head; // N->A
            head->prev = nNode; // N<-A
            head = nNode;
        }
        else tail = head = nNode;
        ++len;
    }


    void push_back( const T& data )
    {
        Node* nNode = new Node( data );

        if( len )
        {
            tail->next = nNode; // B->N
            nNode->prev = tail; // B<-N
            tail = nNode;
        }
        else tail = head = nNode;
        ++len;
    }

    void insert_sorted( const T& data )
    {
        Node* nNode = new Node( data );

        // case 1 ... NOT inserted as the head node
        if( head  &&  head->data <= data )
        {
            // find Node to insert after
            Node* prev = head;
            Node* cur = head->next;
            while( cur && cur->data <= data )
            {
                prev = cur;
                cur = cur->next;
            }
            // ok found spot ... insert after 'prev'

            prev->next = nNode;
            nNode->prev = prev;

            if( cur ) // NOT at end
            {
                cur->prev = nNode;
                nNode->next = cur;
            }
            else // at end
            {
                tail = nNode;
            }
        }
        else // insert at head ...
        {
            if( len )
            {
                nNode->next = head;
                head->prev = nNode;
                head = nNode;
            }
            else tail = head = nNode;
        }

        ++ len;
    }

    // a re-link method ... might be faster? for LARGE data records ? //
    void insert_sorted( Node* nNode )
    {
        // case 1 ... NOT inserted as the head node
        if( head  &&  head->data <= nNode->data )
        {
            // find Node to insert after
            Node* prev = head;
            Node* cur = head->next;
            while( cur && cur->data <= nNode->data )
            {
                prev = cur;
                cur = cur->next;
            }
            // ok found spot ... insert after 'prev'

            prev->next = nNode;
            nNode->prev = prev;

            if( cur ) // NOT at end
            {
                cur->prev = nNode;
                nNode->next = cur;
            }
            else // at end
            {
                nNode->next = 0;
                tail = nNode;
            }
        }
        else // insert at head ...
        {
            nNode->prev = 0;
            if( len )
            {
                nNode->next = head;
                head->prev = nNode;
                head = nNode;
            }
            else { nNode->next= 0 ; tail = head = nNode; }
        }

        ++ len;
    }
   
    // Note! This method, (moving and re-linking Nodes),
    // is MUCH slower than that below, for small (int) data records tested //
    void relink_insert_sort()
    {
        if( len > 1 ) // then head and cur != 0 //
        {
            Node* cur = head;
            Node* next = cur->next;
            head = tail = 0;
            len = 0;
            for( ; ; next = cur->next )
            {
                insert_sorted( cur );
                cur = next;
                if( !cur ) break;
            }
        }
    }
   
    void insert_sort()
    {
        if( len > 1 )
        {
            Node* cur = head->next;

            for( ; cur != 0; cur = cur->next ) /* start with set of just the first 2 elements (if exists) */
            {
                T cmp = cur->data; /* get copy of this new cmp element on each outer loop ... */
                Node* prev = cur->prev; /* get Node of element just to the left of the above 'cmp' to start comparisons */
                while( prev != 0 && cmp < prev->data )
                {
                    prev->next->data = prev->data; /* copy element 'up' ... */
                    prev = prev->prev; /* decrement j in preparation for next inner loop ... */
                }
                /* insert element at prev->next (since prev was 'decremented' above) */
                if( prev ) prev->next->data = cmp;
                else head->data = cmp;
            }
        }
    }
   
    void select_sort()
    {
        Node* cur = head;
        while( cur )
        {
            Node* min = cur;
            Node* next = cur->next;
            while( next )
            {
                if( next->data < min->data ) min = next; // update if needed //
                next = next->next;
            }
           
            if( cur != min ) // swap min and cur //
            {
                T tmp = cur->data;
                cur->data = min->data;
                min->data = tmp;
            }
           
            cur = cur->next;
        }
    }
   
    void select_sort_simpler()
    {
        Node* cur = head;
        while( cur )
        {
            Node* min = cur;
            Node* next = cur->next;
            while( next )
            {
                if( next->data < min->data ) min = next; // update if needed //
                next = next->next;
            }

            T tmp = cur->data;
            cur->data = min->data;
            min->data = tmp;

            cur = cur->next;
        }
    }
   
    void bubble_sort()
    {
        if( len > 1 )
        {
            Node* end = 0;
            Node* cur = head->next; // start 1 element in //
            bool swap;
            bool pass = false;
            do
            {
                swap = false;
                while( cur != end )
                {
                    if( cur->data < cur->prev->data ) // swap //
                    {
                        T tmp = cur->data;
                        cur->data = cur->prev->data;
                        cur->prev->data = tmp;
                        swap = true;
                    }
                    cur = cur->next;
                }
               
                if( pass ) end = end->prev;
                else end = tail;
               
                pass = true;
               
                if( !end ) break;
               
                cur = head->next; // get ready ready for next outer (do) loop //
            }
            while( swap );
        }
    }
   
   
   
    void print( std::ostream& os = std::cout ) const
    {
        Node* cur = head;
        while( cur )
        {
            os << cur->data << ' ';
            cur = cur->next;
        }
    }

    void printReversed( std::ostream& os = std::cout ) const
    {
        Node* cur = tail;
        while( cur )
        {
            os << cur->data << ' ';
            cur = cur->prev;
        }
    }
   
    bool isSorted() const
    {
        if( len > 1 )
        {
            Node* cur = head;
            while( cur->next )
            {
                if( cur->next->data < cur->data ) return false;
                cur = cur->next;
            }
        }
        return true;
    }
   
} ;



// def'n of overloaded (assignment) operator =
template< typename T >
List< T >& List< T >::operator = ( const List& other )
{
    if( this != &other )
    {
        clear();
        for( Node* cur = other.head; cur != 0; cur = cur->next )
            push_back( cur->data );
    }
    return *this;
}
   

#endif

Now the test program for the above DLLsorts.h code ...

Code: [Select]

// test_DLLSorts.h.cpp //  // 2017-02-13 //
 

#include "DLLsorts.h"

// include <iostream> // included above //
#include <string>




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

    cout << "Now testing push_front: ";
    myLst.push_front( "Sam" );
    myLst.push_front( "Anne" );
    myLst.push_front( "Joe" );
    myLst.push_front( "Zak" );
   
    List< string > myLstCpy( myLst ); // construct a (backup) copy //
   
    myLst.print();
   
    cout << "\nPrinting after relink_insert_sort: ";
    myLst.relink_insert_sort();
    myLst.print();
   
    cout << "\nPrinting reversed: ";
    myLst.printReversed();
   
    myLst.clear();
   
   
    cout << "\n\nNow testing push_back: ";

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

    myLst.print();

    cout << "\nPrinting after insert_sort: ";
    myLst.insert_sort();
    myLst.print();

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

    myLst.clear();
   

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

    myLst.print();

    cout << "\nPrinting reversed: ";
    myLst.printReversed();
   
   
    myLst = myLstCpy; // restore from copy //
    cout << "\n\nPrinting before select_sort: ";
    myLst.print();

    cout << "\nPrinting after select_sort: ";
    myLst.select_sort();
    myLst.print();
   
   
    myLst = myLstCpy; // restore from copy //
    cout << "\n\nPrinting before select_sort_simpler: ";
    myLst.print();

    cout << "\nPrinting after select_sort_simpler: ";
    myLst.select_sort_simpler();
    myLst.print();
   
   
   
    myLst = myLstCpy; // restore from copy //
    cout << "\n\nPrinting before bubble_sort: ";
    myLst.print();

    cout << "\nPrinting after bubble_sort: ";
    myLst.bubble_sort();
    myLst.print();
   
   
   
    cout << "\n\nPress 'Enter' to continue/exit ...";
    cin.get();
}

And the timed sorts version ...

Code: [Select]

// timed_DLLsorts.cpp //  // 2017-02-13 //
 

#include "DLLsorts.h"

// include <iostream> // included above //

#include <string>
#include <sstream> // re. stringstream
#include <cstdlib> // re, rand, srand
#include <ctime> // re, time clock


const int MAX_SIZE = 30000;


template< typename T >
T takeIn( const std::string& msg, const std::string& errMsg = "\nError! Try again.\n\n" )
{
    T val = T();
    while( true )
    {
        std::cout << msg << std::flush;
        if( std::cin >> val && std::cin.get() == '\n' )
            break;
        else
        {
            std::cout << errMsg;
            std::cin.clear(); // clear error flasgs
            std::cin.sync(); // 'flush' cin stream ...
        }
    }
    return val;
}

char takeInChr( const std::string& msg )
{
    std::cout << msg;
    std::string reply;
    getline( std::cin, reply );
    if( reply.size() )
return reply[0];
    // else ...
    return 0;
}

bool more( const std::string& text = "" )
{
    char reply = takeInChr( "More " + text + "(y/n) ? " );
    if( reply == 'n' || reply == 'N' )
return false;
    // else ...
    return true;
}


void fillUpList( List< int >& lst, int num )
{
    for( int i = 0; i < num; ++ i )
        lst.push_back( rand() );
}




int main()
{
    using std::cout; using std::cin;
    using std::string; using std::stringstream;
   
    srand( time(0) ); // seed the random generator //
   
    do
    {
        int num = 0;
        for( ; ; )
        {
            stringstream ss;
            ss << MAX_SIZE;
            num = takeIn< int >( "How many numbers to sort (10000.." + ss.str() + "): " );
            if( num >= 10000 && num <= MAX_SIZE ) break;
            //else ///
            cout << "\nTry again with a value in range 10000.." << MAX_SIZE << " ...\n\n";
        }
       
        List< int > lst;
        fillUpList( lst, num );
       
        List< int > lstCpy( lst ); // save a (backup) copy //
       
       
        double t1 = clock();
        lst.insert_sort();
        double t2 = clock();
        cout << "\nTime to insert_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
             
        lst.push_front(1000000);
        cout << "\nIf already was (mostly) sorted ...\n";
        t1 = clock();
        lst.insert_sort();
        t2 = clock();
        cout << "Time to insert_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
             


        lst = lstCpy;
        t1 = clock();
        lst.relink_insert_sort();
        t2 = clock();
        cout << "\n\nTime to relink_insert_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );

        lst.push_front(1000000);
        cout << "\nIf already was (mostly) sorted ...\n";
        t1 = clock();
        lst.relink_insert_sort();
        t2 = clock();
        cout << "Time to relink_insert_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
             
             
        lst = lstCpy; // restore from copy //
        t1 = clock();
        lst.select_sort();
        t2 = clock();
        cout << "\n\nTime to select_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
             
        lst.push_front(1000000);
        cout << "\nIf already was (mostly) sorted ...\n";
        t1 = clock();
        lst.select_sort();
        t2 = clock();
        cout << "Time to select_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
             

        lst = lstCpy; // restore from copy //
        t1 = clock();
        lst.select_sort_simpler();
        t2 = clock();
        cout << "\n\nTime to select_sort_simpler was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );

        lst.push_front(1000000);
        cout << "\nIf already was (mostly) sorted ...\n";
        t1 = clock();
        lst.select_sort_simpler();
        t2 = clock();
        cout << "Time to select_sort_simpler was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
             
             
        lst = lstCpy; // restore from copy //
        t1 = clock();
        lst.bubble_sort();
        t2 = clock();
        cout << "\n\nTime to bubble_sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );
             
        lst.push_front(1000000);
        cout << "\nIf already was (mostly) sorted ...\n";
        t1 = clock();
        lst.bubble_sort();
        t2 = clock();
        cout << "Time to bubble sort was " << (t2-t1)/CLOCKS_PER_SEC << " seconds "
             << ( lst.isSorted() ? "and SORTED ok." : "but was NOT sorted!" );


        cout << "\n\n";
    }
    while( more() );


}