Sorting a Doubly Linked List C++

Trying to do it through a loop that traverses through the list.

In the loop I'm feeding the head node into a sorting function that I have defined and then I'm using strcmp to find out if which name in the node should come first.

It is not working because writing the names too early.

Im comparing them all linearly by going down the list one node at a time and not going back to see if the first should come before the last. That part explained would be helpful.

The two functions that are most important to me now are defined as follows:
I have tried my best to do what I think is right for the sorting function.

void list::displayByName(ostream& out) const
{
    list *ListPtr = NULL;
    node *current_node = headByName;
    winery *wine_t = new winery(); 
    // winery is another class object type
    // im allocating it to prevent a crash when I call it.


    while ( current_node != NULL )
    {
        *(wine_t) = current_node->item;
        wine_t = ListPtr->sort( current_node );
        out << wine_t << endl;
        current_node = current_node->nextByName;
    }
    delete wine_t;
}


winery * const list::sort( node * current_node ) const
{
    // current_node is the first node.
    const char *SecondName = NULL, *FirstName  = NULL;
    winery *wine_t   = new winery();

    if ( current_node != NULL )
    {
        SecondName   = current_node->item.getName();            

        current_node = current_node->nextByName;
        FirstName    = current_node->item.getName();
    }

    if ( strcmp( FirstName, SecondName ) == -1 )
    {
        *(wine_t)  = current_node->item;
        FirstName  = NULL;
        SecondName = NULL;
        return wine_t;

    }
    else if ( strcmp( FirstName, SecondName ) == 1 )
    {
        *(wine_t) = current_node->item;
        FirstName = NULL;
        SecondName = NULL;
        return wine_t;
    }
    else return wine_t;// then the strings are equal


    FirstName  = NULL;
    SecondName = NULL;
    return wine_t;
}

And I started to develop my nodes here:

void list::insert(const winery& winery)
{

    node *current_node = new node( winery );

    if ( headByName == NULL )
    {
        headByName   = current_node;
        headByRating = current_node;
        tail         = headByName;
        current_node->prev = current_node;
    }
    else

    {
        current_node->prev = tail;
        tail->nextByName   = current_node;
    }

    tail = current_node;
    current_node = NULL;
}

I think its correct in that function above. Could I possibly get away with sorting it there?

Below are my varaibles that I am working with:

public list
{
         ...
    void insert(const winery& winery);
    void displayByName(ostream& out) const;
}

private:
    struct node
    {
        node(const winery& winery);     // constructor
        winery item;
        node * prev;
        node * nextByName;
        node * nextByRating;
    };


    winery * const sort(node*) const;
    node * headByName;
    node * headByRating;
    node * tail;
};

Any help is appreciated.
Thanks very much =)

Answer

From what I understand, you want list::sort to find the least node in the list which is greater than the input.

To do this, you need to iterate through all the elements and keep the current least-but-greater node found.

Something like this:

node * const list::sort( node * given_node ) const
{
    if ( given_node == NULL )
    {

        return NULL;
    }

    // Smallest node found which is greater than given_node.
    node * least_found_node = NULL;

    // Node we are looking at right now.
    node * current_node = given_node->nextByName;

    // Go through all nodes.

    while ( current_node && current_node != given_node )
    {
        // Is this node bigger than the given node?
        if ( strcmp( current_node->item.getName(), given_node->item.getName() ) < 0 )
        {
            // Is this node smaller than the smallest node we know of?
            if ( least_found_node == NULL ||
               ((strcmp( current_node->item.getName(), least_found_node->item.getName() ) > 0) )
            {
                // We found a better node.

                least_found_node = current_node;
            }
        }

        current_node = current_node->nextByName;
    }

    return least_found_node;
}

Now change your display function to use it like this:

void list::displayByName(ostream& out) const
{
    // Find first node initially.
    node * current_node = sort( NULL );

    while ( current_node != NULL )
    {

        // Print node.
        out << current_node->item.getName();

        // Find next node in sorted output.
        current_node = sort( current_node );
    }
}

This part keeps calling sort until sort returns NULL. The first call to sort is with NULL so the lowest item is found (that is, the first in the sorted list). sort returns NULL if there are no more nodes larger than current_node, thus terminating the loop.