I''m having a serious problem with my linked lists. A node in my list looks like this: typedef struct NODE { //some data struct NODE* parent; } Now I have an array that looks like this: NODE* nodearray[MAX_NODE_NUM]; Some of the nodes in this list can have the same parent, so nodearray[1]->parent and nodearray[2]->parent could be pointing to the same node. I allocate space for the nodes in nodearray at run time, so if the array has 3 nodes then nodearray[0], nodearray[1] and nodearray[2] have been allocated and the rest are NULL pointers, the number of nodes in the list is stored in a var lets call it node_num. Now here is my problem: in the program new nodes are inserted and deleted all the time. I know how to add new nodes but I don''t have clue how to delete em since some of the nodes shares the same parents. Note that two nodes only share the same parent if they are spawned from the same node. Here is the way new nodes are added. You take the top node (if node_num is 4 then this is nodearray[3], ok?),lets call this node A, then you "delete" A and replace it by let us say B and C. the array changes like this: {...,A} to {...,B,C} now B and C has A as parent. (A is still in memory, but it is not in the nodearray). How do I for example delete B. When deleting it I also want to delete all of of its parents, in this case the problem is that the parent A is shared by C. The problem gets even larger when B and C spawns new nodes themself. Can somebody help me with this? If anybody is wondering, this is for an A* algorithm. ------- Me Hardguy. and here is my game...

If I have understood you correctly, basically what you are looking for is a fast way to make sure that you can delete a parent node..

First of all though, you are not using a linked list. If you were to arrange your format as a linked list, it wouldn''t be in an array, but that is besides the point .

So, because you presented your problem using an array, we''ll solve it using an array. Basically, what we can do here is instead of making the children keep track of everything, we will add a variable to the node, called numChildren. This numChildren variable will be incremented when a child is created and decremented when a child is deleted. And when the variable hits zero, you know that it is safe to destroy the parent. So the delete function can be recursive sort of like this:

    void Delete(NODE* deadNode){  if (numChildren==0)  {    parent->numChildren--;    Delete(parent);    /* Kill it here */  } else  {    /* You still have children nodes here (app specific) */  }}    

PreManDrake

Thanks for the reply...

I think that it will work...

-------
Me Hardguy.
and here is my game...