Linked list implementation very tiny question-CodePudding

#include <string>
using namespace std;

struct Link {
    string value;
    Link* prev;
    Link* succ;
    Link(const string& v, Link* p = nullptr, Link* s = nullptr)
        : value{ v }, prev{ p }, succ{ s } { }
};

Link* erase(Link* p) // remove *p from list; return p’s successor
{
    if (p == nullptr) return nullptr;

    if (p->succ) p->succ->prev = p->prev;
    if (p->prev) p->prev->succ = p->succ;
    return p->succ;

}
Link* find(Link* p, const string& s) // find s in list;
// return nullptr for “not found”
{
    while (p) {
        if (p->value == s) return p;
        p = p->succ;
    }
    return nullptr;
}

So this is like the implementation with some helper functions, (this is from a book) and then the author does this to make a linked list:

Link* norse_gods = new Link{ "Thor" };
norse_gods = insert(norse_gods, new Link{ "Odin" });
norse_gods = insert(norse_gods, new Link{ "Zeus" });
norse_gods = insert(norse_gods, new Link{ "Freia" });
Link* greek_gods = new Link{ "Hera" };
greek_gods = insert(greek_gods, new Link{ "Athena" });

greek_gods = insert(greek_gods, new Link{ "Mars" });
greek_gods = insert(greek_gods, new Link{ "Poseidon" });

Basically my question is he says this:

Link* p = find(norse_gods, "Zeus");
if (p) {
    erase(p);
    insert(greek_gods, p);
}

Did you notice the bug? It’s quite subtle (unless you are used to working directly with links). What if the Link we erase() is the one pointed to by norse_gods? Again, that doesn’t actually happen here, but to write good, maintainable code, we have to take that possibility into account:

Link* p = find(norse_gods, "Zeus");
if (p) {
    if (p == norse_gods) norse_gods = p– > succ;
    erase(p);
    greek_gods = insert(greek_gods, p);
}

I just don't understand what the bug is? Is it just that norse_gods will now point to NULL because we erased it?

Also here he just calls erase() which returns something but doesn't do anything with the value returned right?

CodePudding user response：

Although the insert() function is not shown, it is clear based on the context that it expects its first parameter to be an existing node in the linked list. Otherwise it will not work correctly.

What if the Link we erase() is the one pointed to by norse_gods?

Then it is no longer a member of the linked list, by definition. Using insert(), now, results in all sorts of hilarity.

CodePudding user response：

You created a list the first node of which is pointed to by the pointer norse_gods.

Link* norse_gods = new Link{"Thor"};
norse_gods = insert(norse_gods,new Link{"Odin"});
norse_gods = insert(norse_gods,new Link{"Zeus"});
norse_gods = insert(norse_gods,new Link{"Freia"});

Now assume that you are going to remove from the list the first node. To do that you are calling the function

erase( norse_gods );

Now the list will start from the next node after the removed first node. But the pointer norse_gods in main still points to the previous first node of the list. That is the new state of the list was not reflected in the pointer that points to the previous removed first node of the list.