Understanding why a string stored in a linked list won't print properly

Question

I'm working on an assignment where I've been given specific member functions I need to complete for a linked-list. One of them requires me to copy a node, change its name, delete the old node and reinsert the new one back into the list. I've come up with this code

while(start != NULL)
{
    if(start->id == nID) 
    {
        start->name = newName;
        holdNode = start;
        removeNode(nID); //removes start from the linkedlist
        addNode(holdNode->name, holdNode->id, holdNode->cost); 

        found = true; 
        break;
    }
    else
        start = start->next; 

I get the correct output in xcode, but when I run it with g++ the name field is either empty or a series of random characters. I'm guessing it has something to do with pointing to the start node and then deleting it, but I can't figure out why it will work in one place but not the other.

Xcode Output

1, testing, $9.99

g++

1, , $9.99

Any help is very much appreciated

Answer 1

Your code is not making any copy of a node. It merely updates the name of the existing node that it finds, then it saves a pointer to that node, removes that node from the list invalidating the pointer you just saved, then tries to use that invalid pointer to get the values to use when inserting a new node. That is where your code is failing.

Try this instead:

bool changeName(int nID, string newName)
{
    Product *node = head;

    while (node) //while there are items in the list
    {
        if (node->id == nID) //if ids match
        {
            double price = node->price;
            removeNode(nID); //remove node from the linkedlist
            addNode(newName, nID, price); //insert new node
            return true;
        }

        node = node->next; //move to next node
    }

    return false;
}

Live Demo

However, this is a little inefficient, as removeNode() is likely doing the same id search all over again. A linked list is able to insert and remove a node quickly, without traversing the list multiple times. Just unlink the found node from its surrounding nodes. At the very least, you can get rid of the call to removeNode() in changeName() like this:

bool changeName(int nID, string newName)
{
    Product *node = head, *prev = NULL;

    while (node) //while there are items in the list
    {
        if (node->id == nID) //if ids match
        {
            double price = node->price;

            //remove node from the linkedlist
            //removeNode(nID);
            if (prev) prev->next = node->next;
            if (node == head) head = node->next;
            delete node;

            //insert new node
            addNode(newName, nID, price);

            return true; 
        }

        prev = node;
        node = node->next; //move to next node
    }

    return false;
}

Live Demo

Another option would be to not actually destroy the found node at all, simply relocate it as-is. Unlink it from its surrounding nodes, and then link it to the nodes at the desired new position, eg:

bool changeName(int nID, string newName)
{
    Product *node = head, *prev = NULL;

    while (node) //while there are items in the list
    {
        if (node->id == nID) //if ids match
        {
            //remove node from the linkedlist
            if (prev) prev->next = node->next;
            if (node == head) head = node->next;

            //insert node in new position
            Product **node2 = &head;
            while ((*node2) && ((*node2)->name < newName)) {
                node2 = &((*node2)->next);
            }

            node->name = newName;
            node->next = *node2;
            *node2 = node;

            return true; 
        }

        prev = node;
        node = node->next; //move to next node
    }

    return false;
}

Live Demo