Removing the first occurrence of a generic element x in a node-based linked list.

removefirstocc.cpp

//assume we're looking for x.

bool found = false;
Node* temp = head, rm = NULL;

//now we loop through our list looking for a node that holds something == to x
while(temp != null && !found) {
  if(temp->data == x) { //if we find it, set found to true and rm to the node
    found = true;
    rm = temp;
  }
  else //otherwise just skip ahead to the next node
    temp = temp->next; 
}

//if we didn't find anything, we're done.
if(!found)
  return;

//if we passed the last if-statement, then we definitely found something so rm is definitely not null
//so we assume our linked list looks like this: [a] [rm] [b]
Node* a = rm->prev;
Node* b = rm->next;

//since we approached from the left, [a] cannot be null, so...
//we go ahead and "unhook" rm from a
a->next = b;

//if b was null, and rm was at the end, a now equals null. Which is how it's supposed to be.

//but if b is null, we shouldn't try to unhook rm from it. 

//So we check it...
if(b != NULL) { //if it definitely exists...
  //unhook rm from it
  b->prev = a;
}

//Now that it's safely unhooked, we can delete rm.
delete rm;

//now we're done!