Delete all occurrences of an item in linked list

Question

This code takes an item as an argument and deletes all occurrences of the item in the linked list. It works well with my testing. Is there anything that I am missing? Can this code be improved further?

void
LinkedList::DeleteAllOccurences(int key) {
 Node *temp = head;
 Node *prev = head;
 while(temp!=NULL) {
 if(temp->item == key){
 if(temp == head) {
 head = temp->next;
 delete temp;
 temp = head;
 } else {
 prev->next = temp->next;
 delete temp;
 temp = prev->next;
 }
 } else {
 prev = temp;
 temp = temp->next;
 }
 }
 return;
}

• forsvarir: Your code is missing context. What does Node look like, what members does the LinkedList class have? How are Nodes created? Your previous question suggests that LinkedList has a tail member, which you're not addressing in the posted code. Without the context, we're left guessing.

Answer 1

Yes, your code can be improved by not handling the head as a special case. Yes, that means using a double-pointer, but the structure gets much more straight-forward and shorter:

void LinkedList::DeleteAllOccurences(int key) {
 Node** p = &head;
 while(*p)
 if((*p)->item == key) {
 Node* tmp = (*p)->next;
 delete *p;
 *p = tmp;
 } else
 p = &(*p)->next;
}

Answer 2

Another alternative to double pointers is using a dummy node that initially points to head, and after you are done with removing the items you restore the head in case its node got deleted:

void
LinkedList::DeleteAllOccurences(int key) {
 Node dummy;
 dummy.next = head;
 Node *node = &dummy;
 while (node->next != NULL) {
 if (node->next->item == key) {
 Node *temp = node->next;
 node->next = temp->next;
 delete temp;
 } else {
 node = node->next;
 }
 }
 head = dummy.next;
 return;
}