How is the recursive call to destructor made in linked list?

Question

I was going through this blog post and came across this code.

#include <iostream>
#include <string>

using namespace std;

struct LNode {
   int data;
   LNode* next;

   LNode(int n){data = n; next = nullptr;}

   void add_to_end(int n) {
      if (next)
         next->add_to_end(n);
      else
         next = new LNode(n);
   }
   ~LNode() { cout << " I am from LNode Destructor " << endl; delete next; }
};

int main()
{   
   LNode root(1);
   root.add_to_end(2);
   root.add_to_end(3);
   root.add_to_end(4);

}

The output of this code is

 I am from LNode Destructor 
 I am from LNode Destructor 
 I am from LNode Destructor 
 I am from LNode Destructor 

For some reason I always thought I had to traverse through the linked list using some kind of while or for loop and go on deleting all the nodes that I had dynamically allocated using new. But in above code how did the destructor got called four times and how did it automatically traverse through the linked list creating this domino effect (completely deleting the allocated memory by itself ).

Answer 1

This code:

~LNode() { delete next; } // destructor

If next is set to 0, NULL or nullptr nothing will happen. However if it is set to the address of the following LNode it will cause the following LNode's destructor to run. Its destructor will do the same thing causing its following LNode to be destroyed and so on until you encounter a next variable that equals nullptr.

Answer 2

It's basically a chain.

Starting from the root node (which is the one who loses the ambit, and therefore, its deconstructor is called automatically), when calling delete next;, you are calling the deconstructor of the next element, and so on. When next is NULL, 0 or nullptr, the process will stop.

You can also add indexes to the nodes, and see by yourself the destruction order.

Answer 3

delete and destructor call are two subtly different things. But each time you delete (non NULL) pointer to LNode it's destructor is called.

See this question for details: Does delete call the destructor?

Destructor of root instance is called when it goes out of scope at the end of main():

int main()
{   
   LNode root(1);
   root.add_to_end(2);
   root.add_to_end(3);
   root.add_to_end(4);
/* Destructor of root is called here. Imagine this is present here: */
   root.~LNode(); // calling destructor on object root
}

~LNode destructor calls delete next; which in turns calls destructor of that object which in turn... The whole recursion is stopped when delete next; is called on NULL pointer which does nothing (definitely not calling any destructor).

Your callstack when the last destructor is called will look like this:

root.~LNode()
delete root.next
root.next.~LNode()
delete root.next->next
root.next->next->~LNode()
delete root.next->next->next
root.next->next->next->~LNode()

and then delete next; is actually called on NULL and recursion stops.

Answer 4

how did the destructor got called four times and how did it automatically traverse through the linked list

This is a common form of recursion.

---

A linked list is a recursive data structure.

I thought you might be interested in seeing a few more examples of recursion in a (home built and simple) single linked list.

---

Here is the ctor (simplified). The parameter a_max specifies how many node elements to create.

LMBM::Node::Node(uint8_t a_max) :
   m_nodeId            (++M_nodeCount),
   m_next              (0), // linked list
   //... other node initializers items
{
   if(a_max > 1)
   {
      uint8_t nmax = static_cast<uint8_t>(a_max - 1);
      m_next = new Node(nmax); // recurse create another Node
      dtbAssert(m_next)(a_max); // confirm 
   }
   else // (1 >= a_max)
   {
      dtbAssert(1 == a_max)(a_max); // at least one node
      // all requested nodes created
   }

   if (1 == m_nodeId) //i.e. the 1st node
   {
      M_firstNode   = this;   // capture list anchor to static
      M_MAX_THREADS = a_max;  // capture list size to static

      // ...  a few more actions
   }

} // LMBM::Node::Node(uint8_t a_max)

The above is extracted from running code, but I now consider this code not suitable to ship because when new fails (for any reason) the code asserts. While my dtbAssert provides debugger support, it is not suitable for client use.

Yes, there are no loops here.

Perhaps when you get used to it, the simplicity and ease of use are typical of recursion.

The ctor extends the list with simple new (typically discouraged by many of your peers who prefer a smart pointer).

Each node gets assigned a unique m_node_id to aid debug.

The invocation to create this list is simply:

LMBM::Node nodes(LMBM::Node::DEFAULT_MAX_NODES);

Code in main (with limit checks) can pass in a user value for larger or smaller lists.

---

The dtor is much like from your blog finding (though in reversed sequence)

LMBM::Node::~Node(void)
{
   if(m_next) // delete objects and list
      delete m_next; // recurse down the list

   // ... clean up actions, if any 

   m_nodeId = 0;

} // Node::~Node(void)

This dtor first spins to the end of the list, then while unwinding the stack does cleanup and delete activity.

---

This init() method initializes some resources (semaphores, etc.), again, using recursion, and completing the last node's init() first.

void LMBM::Node::init(void)
{
   if(m_next)
      m_next->init(); // tail first

   // 1. ALLOCATE resource, such as a semaphore
   m_semIn = new Sem_t; // create 1 semaphore per thread
   dtbAssert(m_semIn)(m_nodeId);

   //std::cout << "m_semIn " << m_nodeId << " = " << (void*)m_semIn << "\n";

   // 2. INITIALIZE default Sem_t ctor is ok

} // void LMBM::Node::init(void)

(No loops here, either.)

FYI - LMBM::Sem_t has 4 lines of C++ code, and via the Linux API wraps a single Posix Process Semaphore, set to local mode (unnamed, unshared).

It turns out that this Posix semaphore does work with std::threads as well as posix threads - one of the things I was testing here.

---

Here is startApp(). I won't show much more than the recursion used... in the example from which I snapshot this code, a thread performs each node's activities.

void LMBM::Node::startApp(void)   // activate threads
{
   if(m_next)
      m_next->startApp(); // recurse to end of linked list

   // 4. start my thread
   m_thread = new std::thread (LMBM::Node::threadEntry, this);
   dtbAssert(m_thread);

   // ... confirm thread running state

} // void LMBM::Node::startApp(void)   // activate threads

All the threads cooperate in one way or another.

---

At this point, I have N nodes; each node has a thread; and what the thread does can be determined by m_node_id; and debugger cout's can be augmented with thread id's that are of 1..10 nature instead of the system id's.

Answer 5

A tiny clarification: The delete next; call causes the destructor to be called on the nodes from first to last - but the actual storage reclamation occurs from last to first. I.e, this is the sequence:

 1) destructor invoked on node 1.
 2)   delete called with pointer to node 2.
 3)   destructor invoked on node 2.
 4)     delete called with pointer to node 3.
 5)     destructor invoked on node 3.
 6)       delete called with pointer to node 4.
 7)       destructor invoked on node 4.
 8)         delete called with nullptr.
 9)       destructor call at (7) reclaims node 4 and returns.
10)     destructor call at (5) reclaims node 3 and returns.
11)   destructor call at (3) reclaims node 2 and returns.
12) destructor call at (1) reclaims node 1 and returns.