Deleting any Node from a linked list
Author
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
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;}
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.
Author
Quote:Original post by Marmin
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.
i can delete the last, but the node pointing to last should be the last node after deleting.
Quote:Original post by mikbalQuote:Original post by Marmin
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.
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.
Author
Quote:Original post by CmpDevQuote:Original post by mikbalQuote:Original post by Marmin
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.
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
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.
Hope that Help,
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,
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.
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.
Quote:Original post by mikbalIn 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.
it has many extreme cases to deal with
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.
Maybe this will help:
http://www.gamedev.net/community/forums/topic.asp?topic_id=208775&whichpage=1�
http://www.gamedev.net/community/forums/topic.asp?topic_id=208775&whichpage=1�
Quote:Original post by mikbalQuote:Original post by Marmin
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
