Delete node from Linked List

Question

I am working on iterative delete function that deletes node from a linked list, I think that the code is supposed to work fine, it traverses through the list, finds the needed node, points the head to the next node and deletes the current, but when I test run it I get infinite loop, could you please help me to pinpoint the error, here is the function:

typedef struct E_Type * List;
struct E_Type
{
  int data;
  struct E_Type* next;
};

the function:

 bool erase(List & l, int data){
 List head = l; 
 if (l != 0){
    for(List current = head; current; current = current->next){
    if ( current->data == data )
       head = current->next;
       delete current;
       return true;
     }
   }
 return false;
}

the test program:

int main()
{
  List l = 0;
  cout << boolalpha << l->data << "went well? "<< (insert(l,73)) << endl;
  cout << boolalpha << l->data << "went well? "<< (insert(l,24)) << endl;
  print(cout,l);
  cout << boolalpha << "Is deleted 24? "<<(erase(l,24)) << endl;    
  cout << boolalpha << "Is deleted 35? "<<(erase(l,35)) << endl;
  print(cout,l);
  cout << endl;
  return 0;
}

the insert:

bool insert(List & l, int data)
{   

    List current = l;
    while(current != 0) {
        if (current->data == data)
        return false;
       current = current->next;
    }

    if (l == 0 || l->data > data){
        List new_list = new E_Type;
        new_list->data = data;
        new_list->next = l;
        l = new_list;
    return true;
    }

    else if(l->data < data){
    insert(l->next, data);
    return true;
    }

}

I see no { after the second if statement in erase. That looks unintentional; you have multiple statements indented after it. Try enclosing those statements in braces. (There are still errors, but that looks like it'd be a big problem. Looks like it unconditionally deletes the first entry.) — cHao
– cHao, Commented Dec 12, 2012 at 13:31

Frerich Raabe · Accepted Answer · 2012-12-12 14:19:32Z

3

As Andreas Brinck already points out, you need to update the 'previous' link as well. However, you don't need a dedicated variable for this, just use a pointer to a pointer:

bool erase(List & l, int data){
  List *it = &l;
  while ( *it ) {
    if ( (*it)->data == data ) {
      List next = (*it)->next;
      delete *it;
      *it = next;
      return true;
     }
     it = &(*it)->next;
  }
  return false;
}

This also takes care of handling all the "special cases" such as deleting from an empty list, deleting the first element in the list or deleting the last element in the list.

edited Dec 12, 2012 at 14:19

answered Dec 12, 2012 at 13:49

Frerich Raabe

95.2k20 gold badges127 silver badges216 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

EmilDo Over a year ago

thanks a lot, the poiner solution is great and now i now how to easily refer to prev node in other functions.

Andreas Brinck · Accepted Answer · 2012-12-12 13:30:51Z

3

You need to keep track of the previous node as well in your for loop and do something like:

prev->next = current->next;
delete current;

You'll also need to handle the case where the deleted element is the first element of the list, in this case you need to set l to l->next

 bool erase(List & l, int data){
 if (l != 0){
    for(List current = head, prev = 0; current; prev = current, current = current->next){
    if ( current->data == data )
    {
       if (prev)
       {
           prev->next = current->next;
       }
       else
       {
            l = current->next;
       }
       delete current;
       return true;

     }
   }
 return false;
}

Your first erase is probably creating a circular list right now.

edited Dec 12, 2012 at 13:30

answered Dec 12, 2012 at 13:22

Andreas Brinck

52.9k15 gold badges87 silver badges114 bronze badges

7 Comments

EmilDo Over a year ago

How can I keep track of the previous node in this for loop, I also thought about that solution but have no idea how to implement prev node here.

cHao Over a year ago

Looks more like it's removing all the entries before the one being deleted. (Since it's not actually deleting them, though, it's leaking memory.)

EmilDo Over a year ago

Yes.. how could i miss that, i should close the if statement inside the loop

Andreas Brinck Over a year ago

@cHao Good catch, although it returns after deleting the first value.

EmilDo Over a year ago

yes it works now but deletes all the data before current, I will try with prev node now

|

cowls · Accepted Answer · 2012-12-12 13:17:28Z

0

We may need to see your insert method as well.

Is it possible that

current == current->next

If so that could cause the infinite loop.

answered Dec 12, 2012 at 13:17

cowls

24.4k9 gold badges51 silver badges78 bronze badges

Collectives™ on Stack Overflow

Delete node from Linked List

3 Answers 3

1 Comment

7 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

7 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related