Thread: linked list

    #1
  1. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2003
    Posts
    1
    Rep Power
    0

    linked list


    how can i delete a node in a single link list, if i know the address of that node(only) i.e to be deleted and i dont know the address of root node.

    how can i find in a double linked list, if the pointer is missing.means, the pointer is not pointing to the next node and it may point to some other double linked list also.so i have to find out which node's pointer is missing
  2. #2
  3. *bounce*
    Devshed Novice (500 - 999 posts)

    Join Date
    Jan 2002
    Location
    Delft, The Netherlands
    Posts
    514
    Rep Power
    42
    how can i delete a node in a single link list, if i know the address of that node(only) i.e to be deleted and i dont know the address of root node.
    You can't. You need both addresses; the address of the node to delete, and the address of any of the preceding nodes. There's no other way, period.

    how can i find in a double linked list, if the pointer is missing.means, the pointer is not pointing to the next node and it may point to some other double linked list also.so i have to find out which node's pointer is missing
    Pointers are never "missing". They either contain an address, or they are NULL. That means, if you're looking at a pointer's value, you can't tell if which linked list it points to. To put it simple: the only thing you can determine from a pointer's value is if it's pointing somewhere, or not (NULL). It does not convey any type information at all.

    Sorry :)
    "A poor programmer is he who blames his tools."
    http://analyser.oli.tudelft.nl/
  4. #3
  5. not a fan of fascism (n00b)
    Devshed Frequenter (2500 - 2999 posts)

    Join Date
    Feb 2003
    Location
    ct
    Posts
    2,756
    Rep Power
    95
    "how can i delete a node in a single link list, if i know the address of that node(only) i.e to be deleted and i dont know the address of root node."

    - i was thinking of maybe a hack way to do it. if u can determine the size of the node, then u know how many bytes in memory it occupies. and i believe nodes in a list are all stored sequentially in memory, so u could offset the pointer to the node to get pointers to the nodes in front/back of it.
  6. #4
  7. *bounce*
    Devshed Novice (500 - 999 posts)

    Join Date
    Jan 2002
    Location
    Delft, The Netherlands
    Posts
    514
    Rep Power
    42
    ...I believe nodes in a list are all stored sequentially in memory...
    No. You're thinking of elements in an array. With linked lists the following scenario is possible:

    • allocate memory for a node and add it to the list
    • allocate more memory from the heap for other data structures
    • allocate another node and add it to the list


    In the above scenario, the chance of the two nodes being adjecent in memory is well-nigh nil.
    "A poor programmer is he who blames his tools."
    http://analyser.oli.tudelft.nl/
  8. #5
  9. Contributing User
    Devshed Supreme Being (6500+ posts)

    Join Date
    Jan 2003
    Location
    USA
    Posts
    7,254
    Rep Power
    2222
    Stupid question:
    How could any functioning program find itself in the situation of not knowing the address of the root node of a linked list that it had created?

    I don't understand how the situation ysd4477 is trying to solve could ever arise unless the program has a bug in it. In that case, the solution is to correct the code and recompile.
  10. #6
  11. *bounce*
    Devshed Novice (500 - 999 posts)

    Join Date
    Jan 2002
    Location
    Delft, The Netherlands
    Posts
    514
    Rep Power
    42
    I don't understand how the situation ysd4477 is trying to solve could ever arise unless the program has a bug in it.
    It's not a stupid question; it's a valid point :)

    Code:
    void add_node_to_list (Node *ptr) {
       ???
    }
    That's an example of ysd4477's description, and yes, it's either an implementation or design flaw.

    In that case, the solution is to correct the code and recompile.
    Sounds like sound advice to me :)
    "A poor programmer is he who blames his tools."
    http://analyser.oli.tudelft.nl/
  12. #7
  13. not a fan of fascism (n00b)
    Devshed Frequenter (2500 - 2999 posts)

    Join Date
    Feb 2003
    Location
    ct
    Posts
    2,756
    Rep Power
    95
    yea i just figured out that wasnt possible... went to try it, and realized that you attach nodes on the fly
  14. #8
  15. No Profile Picture
    Junior Member
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2003
    Posts
    18
    Rep Power
    0
    how can i delete a node in a single link list, if i know the address of that node(only) i.e to be deleted and i dont know the address of root node.
    If the last item of your single linked list is not NULL (which is the standard way) but points to the first item of the linked list, there is a way in calculating the pointer to the item before the item to be deleted. Then you have a chance.

IMN logo majestic logo threadwatch logo seochat tools logo