Question: You are given a pointer to a node (not the tail node) in a singly linked list. Delete that node from the linked list. Write code in C.
Answer: To delete a node, you have to redirect the next pointer of the previous node to point to the next node instead of the current one. Since we don’t have a pointer to the previous node, we can’t redirect its next pointer. So what do we do?
We can easily get away by moving the data from the next node into the current node and then deleting the next node. This solution has O(1) runtime. Here’s some code to illustrate this simple logic.
void deleteNode( Node * node )
{
Node * temp = node->next;
node->data = node->next->data;
node->next = temp->next;
free(temp);
}
Some things to consider. This method could pose potential problems. For instance, let’s consider we have a linked list A -> B -> C -> D and we are given a pointer to B to delete it. Theoretically, you would expect B to be deleted and all pointers which were pointing to B to become invalid. However, if we use this function to delete B, all pointers which were pointing to B will still be valid. Furthermore, node B now will contain the value C and node C will be invalid. Any previous pointers to C will become invalid, which may not be expected behavior in general. This is not a problem if there are no external links to any of the items in the linked list. But this would definitely be something you should consider asking your interviewer to show your thinking process.
Simple enough? Try more linked list questions.
If you have any questions, please feel free to send me an email at [email protected]. If you have any interview questions which you feel would benefit others, I would love to hear about it.
If you're looking for some serious preparation for your interviews, I'd recommend this book written by a lead Google interviewer. It has 189 programming questions and solutions:
Helpful Tip: If deleting a char/string node, you need to replace the second line of the function (ie. node->data = node->next->data;) with “strcpy(node->data, node->next->data);”
Thanks for good explanation. I was thinking of temp node is not required. But for freeing the deleted node we need temp node. By reading this post I came to know this.
So what if I want to delete the tail node. Should I just do a free(node).
Thanks for the explanation but just to simplify
1. First make the node to be deleted to point the next node.
2. Copy the content of the next node in to the node that has to be deleted.
3. Assign the next pointer of the newly copied node to the next pointer of the node from which the content has been copied.
4. Delete the node from which the data has copied.
Code Example:
A->B->C->D, we want to delete B as above steps say:
Next = B->link; // assign B to point to next node
B->data = Next->data; // copy the data from next node to B data.
B->link = Next->link;//make B to point to the node after Next.
Free (Next); // now delete the Next node, becz its content is there in B. and the content of B is overwritten.
i.e. The effective deletion was the data content in B by overwriting it.
or:
Next = B->link;
AfterNext = Next->link;
B->data = Next->data;
B->link = AfterNext;
free(Next);
You can not do that without being given a pointer to a node before or head.
how to delete last node from a singly link list ?
Is there a way to remove the tail also in O(1) and without using pointer to prev in addition to the pointer to next ?
Copy the data from the node to be deleted to its next node and delete the node. This works provided 1) the node to be deleted is not the last and 2) we can copy the data
Temp can not be null since the node being sent in is not the tail node. It states in the question that the node can not be the tail node.
flunked : temp could be NULL