Corrupt pointer in a linked list

Question

How would you find if one of the pointers in a linked list is corrupted or not ?

Answer 1

There are several possibilities.

If the list is doubly linked, it's possible to check the back pointer from what a front pointer points to, or vice versa.

If you have some idea as to the range of expected memory addresses, you can check. This is particularly true of the linked list is allocated from a limited number of chunks of memory, rather than having each node allocated independently.

If the nodes have some recognizable data in them, you can run down the list and check for recognizable data.

This looks to me like one of those questions where the interviewer isn't expecting a snappy answer, but rather an analysis of the question including further questions from you.

Answer 2

Yuo could keep a doubly linked list. Then you can check that node->child->parent == node (although if node->child has become corrupt this has a reasonable chance of causing an exception)

Answer 3

Introduce a magic value in your node structures. Initialize it upon new node allocation. Before every access, check if the node structure that the pointer points to contains the valid magic. If the pointer points at an unreadable data block, your program will crash. For that, on Windows there's API VirtualQuery() - call that before reading, and make sure the pointer points at readable data.

Answer 4

It's sort of a pain, but you can record the values of each pointer as you come across them with your debugger and verify that it's consistent with what you'd expect to find (if you'd expect a pointer to be NULL, make sure it's NULL. if you'd expect a pointer to refer to an already existing object, verify that that object's address has that value, etc.).

Answer 5

Several debuggers / bound-checkers will do this for you, but a cheap and quick solution to this question is to

• Alter the structure of the list's nodes to include one additional char[n] field (or more typically two, one as the first the other as the last fields in the structure, hence allowing bounds-checking in addition to pointer corruption).
• Initiallize these fields with a short (but long enough...) constant string such as "VaL1D-LiST-NODE 1234" when the nodes are created.
• Check that the values read in this(these) field(s) match the expected text, each time a node is dereferenced, and before using the node in earnest.

When the field(s)' value do not match this is either the indication that:

• the pointer is invalid (it never pointed to a list node)
• something else is overwriting the node structure (the pointer is "valid" but the data it points to has been corrupted).