How can I delete a node from the middle of a C++ queue?

Question

I have a linked list with a c-style ctor and dtor.

I just got too frustrated when this if statement decided not to test true, putting me in an infinite loop. I dont understand why it will never test true.

I am trying to delete a node (the address of a class object) from my LinkedList.

Maybe someone could help me out?

Node *Current = first_; // I want this to be my only Node Ptr Varaible Declaration.
if ( NULL == first_ )
std::cout << "Cannot delete from an empty list: \n";


while ( Current != NULL )
{
  if ( first_->data_ == node->data_ ) 
  {
    //check to see if we are deleteing the head.
    first_ = first_->next_;
    --listLen_;
    delete Current;
    std::cout << "Head Deleted!\n";
  }
  if ( Current->data_ == node->data_ ) // FOR SOME REASON this is never true?
  {
    --listLen_;
    node->data_ = NULL;
    Current  = Current->next_;
    node->data_ = Current;
  }
  else  // we must not of found it.  // else should match previous i
  {
    Current->prev_ = Current;// since we are not deleting the first node we are OK here.
    Current     = first_->next_;

    if ( Current->next_ == NULL ) // see if we are at the end of the list.
    {
      first_ = NULL;  
      last_  = Current->prev_;

    }
  }
}
return;

Answer 1

You don't show where node comes from or how data_ is defined, but if it is a pointer type, you probably need to compare the contents, not the addresses.

Assuming that data_ is a pointer to something and what it points to has operator== defined or is a built in type and it has the value you are looking for then you can do this instead:

if ( *Current->data_ == *node->data_ )

Answer 2

This should really be rewritten, since it has too many problems...also why not use a STL container? I assume this is a homework question.

The answer to the infinite loop is the else case that increments to the next node:

Current        = first_->next_;

This will make you loop forever if the data is not found in in the first two nodes...since you will set the next test to the first's next node always and it will never set the current to NULL provided there are more than 2 nodes in the list.

Answer 3

if first_->data_ == node->data_ ever evaluates to true then the second if statement will always evaluates to true then the second if condition will always evaluate to false Current->data_ == node->data_ because on the first iteration first_ == Current and you delete Current without ever updating it

To delete a node from a linked list you seem to be doing way too much work.

Answer 4

I'm not entirely sure what you're trying to accomplish, but I'm certain you're doing it wrong. If you're merely trying to remove an element from a doubly-linked list that matches node->data_, it's as easy as this:

Node *Current = first_;

while (Current != NULL)
{
  if (Current->data_ == node->_data)
  {
    //If Current isn't the head of the list, set prev to next
    if (Current != first_)
      Current->prev_->next_ = Current->next_
    else
    {
      first_ = Current->next_;
      if (first_ != NULL)
        first_->prev_ = NULL;
    }

    //If Current isn't the tail of the list, set next to prev
    if (Current->next_ != NULL)
      Current->next_->prev_ = Current->prev_
    else if (Current->prev_ != NULL)
      Current->prev_->next_ = NULL;


    delete Current;
    Current = NULL;
  }
  else
  {
    Current = Current->next_;
  }
}
return;

Answer 5

Not really an answer here for the actual question but a suggestion.

I would never iterate through a linked list to delete an entry in the list. Each entry should have a valid next and previous pointer and when you go to delete an entry from the list you just make the previous record point to the next one and vice versa to remove yourself from the list. An empty list should have a head record and a tail record that just point to each other and all valid entries are inserted in between.

Answer 6

Keep your loops small, it easier to figure out what went wrong. Assuming your data compare makes sense, look at this the following:

curr = first_;
while( curr && (curr->data_ != node->data_) ) { 
  curr = curr->next_; 
}
if (!curr) return   // didnt find it, nothing to remove
if ( curr == first_ )   
  first_ = curr->next_  
else      
  curr->prev_->next_ = curr->next_
curr->next_->prev_ = curr->prev_ // always fix next's prev
delete curr