C++ linked list

Question

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?

Answer 1

• 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;
    }