Can someone explain why i'm getting an infinite loop for my linked list and how to fix it?

Question

I'm new to C++ and i'm trying to write a method to add a node to the end of a linked list but i'm getting an infinite loop and i'm not sure why.

#include "Car.h"

Car::Car()
{
    this->pName = NULL;
    this->pNext = NULL;
}

Car::Car(const char *name)
{
    this->pName = name;
    this->pNext = NULL;
}

#include "Garage.h"

Garage::Garage()
{
    this->pHead = NULL;
}

void Garage::AddToFront(Car *r) 
{
    if (this->pHead != NULL) 
    {
        Car *tmp = this->pHead;
        this->pHead = r;
        r->pNext = tmp;
    }
    this->pHead = r;
}

void Garage::Print(const char *string)
{
    Trace::out("Garage(%s): \n",string);
    Car tmp = *pHead;
    while (tmp.pNext != NULL) 
    {
        Trace::out("\tCar(%s)--->%s \n", tmp.pName, tmp.pNext->pName);
        tmp = *tmp.pNext;
    }
    Trace::out("\tCar(%s)--->%s \n", tmp.pName, "(null)");
    Trace::out("\n");
}

void Garage::Remove(Car *r)
{
    Car *tmp = this->pHead;
    Car *prev = NULL;
    if (pHead == r)
    {
        pHead = r->pNext;
        return;
    }
    while (tmp != NULL && tmp != r)
    {
        prev = tmp;
        tmp = tmp->pNext;
    }
    prev->pNext = tmp->pNext;
}

void Garage::AddToEnd(Car *r)
{
    if (pHead == NULL)
    {
        pHead = r;
        return;
    }
    else
    {
        Car *tmp = pHead;
        while (tmp->pNext != NULL)
        {
            tmp = tmp->pNext;
        };
        tmp->pNext = r;
        return;
    }
}

int main()
{
    // -------------------------------------------------
    // Do not change the main() function in any way
    // -------------------------------------------------
    // Output needs to match PDF exactly
    //--------------------------------------------------

    Car A("Jetta");
    Car B("Accord");
    Car C("Forte");
    Car D("Outback");
    Car E("Escape");

    Garage G;

    G.AddToFront(&A);
    G.AddToFront(&B);
    G.AddToFront(&C);
    G.AddToFront(&D);
    G.AddToFront(&E);

    G.Print("Add to Front");

    G.Remove(&A);
    G.Remove(&C);
    G.Remove(&E);

    G.Print("Remove A,C,E");

    G.AddToEnd(&A);
    G.Print("After A");
    G.AddToEnd(&C);
    G.Print("After C");
    G.AddToEnd(&E);

    G.Print("Add to End");

I've tried debugging and printing my list but I can't figure out what to do. It looks like i've made my list circular but i'm not sure how I did this and how to fix it. I can post my header files too if that would be helpful to debugging this.

Answer 1

Can someone explain why I'm getting an infinite loop for my linked list and how to fix it?

The linked list in the OP is a brittle structure that depends on the the allocation of Car nodes in function main. Functions in struct Garage do not copy Car nodes when they are inserted into the Garage list. Instead, the Garage list simply stores pointers to the Car nodes that are allocated in function main.

When you remove Car* r from the Garage list, r->pNext continues to point into the Garage list.

When that same car is added back at the end of the list, you create a loop in the Garage list.

One way to fix both problems is to set r->pNext to nullptr when Car* r is removed from the Garage list.

Here is my version of function Remove. It calls helper function FindPrev, which, in all but a few special cases, returns a pointer to the node that precedes Car* r in the Garage list.

FindPrev returns nullptr when:

• The Garage list is empty.
• Car* r is not found in the Garage list.
• Car* r is found at the head of the Garage list.
• r is nullptr.

Car* Garage::FindPrev(Car* r)
{
    if (r == nullptr || pHead == nullptr || r == pHead)
        return nullptr;
    Car* p{ pHead->pNext };
    Car* prev{ pHead };
    while (p != nullptr && p != r)
    {
        prev = p;
        p = p->pNext;
    }
    return p ? prev : nullptr;
}

void Garage::Remove(Car* r)
{
    if (r == nullptr || pHead == nullptr)
        return;
    else if (pHead == r)
    {
        pHead = pHead->pNext;
        r->pNext = nullptr;
    }
    else if (auto p{ FindPrev(r) }; p)
    {
        p->pNext = r->pNext;
        r->pNext = nullptr;
    }
}

As a precaution, function AddToEnd should set r->pNext to nullptr, as well. My version includes a check to see whether Car* r is nullptr.

void Garage::AddToEnd(Car* r)
{
    if (r == nullptr)
        return;
    else if (pHead == nullptr)
    {
        pHead = r;
        r->pNext = nullptr;
    }
    else
    {
        Car* tmp = pHead;
        while (tmp->pNext != nullptr)
        {
            tmp = tmp->pNext;
        };
        tmp->pNext = r;
        r->pNext = nullptr;
    }
}

Incidentally, function AddToFront can be simplified. Once again, I have added a check to verify that r is not nullptr. You need that in all the functions that accept r as a parameter.

void Garage::AddToFront(Car* r)
{
    if (r != nullptr)
    {
        r->pNext = pHead;
        pHead = r;
    }
}

Output:

Garage(Add to Front):
        Car(Escape)--->Outback
        Car(Outback)--->Forte
        Car(Forte)--->Accord
        Car(Accord)--->Jetta
        Car(Jetta)--->(null)

Garage(Remove A,C,E):
        Car(Outback)--->Accord
        Car(Accord)--->(null)

Garage(After A):
        Car(Outback)--->Accord
        Car(Accord)--->Jetta
        Car(Jetta)--->(null)

Garage(After C):
        Car(Outback)--->Accord
        Car(Accord)--->Jetta
        Car(Jetta)--->Forte
        Car(Forte)--->(null)

Garage(Add to End):
        Car(Outback)--->Accord
        Car(Accord)--->Jetta
        Car(Jetta)--->Forte
        Car(Forte)--->Escape
        Car(Escape)--->(null)