Delete a node from a list by a given criteria

[budala]

Hello there. I have a linked list, wherein every node has a name, age and a unique ID number. I want to delete a node which has the desired ID number. The problem is that maybe the ID number I want to delete isn't in the list yet.

Now, I can solve this with a helper function which first checks if a node with the desired ID exists, then if it does it returns the predecessor of that node or NULL if it doesn't. But I would like to do it without that helper function.

Can you help me?

[Spidey]

Well, you don't really need a need a helper function. All you have to do is start at the head of the list and loop till you reach the node with the desired ID or the end of the list. Throughout this loop you can maintain a previous pointer which is always one step behind the loop. After your loop has finished, you can check the loop counter variable. If it points to the node with the desired ID, then delete it. If it points to the end of the list, just return without deleting any value.

[budala]

Ok, this is my first attempt using your logic. And of course it doesn't work

void Delete(person **head)
{
	person *temp = *head;
	person *p, *q;
	int ID;
	
	printf("Enter the ID of the person you want to remove : ");
	scanf("%d",&ID);
	
        /*ID's start from 1 */
	if (ID < 1) printf("Wrong ID!!");
	else
	{
		if (temp == NULL) printf("List is empty! Nobody to remove!!");
		else
		{		
			while (temp->ID != ID || temp != NULL)
			{
				p = temp;
				temp = temp->next;
			}
			
			q= p->next;
			if (q == NULL) printf("Wrong ID!!");
			else
			{
				if (q->ID == ID) 
				{
					p->next = q->next;
					free(q);
				}
			}
		}
	}
}

[Spidey]

What kind of error are you getting ?

Also, I would suggest to take the scanf out of the function ad pass the ID to be removed into the delete function. You could also create a wrapper function which passes in the head of the list.
Also, you should have a special case if there is only one item in the list, i.e the head.

[BEN10]

Ok, this is my first attempt using your logic. And of course it doesn't work

void Delete(person **head)
{
	person *temp = *head;
	person *p, *q;
	int ID;
	
	printf("Enter the ID of the person you want to remove : ");
	scanf("%d",&ID);
	
        /*ID's start from 1 */
	if (ID < 1) printf("Wrong ID!!");
	else
	{
		if (temp == NULL) printf("List is empty! Nobody to remove!!");
		else
		{		
			while (temp->ID != ID || temp != NULL)
			{
				p = temp;
				temp = temp->next;
			}
			
			q= p->next;
			if (q == NULL) printf("Wrong ID!!");
			else
			{
				if (q->ID == ID) 
				{
					p->next = q->next;
					free(q);
				}
			}
		}
	}
}

I think there is no need to create an extra variable q, coz q=p->next will always be same as temp(i.e q==temp) after the while loop finishes. Else looks fine with the delete function.

[budala]

What kind of error are you getting ?

Also, I would suggest to take the scanf out of the function ad pass the ID to be removed into the delete function. You could also create a wrapper function which passes in the head of the list.
Also, you should have a special case if there is only one item in the list, i.e the head.

no error, the program just ends, and in Xcode the line

while (temp->mb != mb || temp != NULL)

is highlighted

why should i take out the scanf out? any specific reason?

ok, i'll try a special case for a single node in a list.

wrapper function??? explain please

I think there is no need to create an extra variable q, coz q=p->next will always be same as temp(i.e q==temp) after the while loop finishes. Else looks fine with the delete function.

ah, silly me q == temp

[Brafil]

I would revise that condition. It's not entirely meaningful.

I think Spidey means moving scanf outside the function.

[roaan]

The best advice i can give you is to take a pencil, a paper and draw out three nodes having all the information that you want. See if all the situations (found an id, only single node, id not present, deleting a node) work out with your current code and then modify it. This was the advice i got from one of the forum members and it really works out well (rather excellently). If unable to solve it yet then post it.

Anyhow let us proceed with what you have been doing till now. You have come till here.

[insert]

while (temp->ID != ID || temp != NULL)
			{
				p = temp;
				temp = temp->next;
			}

What can happen next? temp is a pointer to the current node and p is a pointer to the previous node. So this is good till now.

If i reach the end of the list without finding the id i was looking for i shoudl return back without modifying the existing linked list

So ill do something like this.

[insert]

  if(temp == NULL)

   return;

What happens if i have come out of that while loop and temp != NULL. It implies that i have a node with the relevant id i was looking for. So i need to delete this and set the pointer of the p(the previous node) to the next one. Right

So ill do something like this after the above if condition

[insert]

else if(temp ->id == id)
{
    p->next = temp->next;
    free(temp);
}

Thats it . Is there any other case which needs to be handled. I dont think so. This should solve the problem. And you dont need the q as BEN10 pointed out.

[roaan]

I hope this attachment ( a file given by one of the members in this forum ) to handle these problems would be good and a lot easier.

[BEN10]

Yeah. I always try problems using pen-paper, specially when it's related to manipulating a list.

[Kennedy]

This is backwards:

while (temp->ID != ID || temp != NULL)

and can cause a segfault (keeping in mind that conditions in C short circuit).

[roaan]

What kind of error are you getting ?

Also, I would suggest to take the scanf out of the function ad pass the ID to be removed into the delete function. You could also create a wrapper function which passes in the head of the list.
Also, you should have a special case if there is only one item in the list, i.e the head.

How do we use the wrapper function here ?

[Spidey]

Aah, well basically a wrapper function is used to abstract out the implementation specific parameters of a data structure. For example, the delete function in the list above always takes in the head of the list. But the user of the list doesnt really care about that, all he/she cares about is deleting the person with that particular ID So instead of directly passing in the head node to the delete function you can create a wrapper function which accepts the ID, which calls the proper delete function and passes in the node. This is mostly just a convenience function so that anyone else using the code does not have to pass in the each time.

eg :

void Delete(int ID)
{
    DeleteNode(head,ID);
}

[roaan]

Aah, well basically a wrapper function is used to abstract out the implementation specific parameters of a data structure. For example, the delete function in the list above always takes in the head of the list. But the user of the list doesnt really care about that, all he/she cares about is deleting the person with that particular ID So instead of directly passing in the head node to the delete function you can create a wrapper function which accepts the ID, which calls the proper delete function and passes in the node. This is mostly just a convenience function so that anyone else using the code does not have to pass in the each time.

eg :

void Delete(int ID)
{
    DeleteNode(head,ID);
}

Okay i get the point. But isnt this redundant then ? Or i am missing the point here because eventually the deletenode function in the wrapper function is doing just that.

[Spidey]

Well, if you mean passing in the head then yes, but only if your talking about the head being accessible from inside the function meaning it is global. In which case you wouldn't even need the wrapper and simply pass in the ID. But most times, it is necessary to pass in the head so it would be useful then.