LinkedList "node jump"

Question

Trying to figure out why my list() class pointers are being overwritten with the third node. What happens in the insert function (below) is that the third time the insert function is called my "headByName->nextByName" node pointer is overwritten by the third node, when it should point to the second. So as you can guess the 4th node is overwritten by the 5th and the 6th node is overwritten by the 7th, hence the "jump" in nodes.

The attributes of the winery object are passed through the winery ctor and then to the list::insert function via these calls in main:

//main.cpp
//the attributes of the winery object are the paramaters, name, location, acres, rating:
list *listPtr = new list();
wineries->insert(winery("Lopez Island Vinyard", "San Juan Islands", 7, 95));
wineries->insert(winery("Gallo", "Napa Valley", 200, 25));
wineries->insert(winery("Cooper Mountain", "Willamette Valley", 100, 47));

Then the winery ctor is called where I allocate the private pointer memembers:

//winery.cpp
winery::winery(const char * const name, const char * const location, const int acres, const int rating)
  : m_acres( acres ), m_rating( rating )
{
    if (name)
    {
     size_t len = strlen( name ) +1;
     m_name = new char[len];
     strcpy_s( m_name, len, name );
    }
    else
     m_name = NULL;

    if (location)
    {
     size_t len = strlen( location ) +1;
     m_location = new char[len];
     strcpy_s( m_location, len, location );
    }
    else
     m_location = NULL;
}

And then to the issue at hand: If you can imagine this function has already been called twice then current_node will have the thrid winery. headByName will have the first node and in it [+], headByName->next will have the third. I need headByName->next to have the second. I am just wondering why it has been overwritten..

// list.cpp
void list::insert(const winery& winery)
{
    node *current_node = new node( winery ); // the third wineries info!
    node *next_node  = NULL;
    list *list_ptr  = NULL;
    do
    {
     if ( headByName == NULL || headByRating == NULL ) // then we are here for the first item
     { 
      headByName  = current_node; // the list ptrs have a node address. 
      headByRating = current_node;
     } 
     else
     {   

      next_node       = current_node; 
// transfer by the next call in main.
      headByName->nextByName    = next_node;
      headByRating->nextByRating = next_node;

     }
    } while ( headByName == NULL || headByRating == NULL );

    next_node  = NULL;
    current_node = NULL;
}

Could someone please find my second node? oh yeah, and the pointers that are available to me:

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

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

this might be of some importance, its the body of the node ctor:

//list.cpp
list::node::node(const winery &winery) :
nextByName( NULL ), nextByRating( NULL ), item( winery.getName(),
winery.getLocation(), winery.getAcres(), winery.getRating() )
{
    // where the item paramters are all pub-mem functions of the winery class.  

}

Answer 1

I think that problem is here:

headByName->nextByName     = next_node;
headByRating->nextByRating = next_node;

You're always override second node. As I understand you should find last one by iterating through whole list and insert after last node.

Answer 2

Well the primary issue is that when you insert a node you ALWAYS set

headByName->nextByName     = next_node;
headByRating->nextByRating = next_node;

So the second node gets filled appropriately. Then the third comes along and ovrwrites the second node and the second node disappears into oblivion.

Answer 3

Your constructor is not related but the first thing that sticks out is this error in assignment logic:

headByName->nextByName     = next_node;
headByRating->nextByRating = next_node;

Here you're always setting the next node of the head node (the 2nd node) to whatever the new node is. That's why the second node in the list is always the newest one.

If you wish to add items onto the end of the list, you should keep a tail pointer that points to last item inserted, starting from the head item.

With that your assignment would instead be:

tail_pointer->nextByName = current_node;
tail_pointer->nextByRating = current_node;

tail_pointer = current_node;

Secondly, the do/while loop is unnecessary. headByName and headByRating will always be set to point to the newly allocated node current_node, meaning that

while ( headByName == NULL || headByRating )

will always break out of the loop (provided that you aren't running out of memory of course).

You are always assigning both variables by using lazy initialization in the first if block in list::insert.

Linked List inserts are constant time, O(1), because you don't have to iterate anything in a loop - you always know exactly where to operate on: tail_pointer.

Also, this:

next_node    = NULL;
current_node = NULL;

is good style in my opinion, but don't forget that you are not actually deallocating the data with this, in case that was your intention :-)

Keep a tail pointer that always points to the newest item!