#1
  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. #2
  3. 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
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2003
    Posts
    55
    Rep Power
    12
    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.
  6. #4
  7. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,624
    Rep Power
    4247
    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 :)
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  8. #5
  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


    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
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2003
    Posts
    55
    Rep Power
    12
    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.
  12. #7
  13. 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
  14. #8
  15. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2002
    Posts
    272
    Rep Power
    19
    and it's not doubly linked and it's not circular?
  16. #9
  17. 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
  18. #10
  19. No Profile Picture
    Dinesh_P_V
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2003
    Location
    India
    Posts
    259
    Rep Power
    0

    Answer to my puzzle


    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.
  20. #11
  21. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2003
    Posts
    55
    Rep Power
    12
    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.
  22. #12
  23. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Aug 2002
    Posts
    272
    Rep Power
    19
    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.

IMN logo majestic logo threadwatch logo seochat tools logo