Deleting any Node from a linked list

This topic is 3566 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Hi, I should write a fuction that can delete a specific node. Node has a integer key value to be spotted. We dont know this node is the first, last or in the middle. First and middle cases are easy but i cant figure anything to delete the last node. Here is my node; private: string name; int value; Node *next; i am allowed just to have a next pointer, no prev pointer. and i cant use counter to determine the lenght of linked list either. it seem like i need to write a function to get previous node of a given node. then do some tricks to delete the last one Do you have any idea to do that? Thank you

Share on other sites
When you delete a node from a singly linked list, you need to update the pointer which points to that node (regardless of whether it's the first, middle or last node). Therefore, that pointer should be passed by reference to your deletion function, and thus:

void delete_node(Node *&n){  Node *t = n;  n = t -> next;  delete t;}

Share on other sites
Hi, deleting a last node is easy, just test if the pointer to the next is Nil , and then delete the one you're testing.

Share on other sites
Quote:
 Original post by MarminHi, deleting a last node is easy, just test if the pointer to the next is Nil , and then delete the one you're testing.

i can delete the last, but the node pointing to last should be the last node after deleting.

Share on other sites
Quote:
Original post by mikbal
Quote:
 Original post by MarminHi, deleting a last node is easy, just test if the pointer to the next is Nil , and then delete the one you're testing.

i can delete the last, but the node pointing to last should be the last node after deleting.

Come on, this is homework and your tutor has already given you the theory of how to complete this.

Share on other sites
Quote:
Original post by CmpDev
Quote:
Original post by mikbal
Quote:
 Original post by MarminHi, deleting a last node is easy, just test if the pointer to the next is Nil , and then delete the one you're testing.

i can delete the last, but the node pointing to last should be the last node after deleting.

Come on, this is homework and your tutor has already given you the theory of how to complete this.

:)
yes it is a homework, and sadly it has many limitations.( like no counters allowed)
i figured out everything except the last node. it has many extreme cases to deal with

Share on other sites
To delete a node from a link list, that isn't the last node means you need, the nodes to keep track of the Node before it in the list.

class Node_c{Node_c *Next;Node_c *Last;Node_c *RemoveMe();   {   if (Next != NULL)      {      Next->Last = Last;      }   if (Last != NULL)      {      Last->Next = Next;      }   Last = NULL; // Clear Link   Next = NULL; // Clear Link   return(this); // Return Pointer to Node to be Deleted   }}// Create Nodes A<->B<->CNode_c A, B, C;A.Next = &B;A.Last = NULL;B.Next = &C;B.Last = &A;C.Next = NULL;C.Last = &B;// No To Remove B from theNode_c *T = B.RemoveMe(); // Removes B from Link list and keeps a pointer to Node so can be deleted if dynamically allocated.

Hope that Help,

Share on other sites
As ThoorVyk has already mentionend, the actual deletion always need to update the pointer referring to the node which will be deleted. This is true regardless of where the node is located in the list. In practice, one needs to store also a pointer to the first node (the "list head"), so even deleting the first node needs a pointer to be updated.

Quote:
 Original post by mikbalit has many extreme cases to deal with
In fact, it has no special cases if using ThoorVyk's solution. Otherwise, if going the non-reference way, it has just a single special case, namely the one of the head node.

The solution of ThoorVyk works well for all cases (if the programming language of interest supports references). However, it relies on the fact that the predecessor node or the list head pointer, resp., is given. So make sure to remember that referring pointer when iterating the list on looking up the node for deletion. And as Marmin has mentioned, its easy to detect when the end of list is reached.

Share on other sites
Maybe this will help:
http://www.gamedev.net/community/forums/topic.asp?topic_id=208775&whichpage=1�

Share on other sites
Quote:
Original post by mikbal
Quote:
 Original post by MarminHi, deleting a last node is easy, just test if the pointer to the next is Nil , and then delete the one you're testing.

i can delete the last, but the node pointing to last should be the last node after deleting.

When you delete a node other than the last, it was pointing to the next node (because there is a next node, because it wasn't last). So you make the previous node point to the next one. You do that by following what ToohrVyk said: pass in the previous node's pointer, by reference.

When you delete the last node, it is pointing to NULL. What you want to do is make the previous node point to NULL, because it will become the new "last node". But that means you can just do the same thing: copy the current next-pointer into the previous node's next-pointer. So you don't have to make any special check.

This is actually a very common result in computer programming. Zero values and null pointers are not such special cases as people think they are.

Share on other sites

This topic is 3566 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Create an account

Register a new account

• Forum Statistics

• Total Topics
628645
• Total Posts
2984020

• 9
• 9
• 10
• 21
• 20