Doubly-linked list infinite loop? [closed]

Question

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.

Closed 9 years ago.

If I were to create a node class, as shown below, and if it were used in a doubly-linked list, would it create an infinite loop upon deconstruction of the doubly linked list? Or would it terminate nicely?

class Node
{
    Node(  );

    ~Node(  )
    {
       delete mNext; //deallocs next node
    }

    Contact mContact;
    Node* mPrevious;
    Node* mNext;
}; 

Edit: If I modified the code to this would it work?

~Node(  )
{
   mPrevious = NULL;
   if (mNext->mPrevious != NULL)
   {
      delete mNext; //deallocs next node
   }
}

Edit 2: Or would this work best?

~Node(  )
{
   if (mPrevious != NULL)
   {
      mPrevious = NULL;
      delete mNext; //deallocs next node
   }
}

Answer 1

If considering the mNext pointer the nodes are forming a loop then then destruction of any of the nodes will indeed probably form an infinite recursive loop and it will terminate the program by blowing up the stack.

What it will probably happen is

1. The first "external" delete node; is issued.
2. When entering the node destructor nothing has been done yet as the code destructor is the "first" thing performed in the destruction process (the destruction process itself is quite involved and includes destructor code, class change, member destruction, base destruction in this order: see this answer for a more detailed explanation).
3. The first destructor instruction fill execute delete mNext; thus triggering the same process on next node in the loop.
4. Because the nodes are forming a loop this chain will reach node again "from the back" thus making the very first call a recursion that would never end.
5. Every call none the less will allocate stack space for the activation record, therefore after a while all the memory allowed to be used for the stack will be depleted and the OS will kill the process. The deletion call is not a "tail call" because after the destructor code completes the memory must be deallocated so this recursion cannot easily be optimized away... while delete mNext; is the last statement on the destructor still there are operations that must be performed after the delete operator completes.

Note however that in my experience a stack overflow unless you use special compiler options is not going to be checked and the program termination will therefore be quite "abnormal". Note also that under Windows there is some horrible code that in some cases hides segfault errors if they happen on program termination, so it's well possible that a windows program could just apparently terminate gracefully in this operaton is done after quitting the event loop.

Give that stack overlflow is not normally considered indeed any behavior is possible, including an apparent "infinite loop" (note that this infinite loop may be not the one of the recursive destructor but somewhere inside the runtime system getting crazy because of the stack overflow).

Why did I use the word probably? The reason is that the C++ standard says that multiple destruction of an object is Undefined Behavior. If you add this to the fact that there is no way in C++ to quit a destructor without completing the destruction you will understand that a compiler is in theory allowed to flag an object as "being destroyed" and to make a daemon fly out of your nosrils if you enter the destructor of the same object twice. Checking for this error is not mandatory however and compiler writers are often lazy (this is NOT an insult for a programmer) and therefore is unlikely that this check will be present (except may be if some special extra debugging option is enabled).

To sum it up: can it loop forever? yes. Can it crash? sure. Can it stop telling me that an object is being destroyed twice? of course. Can it just terminate the program nicely (i.e. witout setting any error code)? yes, that too.

Anything can happen. And Murphy says it will happen whatever is going to do the most damage to you... for example the program will terminate nicely every single time while you are developing it... and it will crash badly in you face during the demo day in front of a thousand prospective customers.

Just don't do that :-)

Answer 2

There is no way for it to know when to stop, so it probably will run infinitely.
You should probably write a List class, which has a pointer to a (or an actual) Node. Node's d'tor should only take care of its own fields, in this case mContact. List's d'tor should iterate over all nodes in the list (remembering when to stop), and delete each one (exactly once).

Answer 3

Assuming you initialize mNext to null, it will not run infinitely. Delete will do nothing when it encounters a null pointer. Thus it would end exactly when you expect it to.

I'm not sure what you are doing with the "if previous" options. Those won't work. Either this will be a valid node and thus have a previous node or it will not be a valid node and checking previous will have undefined results. Stick with the simple answer:

class Node 
{ 
Node(  mNext = NULL; ); 

~Node(  ) 
{ 
   delete mNext; //deallocs next node 
} 

Contact mContact; 
Node* mPrevious; 
Node* mNext; 
};  

Clarification: This solution works, but only if two conditions are met: 1) There are no nodes appearing in the list twice. 2) The list is not circular. If you can guarantee those conditions, this is your simplest answer. If you cannot, you need to do something more complex.

Answer 4

Personally, I think it's a bit odd that a Node's destructor should have anything to do with other nodes.

If the design was up to me, I would create a List class that contains a pointer to Node objects (first and last). The destructor of the List class would take care of iterating through all the nodes in the list and destroying them.

Answer 5

This is actually simple . Assumptions 1)Its a doubly link list and not a circular one 2)No Loops in the link list: this is a double link list 3)The implementation class has only one instance of Node Probably called HeadNode or LinkList ;) and this is the node that is destroyed explicitly

---

Example : LinkList are 1->2->3->4->5->6->NULL The distructor call for HeadNode(reffer 3rd assumption) will cause a recurssive call as follows: delete(1)->delete(2)->delete(3)->delete(4)->delete(5)->delete(6)->NULL So Please chech if (mNext != NULL) delete mNext and it works :)

---

But:If you want to delete a node specifically : Say we want to delete only 4 in above example ,all the nodes will be deleted till NULL so before deleation please ensure you set the Mnext to NULL.

---

The best practice would be to use the STL library or otherwise use autopointer class for the destruction part of the problem