EMC Interview Question
Software Engineer / Developerspublic bool remove(int key) //remove link with given key
{ //(assumes non-empty list)
Link pCurrent = pFirst; //search for link
Link pPrevious = pFirst;
while (pCurrent.iData != key)
{
if (pCurrent.pNext == null)
return false; //didn’t find it
else
{
pPrevious = pCurrent; //go to next link
pCurrent = pCurrent.pNext;
}
} //found it
if (pCurrent == pFirst) //if first link,
pFirst = pFirst.pNext; //change first
else //otherwise,
pPrevious.pNext = pCurrent.pNext; //bypass it
pCurrent = null; //delete link
return true; //successful removal
}
copy the content of the next node into the current node; release the memory of the next node; done
I thought he meant "terrific" solution.
What if the given node is last one in the list?
I thought he meant "terrific" solution.
What if the given node is last one in the list?
If the given node is other than last one then the solution by Syrus is absolutely fine....But if u r supposed to delete the last node then I think U cant delete that particular node because in one way list u can travel only in one direction(no back traversal is possible from a given node)....
good point~ so there is absolutely no way to delete the last node in this scenario huh?
What I don't understand is how you even start to search when all you are getting is some key and no starting or any node address. He says head node is not given, then how do your even traverse the entire list.
A node in a linked list is an object. So what is meant in this question is that one is given the object depicting the node to be deleted. And the object will have the data (key) and the pointer to the next node (object) in the linked list. So the solution given by syrus is correct if the current node is not the last node.
One modification that I can think of to go around this problem is to attach a dummy node at the end of the linked list. This way the node to be deleted can never be the last node. We just make the node to be deleted (if it's second last) the dummy node.
malloc allocates contiguous blocks of memory. so lets say our original list contains nodes: { a, b, c, d, e}. Since we dont know the head, we dont know where the list begins. now we're asked to delete node 'e' (lets say) i.e. we've been given the address of the node 'e'. now if e->next == NULL, we can be certain that 'e' is the last node to be deleted. In this case, we must fix the address pointed to by the node 'd'. But how do we reach node 'd' given node 'e'?
Since malloc allocates memory in continuous chunks, cant we reach node 'd' by doing a pointer arithmetic i.e. Address of node 'd' = Address of node 'e' - sizeof(struct node). Now we can reach node 'd' and fix its next pointer to point to NULL.
the same logic can be used for any node but the first. imagine if we have only 1 node in the list and we're asked to delete this node?
Idea is very well known and It can be done in Constant time ,Having One limitation(If last node is passed)..Please have the following code snippet..
void delete(struct node *x)
{
struct node *y=NULL;
y=x->next;
x->data=y->data;
x->next=y->next;
free(y);
}
If you find any mistake then please let us know.
1. With a single pointer in single linked list, only middle node can be deleted, the last node cant be deleted.
All the cases can be achieved under following conditions
a. either we need two pointers in single linked list
b. or possible if it is a double linked list
c. or if malloc ensures contiguous memory allocations for the nodes
Otherwise I don't any other ways to fix the problem.
If anybody knows the solution please let me know
- Pappu cant dance sala February 03, 2012