1
\$\begingroup\$

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;
}
\$\endgroup\$
1
  • 2
    \$\begingroup\$ 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. \$\endgroup\$
    – forsvarir
    Nov 24, 2016 at 13:21

2 Answers 2

1
\$\begingroup\$

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;
}
\$\endgroup\$
0
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.