How do you insert into a sorted linked list?

Question

I just need to have a linked list in order by name. I can only get it as far as 1st, 3rd, 5th, .. nodes. I just can't think this far. I want to be a C++ programmer but if I can't understand this is their any hope? STL containers std::lists are not an option for me at this point as a student. What you see in the list function is what I am TRYING to understanding.

list::node::node(const winery &winery) : item( winery.getName(), winery.getLocation(),
    winery.getAcres(), winery.getRating() ), nextByName( NULL ), nextByRating( NULL )
{

}

void list::insert(const winery& winery)
{
    node *current_node  = new node( winery ); // but came here and did this so it has new info!
    node *next_node  = NULL;
    node *tail_node     = current_node;

    if ( headByName == NULL ) // then we are here for the first item
    {       
        headByName   = current_node; // the list ptrs will have the first node's address. 
        headByRating = current_node; 
    }
    while ( headByName->nextByName != NULL )
    {
        headByName->nextByName = tail_node;
        tail_node = next_node;
        //next_node = current_node;
    }
    tail_node = new node( winery ); 
    headByName->nextByName = tail_node;
}

And the pointers that are available to me:

struct node
{
    winery  item;
    node *  nextByName;
    node *  nextByRating;
};

class list
{
    ...
private:
    node * headByName;
    node * headByRating;
};

Answer 1

To be a doubly-linked list each node must have a pointer to the node before and after it. You can also store a head and tail node if you like, but that would be more for personal convenience than to meet the requirements of a doubly-linked list.

Answer 2

I'm not sure I understand your question exactly. Going just from the topic "How do you insert into a sorted linked list?" I would do something like this (pseudocode):

list::insert(Winery winery) {
    Winery node = getHeadNode();

    // winery comes before the head node
    if (winery.name < node.name) {
        // the old head node now goes after this new node
        // and this new node becomes the new head node
        winery.next = node;
        setHeadNode(winery);
        return;
    }

    // let's iterate over the rest of the nodes in the list
    Winery previous_node = node;
    node = node.next;
    while (node != NULL) {
        // we found our insertion point
        if (winery.name < node.name) {
            // insert our new node
            previous_node.next = winery;
            winery.next = node;
            return;
        }

        // insertion point not found, move to the next node and repeat
        previous_node = node;
        node = node.next;
    }

    // all elements visited, append our new element to the end of the list
    previous_node.next = winery;
    winery.next = NULL;
}

The above algorithm will insert your new node in the appropriate place in the list, assuming the list is sorted by name.

Answer 3

You called this a doubly linked list, and although it's true that your nodes each have two links, this isn't really what most people think of when they hear about doubly linked lists. Since your two links are apparently unrelated to each other — nobody rates wineries alphabetically — it will be a little easier if you don't think of this as a doubly linked list.

The usual place to insert into a linked list, when a more specific order isn't required, is at the end of the list. The steps to do that are as follows:

1. Create a new node.
2. Find the place to insert the new node (i.e., the last node, at end of the list)
3. Update the last node's "next" pointer to point to the new node.

When you're inserting into what may be the middle of the list, as is the case for you, then there is another step:

2.5. Update the new node's "next" pointer.

The reason that step isn't usually there is that when inserting at the end of a list, the new node's "next" pointer is already null from when you constructed the new node object.

You've figured out the first step already. In fact, you've done it too well because your code actually creates two new nodes. One you store in current_node and the other you store in tail_node. Get rid of the second one.

Step 2 is about figuring out which node should be the one that immediately precedes the new node. When ordering by name, that would be the node that comes before the first node you find that has a name after the current name. You're going to have to walk along the list, possibly looking at every node, until you find one that belongs after the new node's name. As you move along the list, you're going to have to keep track of which node came before that node, too, because once you find the node you're looking for, you're going to have to backtrack.

Worry about the name and the rating separately. Don't try to solve both parts at once. Once you get the winery inserted correctly by name, then duplicate that code and replace "name" with "rating." But don't create another node object. Keep using the same one you created before.

As you've worked on this assignment, have you drawn any pictures of nodes with arrows pointing to other nodes? Try it. You've surely seen it done in your textbook or on your teacher's chalkboard. If a problem is too big for you to reason about entirely in your head, then use something to help you keep track of things outside your head. The professionals do it, too. Since each node has multiple pointers, you should either label the pointers or use different colors for name and rating.

Answer 4

Of course there's hope, we all have to start somewhere! :)

First of all, I must point out a dangerous practice in your implementation that my own students used, and it usually resulted in lots of head scratching to find the problem:

while ( headByName->nextByName != NULL )
{
     headByName->nextByName = tail_node;
     tail_node = next_node;
     //next_node = current_node;
}

Don't use a list member like headByName as your iterating variable within your loop unless it is absolutely necessary. You should find the appropriate node first using a local variable, and then modify that node.

That said, Rob Kennedy is right that you should handle the name and rating separately (in other words a 'pure' implementation would have two instances of a generic list class that is unaware of what 'name' and 'rating' mean), however I assume the interfaces for list, node and function above were given to you in the assignment (if not, disregard the rest of my answer :) ).

Given the above interfaces, my approach would be as follows:

void list::insert(const winery& winery)
{
    node* wineryNode = new node(winery);
    assert (wineryNode);

    // Find  a node in the list with a name greater than wineryNode's
    node* prevNode = NULL;
    node* searchNode = headByName; // Note: not using the list member itself to iterate but a local variable
    while (NULL != searchNode && 
     searchNode.winery.getName() < wineryNode.winery.getName())
    {
     // Keep iterating through the list until there are no more items, or the right node is found
     prevNode = searchNode;
     searchNode = searchNode->nextByName;
    } 

    /* At this point searchNode is either NULL 
       or it's name is greater than or equal to wineryNode's */

    // Check for the case where the list was empty, or the first item was what we wanted
    if (NULL == prevNode)
    {
     headByName = wineryNode;
    }
    else
    {
     // prevNode is not NULL, and it's Name is less wineryNode's
     prevNode-> nextByName = wineryNode;
    }
    wineryNode->nextByName = searchNode; 

    /*  Now you just need to insert sorted by rating using the same approach as above, except initialize searchNode to headByRating, 
    and compare and iterate by ratings in the while loop. Don't forget to reset prevNode to NULL */
}