Removing a node from a linked list

Question

I created a hash table and I want to remove the node from the linked list. The code works to remove the first node, but not to delete the others.

void intHashTable::remove(int num){ int location = ((unsigned)num) % size; Node * runner = table[location]; int checker; if(runner->next == NULL){ if(num == table[location]->num){ table[location] = NULL; } }else{ if(table[location]->num == num){ table[location] = table[location]->next; }else{ //This part doesn't seem to be working. Node *temp = runner->next; while(temp != NULL){ if(temp->num == num){ runner->next = temp->next; delete(temp); break; } } } } 

}

Answer 1

You have not updated temp to point to the next element of the loop:

 temp = temp->next; 

You also present an empty row with a NULL pointer in your table, but you do not handle this case correctly in your code - if runner is NULL , then you will break when you try to access runner->next in the first check. Also, in some cases, you cannot delete the node.

To fix these problems, you can update your code something like this:

 void intHashTable::remove(int num) { int location = ((unsigned)num) % size; Node * runner = table[location]; if (runner != NULL) { if (runner->num == num) { delete runner; table[location] = NULL; } else { while (runner->next != NULL) { if (runner->next->num == num) { Node *temp = runner->next; runner->next = runner->next->next; delete temp; break; } runner = runner->next; } } } } 

Also note that I removed the brackets from delete , which is a C ++ keyword, not a function.

If you use doubly linked lists (i.e. with the previous pointer, as well as the next), you can simplify this code a bit, although for something like a hash table where you only tend to scroll in one direction, it may not be worth the expense to an additional pointer (additional 8 bytes per element in a 64-bit system).

Answer 2

You have not updated the temp and runner variables inside the loop:

  while(temp != NULL) { if(temp->num == num) { runner->next = temp->next; delete temp; break; } runner = temp; // Keep previous element to change its next pointer when num found temp = temp->next; // Advance current pointer to next element }