CODEWITHSUNDEEP
c++linked-list
Ahsan Asif
Ahsan Asif

Reputation: 31

deletion in linked list

This is my deletion code. The problem is that when i delete something from the tail or an nth node it works perfectly fine but whenever i delete something from the head it crashes. What check should i make in order to avoid the crash?

void List::Delete(int data) {
// Create a temp pointer
Node *tmp = head;

// No nodes
if ( tmp == NULL )
return;

// Last node of the list
if ( tmp->Next() == NULL ) {
delete tmp;
head = NULL;
}
else {
// Parse through the nodes
Node *prev;
do {
    if ( tmp->Data() == data ) break;
    prev = tmp;
    tmp = tmp->Next();
} while ( tmp != NULL );

// Adjust the pointers
prev->SetNext(tmp->Next());

// Delete the current node
delete tmp;
}

}

Upvotes: 0

Views: 61

Answers (2)

Ahmed Akhtar
Ahmed Akhtar

Reputation: 1463

There are more than one problems with this code.

  • if ( tmp->Next() == NULL ) this check does not mean "Last node of the list" infact it means that there is only one node in the list since the code below only runs if there are at least two nodes you need to handle this case here.
  • tmp->Data() == data check is needed in addition to the above check to make sure that the only node in the list is also the node we want to delete before deleting it.
  • Node *prev = NULL; this pointer should be initialized so that we can check for NULL later to see if it is the head that needs to be deleted.
  • Also all the deletion should be done inside the loop checking for if ( tmp->Data() == data ) before the break; is applied, otherwise you will have no way to know if the loop ended naturally or was broken, to decide whether the node was found or not.

Here is the corrected code:

void List::Delete(int data) {
 // Create a temp pointer
 Node *tmp = head;

 // No nodes
 if ( tmp == NULL )
 return;

 // it is the only node in the list
 if ( tmp->Next() == NULL && tmp->Data() == data ) {
  delete tmp;
  head = NULL;
 }
 else {
  // Parse through the nodes
  Node *prev = NULL;
  do {
      if ( tmp->Data() == data ){
       if( prev == NULL ) // this is the head case
        head = head->Next();
       else // Adjust the pointers
        prev->SetNext(tmp->Next());
       // Delete the current node
       delete tmp;
       break;
      }
      prev = tmp;
      tmp = tmp->Next();
  } while ( tmp != NULL );
 }
}

Note: The tail case works fine without any alterations in the code because, the only difference that this case creates, is that tmp->Next() for that case would be NULL which is exactly what we want for the new tail in prev->SetNext(tmp->Next()); i.e. set its Next to NULL.

Upvotes: 0

therainmaker
therainmaker

Reputation: 4343

If the node to delete is the head node, then this is what happens:

You declare Node *prev. Notice that it is uninitialised. Then you enter the do while loop, but break at the first if condition because tmp->Data() == data. So you exit the do while loop without executing the next statement, which would initialise prev. Now out of the loop, the next statement accesses the SetNext field of prev, whereas previous is unitialised. This is undefined behavior, and anything can happen; crashing is one such thing.

The way to avoid this is to add a check for whether prev is unitialised, or 'tmp' is the head node. In this case, you should delete the head, and return the node after head. Since your function has a void signature, you should delete the head node, and make the head pointer reference the node after head.

Upvotes: 1

Related Questions