Linked List Question
-
I'm thinking of how a linked list verifies whether a given node pointer points to a valid node in the list. For example, suppose we have a linked list which chains up 10000
NODE, the user calls one member functions which takes aNODE*as parameter:InsertBefore(const NODE* pBefore, LPVOID lpData), now how does the linked list verify ifpBeforepoints to a validNODEwhich is contained in the list? I think basically there would be 2 possibilities: Solution 1, Use::IsValidReadPtrand::IsValidWritePtrto check if the memory is available to current process and the consecutive memory block space are large enough to be read/written against a NODE object. Solution 2, Travel through the whole list and exampBeforewith address of eachNODE, stops whenever a match is found. Personally I think solution 2 is definitely a no go because that would make the linked list ultimately slow if it contains a larget amount of nodes. Solution 1 is faster but not safe, because that way we cannot really make sure ifpBeforereally points to aNODEor not, it could be any object whose size is same or greater than aNODEand if we use some iterating method likewhile (pNode->pNext != NULL) {...;}we'll get our system hang... So I really want to know how a linked list verify aNODE*, is there any better solution, thanks. -
I'm thinking of how a linked list verifies whether a given node pointer points to a valid node in the list. For example, suppose we have a linked list which chains up 10000
NODE, the user calls one member functions which takes aNODE*as parameter:InsertBefore(const NODE* pBefore, LPVOID lpData), now how does the linked list verify ifpBeforepoints to a validNODEwhich is contained in the list? I think basically there would be 2 possibilities: Solution 1, Use::IsValidReadPtrand::IsValidWritePtrto check if the memory is available to current process and the consecutive memory block space are large enough to be read/written against a NODE object. Solution 2, Travel through the whole list and exampBeforewith address of eachNODE, stops whenever a match is found. Personally I think solution 2 is definitely a no go because that would make the linked list ultimately slow if it contains a larget amount of nodes. Solution 1 is faster but not safe, because that way we cannot really make sure ifpBeforereally points to aNODEor not, it could be any object whose size is same or greater than aNODEand if we use some iterating method likewhile (pNode->pNext != NULL) {...;}we'll get our system hang... So I really want to know how a linked list verify aNODE*, is there any better solution, thanks.AFAIK, many linked lists use the "honor system"... that is, when you insert a node, it takes your word for it that it's a valid node. :) The STL linked list uses iterators for this purpose, which makes it less likely to err. You can still mess up if you pass in a list an iterator from a different list, though. If your nose runs and your feet smell, then you're built upside down.
-
I'm thinking of how a linked list verifies whether a given node pointer points to a valid node in the list. For example, suppose we have a linked list which chains up 10000
NODE, the user calls one member functions which takes aNODE*as parameter:InsertBefore(const NODE* pBefore, LPVOID lpData), now how does the linked list verify ifpBeforepoints to a validNODEwhich is contained in the list? I think basically there would be 2 possibilities: Solution 1, Use::IsValidReadPtrand::IsValidWritePtrto check if the memory is available to current process and the consecutive memory block space are large enough to be read/written against a NODE object. Solution 2, Travel through the whole list and exampBeforewith address of eachNODE, stops whenever a match is found. Personally I think solution 2 is definitely a no go because that would make the linked list ultimately slow if it contains a larget amount of nodes. Solution 1 is faster but not safe, because that way we cannot really make sure ifpBeforereally points to aNODEor not, it could be any object whose size is same or greater than aNODEand if we use some iterating method likewhile (pNode->pNext != NULL) {...;}we'll get our system hang... So I really want to know how a linked list verify aNODE*, is there any better solution, thanks.I don't think there is any way you could 100% guarantee that a node passed to one of the member functions was valid. However, you could add an extra member to the NODE that was a pointer back to the linked list. This would reduce the chances of a node being passed in from another list, but even that is still not a guarantee that it is valid. Dave http://www.cloudsofheaven.org