deleting an item in cicular linked list

Question

My program is supposed to do 3 operations:

Insert
Delete
Show on a circular linked list.

My problem is in the delete function. here is the code:

void c_list::del()
{
    int num;
    if(isempty())
        cout<<"List is Empty!"<<endl;
    else
    {
        node *temp1=first;
        node *temp2=NULL;
        cout<<"Enter the number that u want to DELETE:"<<endl;
        cin>>num;
        while(temp1->next!=first && temp1->info != num)
        {
            temp2=temp1;
            temp1=temp1->next;
        }
        if(num != temp1->info )
            cout<<"your number was not found in the list"<<endl;
        else
        {
            if(temp2!=NULL)
            {
                temp2->next=temp1->next;
                cout<<temp1->info<<" was deleted"<<endl;        
            }
            else
            {
                first=temp1->next;
                cout<<temp1->info<<"was deleted"<<endl;
            }
        }
    }
    system("pause");
}

Delete function is working in this way: user enters a number, the program searches that number & when it founds the number, removes it from the list.

Now the problem is that, when the user enters a number that does not exist in the list, the "App crash window" appears(I mean this window:Program is not responding), while I have a provided an error message for this case("your number was not found in the list")!!

Can u tell me what the problem is?

Why do you have same condition for both while loop and if statement (`temp1->info != num` ) ? If that is **false**, then you won't even execute the statements of `if`. — Mahesh, Dec 13 '13 at 17:31
Are you sure your data structure is correct and you eventually reach `first` again? — Christopher Creutzig, Dec 13 '13 at 17:32
@ChristopherCreutzig I think so! I can put the insert() function if u want — Little Girl, Dec 13 '13 at 17:37
@LittleGirl A circular linked list should never crash if properly populated. If the deletion doesn't work, then it might just be a logical mistake. Please post the insert function. — Mahesh, Dec 13 '13 at 17:38
You could insert something like `std::cerr << temp1 << std::endl;` inside your while loop and check if you spot a loop there that does not include `first`. (Using small datasets for debugging is obvious, I guess.) — Christopher Creutzig, Dec 13 '13 at 17:39
I'd suggest considering what happens when the first item in the list matches you number. If it's true that this is a circular list then that case is clearly wrong. If it's not a circular list then your exit condition in the while is wrong. — Speed8ump, Dec 13 '13 at 17:49
@Speed8ump why???? I think it's correct! test it by one or 2 example :| — Little Girl, Dec 13 '13 at 17:54
consider what happens on the first entry. first == NULL. what in the next pointer of the new item set to? — Speed8ump, Dec 13 '13 at 17:54
when I enter and element for the first time, I create a node whose next part points to the first element, then I check whether there is an element in the list or not, if there isn't, the element that I entered would be the first & it's next part will point to itself! Oh should I update the next? — Little Girl, Dec 13 '13 at 17:58

score 0 · Answer 1 · edited May 23 '17 at 12:19

0

Happen that, if you insert a number that is not in list, you have a loop in the first while.

So:

node* temp1 = first;
node* temp2 = 0; 
while(temp1->next!=first && !temp2) {
  if(temp1->info == num) {
     /* save pointer and exit from while */
     temp2 = temp1;
  } else {
    temp1 = temp1->next;
  }
}

Then your code produce garbage because you never call a delete.

Most likely the problem is on the insert method, where maybe, you don't assign correcly pointers.

And then, why system("pause"); ? Take a look here.

edited May 23 '17 at 12:19

Community

1
1

answered Dec 13 '13 at 17:36

Luca Davanzo

21,000
15
120
146

That is probably better code, but logically equivalent, afaics. Apart from the place where the succeeding code cannot work with your change, because `temp1` points to the wrong element. – Christopher Creutzig Dec 13 '13 at 17:41

score 0 · Answer 2 · answered Dec 13 '13 at 17:44

0

I think in your while loop you are reaching to the end of list and after below line temp1 gets NULL.

temp1=temp1->next;

Then you are trying to read info attribute from null pointer and this causes error.

if(num != temp1->info )

I know you said it is circular list but i am not sure it is implemented correctly or not. My suggestion is just try to print temp1->info after while loop to be sure that correctness of list and your implementation.

answered Dec 13 '13 at 17:44

Validus Oculus

2,756
1
25
34

I added the insert code, take a look at it and tell me whether it's right or not. tnx – Little Girl Dec 13 '13 at 17:51
i dont see your insert function, where is it ? – Validus Oculus Dec 14 '13 at 04:07

score 0 · Accepted Answer · answered Dec 13 '13 at 18:02

0

Your insert routine is not creating a circular list. When the list is empty and the initial item is inserted first == NULL. In this case your code leaves the list in a non-circular state. Because:

    newitem->next=first;
    if(first==NULL)
        first=newitem;

At this point first->next == NULL, which should never be the case in a circular list. Your search code fails whenever the item to be found does not exist in the list. This is because it never cycles back around to the first node, since the list is not circular.

answered Dec 13 '13 at 18:02

Speed8ump

1,307
10
25

yes u r right! if I delete newitem->next=first; before if & change if to this: if(first==NULL){ first=newitem; newitem->next=first;} would it be correct? – Little Girl Dec 13 '13 at 18:07
That probably fixes insert. Your delete routine has other issues. Try deleting the first item from the list and see what happens Once you fix that, then try deleting the last item from the list. Also, I'm letting it slide that you never call delete() on the items you are removing. – Speed8ump Dec 13 '13 at 18:12
well another question is that: now that I have changed the insert, my display function is not working correctly... what should I write in the while loop of function display() ? I wrote while(temp->next != first) but it doesn't show the last member of the list – Little Girl Dec 13 '13 at 18:26

deleting an item in cicular linked list

3 Answers3