I have a question about deleting nodes of a linked list.
I'm basically doing it like this:
while(!end_reached)//some loop control function here
start=start->forward();//this a function I know works
I'm trying to delete intermediate nodes without reconnecting the two halves of the resulting list (because one of these halves will be deleted later; my application requires it).
I don't get this to work properly. After a lot of experimenting I discovered that the nodes that are deleted need to be disconnected from all other nodes by making sure that they don't point to any other nodes and they are not pointed to by any other nodes. This means all these nodes have to point to NULL. However, this doesn't make much sense to me. Why would a node need to be disconnected before deleting it? Is it because that the program gets confused if some nodes (even though they are never visited by the program) point to something that no longer exists.
No matter what I disconnect, I still have a hard time getting this deletion to work. Above I gave you a simplified version of my code. My data structure is actually of a grid type. If I visualize my data structure, it would be a table. All nodes in the top row have two pointers: forward and left. All the rows below the bottom row only have forward pointers (the left pointer is set to NULL). I drew you this diagram of my data structure:
D <- C <- B <- A <- start
| | | |
ˇ ˇ ˇ ˇ
H G F E
| | | |
ˇ ˇ ˇ ˇ
L K J I
Maybe I'm having problems because the grid is complicated. My goal is simply to delete the grid above. I've been trying to delete this grid one colulmn at a time. Using the above example, I delete in this order: A, E, I, B, F, J ... and I just cannot get it to work without crashing. There is something tricky about handling the pointers that I cannot figure out.
Do you have any quick ideas as to what I could try?
It sounds like what's happening is you have cross- or multiple-links. When you delete one, the other pointer is still pointing to a deleted node. If above you want to delete C, C has to outgoing pointers, both of which have to be fixed before deleting C.
Pictures like above help a lot. Write a function to print the tree as best you can. You may find who's got bad pointers.
Sorry this is very helpful, and late too - I've been very busy.