Thread: Just a puzzle. How to delete a node given its address

1. No Profile Picture
Dinesh_P_V
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2003
Location
India
Posts
259
Rep Power
0

Just a puzzle. How to delete a node given its address

Hello folks,
This is just a puzzle for you to solve.
Consider a linearly linked list and you are given only the address of the node to be deleted(the start node address is not given). How can we achieve it ?

-Murugesan
2. No Profile Picture
Dinesh_P_V
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2003
Location
India
Posts
259
Rep Power
0

Re: Just a puzzle. How to delete a node given its address

>>This probably isn't exactly want you want
obviously
I asked about the situation where the field-S in a node is known and the memory has been allocated using malloc.

-Murugesan
3. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2003
Posts
55
Rep Power
15
I just posted then deleted an example, the reason i deleted is because I didn't think it was really suitable to assume the linked list is linear in memory, the whole point in linked lists is to allow non-linear data storage.

"where the field-S in a node is known", no, you did not point this out in your first post.
And you didn't state it would be allocated with malloc.

The example I gave didn't use malloc, but this hasn't got anything to do with it, the fact is i assumed linear storage as you said.
Last edited by xtor; September 8th, 2003 at 01:09 PM.
4. There is one way to do it, if you are using DOS. Promise not to laugh at this :). There was an undocumented DOS call, that allowed you to iterate through the memory blocks (it also told you which process ID allocated the block). So, you could iterate through the memory blocks and find the particular block that is pointing to your node.

After this, it is just a matter of pointing the previous block to the next node and deleting your node. Note that this technique will only work in DOS (and maybe not in the newer versions). Frankly, it's probably easier to use a doubly linked list --- more portable and faster as well :)
5. No Profile Picture
Dinesh_P_V
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2003
Location
India
Posts
259
Rep Power
0

Just a puzzle. How to delete a node given its address

No no no.
There is a method through which it is possible to remove the node in what ever OS it may be.
I will tell it tomorrow evening. It is late night here.
-Murugesan
6. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2003
Posts
55
Rep Power
15
I don't believe this at all. You will have to be assuming that no other memory blocks in your address space have the value of the node's address.
Even if each node contained the address of the head & the tail, you would be assuming memory is contiguous.
7. No Profile Picture
Dinesh_P_V
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2003
Location
India
Posts
259
Rep Power
0

Just a puzzle. How to delete a node given its address

I know the purpose of linked list. I am not assuming that the memory in linked list is continous as in the case of array

-Murugesan
8. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2002
Posts
272
Rep Power
22
and it's not doubly linked and it's not circular?
9. No Profile Picture
Dinesh_P_V
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2003
Location
India
Posts
259
Rep Power
0

Just a puzzle. How to delete a node given its address

Yes it is LINEARLY LINKED LIST not a doubly linked list not a circular one ....

-Murugesan
10. No Profile Picture
Dinesh_P_V
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2003
Location
India
Posts
259
Rep Power
0

Here is the answer to my puzzle

node * curr,*tmp;
curr=nodetobedeleted;
if(curr==NULL)
return;
curr->data=curr->next->data;
tmp=curr->next;
curr->next=curr->next->next;
if(tmp!=NULL)
delete tmp;

I thought that u might have got the logic. But you have compiled the program and reported the errors

-Murugesan
Last edited by murugesan; September 9th, 2003 at 07:13 AM.
11. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2003
Posts
55
Rep Power
15
That's stupid, you don't even check if curr->next exists, what if it's the tail? You don't even initialize tmp, so how can you access data it points to (then points to again)?

ALSO, most people would agree that it is better to only work with the pointers to the node to delete it, not exchange it's data.

Waste of time.
Last edited by xtor; September 9th, 2003 at 07:06 AM.
12. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Aug 2002
Posts
272
Rep Power
22
It certainly wasn't made clear that we knew more than the address of the node. You should state your problem a bit more clearly the next time.