Data structure: Singly linked list

[linux_help]

I have been asked a question in the data structure to remove any random node (only its address is known) using singly linked list.

For ex: Here is the linked list

A-->B-->C-->D-->E-->F---(null)

Suppose, address of C node is given. Remove this node without breaking the linked list. List will look like this after removal

A-->B-->D-->E-->F---(null)

Please let me know what is the logic for this?

[ahoodin]

You want to set the *next of B to D before you set *next of C to NULL and delete the node.

HTH,

[linux_help]

Here you know only the address of C. How will you get the address of B (with the help of address of C) to point to D? If possible, please give the code snippet also.

[ahoodin]

Well you can always transverse the list to find it.

[linux_help]

Traversing the list will be easy by using two pointers and delete the appropriate node. But, here you know only the address of the node which is going to be deleted. With the help of the address of node C, we have to delete node C and link node B and D. Do you know solution for this?

[ahoodin]

Well in other problems like this, we usually keep a current pointer and sometimes even a last pointer. Without gathering additional data like that it makes it kind of iffy. :D If it were a doubly linked list, we would have a previous pointer.

[MrViggy]

Traversing the list will be easy by using two pointers and delete the appropriate node. But, here you know only the address of the node which is going to be deleted. With the help of the address of node C, we have to delete node C and link node B and D. Do you know solution for this?
If you only know the address of 'C' then you cannot link node B to D. How could you without a pointer to B? B could be anywhere in the address space.

Viggy

[charansingh]

there is one tricky way to do this..

A-->B-->C-->D-->E-->F---(null)

Now, in this list we have the address of C which has to be deleted.

We can copy the next node to the current node and then delete the next node.

Step 1: Copy the next node contents to the current node

A-->B-->D-->D-->E-->F---(null) // copy contents of D to C

Step 2:

A-->B-->D-->E-->F---(null) // now delete one copy of D, the original one


So we have deleted the node C, but internally we just have deleted its next node :)

[ProgramThis]

Nice solution charansingh :thumb:

That actually should sever his purpuse perfectly. However, he must do a deep copy and not a shallow copy. Otherwise this will not work. What I mean is that you have to clone D and place the contents of D into the memory space of C, otherwise you are just pointing C -- > D and B will still point at where C should be.

I may have not explained that very clearly, basically I am not convinced that you can just place D in the memory address of C without doing a little work. But the algorithm for the solution (i.e. the idea of shifting D) is elegent enough.