4
\$\begingroup\$

The following code seems to work ok to remove a node from a linked list:

bool remove(node * & head, int toBeRemoved)
{
 if (head == nullptr)  //empty list
        return false;
    else {
        node * temp = head;

        //the first node needs to be removed
        if (head->data == toBeRemoved) { 
            head = head->next;
            delete temp;
            return true;
        }

        //seek for node and remove it
        else {
            while (temp->next != nullptr && temp->next->data != toBeRemoved)
                temp = temp->next;
            if (temp->next->data == toBeRemoved){
                node * removeThis = temp->next;
                temp->next = temp->next->next;
                delete removeThis;
                return true;
            }

            //data to be removed can't be found in the list
            else
                if (temp->next == nullptr && temp->next->data != toBeRemoved)
                    return false;
        }
    }
}

(I understand there's a list implementation in C++ but I'm only trying to understand this algorithm here, not replace it with something else).

Even though the code works fine to delete a node placed at the beginning, in between or at the end of a list, I still have some doubts about the following line: if (temp->next->data == toBeRemoved) (it's the first if after the while).

Since that whole block can be executed when the node to be deleted is the last node (i.e., when temp->next==nullptr) I'm wondering how safe it is to attempt to access temp->next->data.

And even if it's safe, is it a bad programming practice?

\$\endgroup\$
1
\$\begingroup\$
  • Too much indentation. Once the if clause returns, there is no reason for else.

  • The conditional

            if (temp->next == nullptr && temp->next->data != toBeRemoved)
    

    is buggy. When temp->next == nullptr, the predicate temp->next->data != toBeRemoved is evaluated, which dereferences a null pointer. You need || instead of &&.

    On the other hand, there is no need to test it at all: by the time you evaluate the mentioned conditional, you know for sure it is true.

  • DRY. A standard technique to avoid repetition is to temporarily prepend the list with a dummy node.

All that said, a recommended rewrite is

    bool remove(node * & head, int toBeRemoved)
    {
        node dummy;    // Notice that it is not a pointer.
        dummy->next = head;
        node * temp = &dummy;

        //seek for node
        while (temp->next != nullptr && temp->next->data != toBeRemoved)
            temp = temp->next;

        if (temp->next == nullptr) {
            return false;
        }
        node * removeThis = temp->next;
        if (removeThis == head) {
            head = removeThis->next;
        } else {
            temp->next = removeThis->next;
        }

        delete removeThis;
        return true;
    }
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ In C++ we have double-poiners, which avoid the need for allocating a temporary node (which might have a non-default-constructible or heavy data-member). See codereview.stackexchange.com/a/160770 \$\endgroup\$ – Deduplicator Apr 14 '17 at 15:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.