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

• Deduplicator: 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