Thread: How does this code destruct the linked list class?

In the book Jumping Into C++, chapter 25, (page 360-370) we have these codes as examples:

Code:

class LinkedList
{ 
   public: 
           LinkedList (); // constructor
          ~LinkedList (); // destructor, notice the tilde (~) 
          void insert (int val); // adds a node
    private: 
             LinkedListNode *_p_head;
 };

class LinkedListNode
{ 
     public:
           ~LinkedListNode ();
             int val;
             LinkedListNode *p_next;
};

LinkedListNode::~LinkedListNode ()
{
         delete p_next;
}

LinkedList::~LinkedList ()
{
         delete _p_head;
}

In the book it says following:

Believe it or not, this code initiates a chain of recursive function calls. What happens is that the call to delete invokes the destructor for the object pointed to by p_next (or does nothing, if p_next is NULL). That destructor, in turn, calls delete and invokes the next destructor. But what’s the base
case? How will this chain of destruction end? Eventually p_next will be NULL, and at that point, the call to delete will do nothing. So there is a base case — it just happens to be hidden inside the call todelete. Once we have this destructor for LinkedListNode, the destructor for the LinkedList itself simply needs to invoke it:

Code:

LinkedList::~LinkedList () 
{ 
         delete _p_head; 
}

This call to delete starts the recursive chain, until the end of the list

I didn't understand the bolded text (I have bolded it). How this recursion deletes the nodes in the list, if what it does when calling delete is to just invoke the next constructor?

Does it just call the next and next constructor until it reaches NULL wtihout deleting the nodes?

Won't this code just "walk through" the nodes in the linked list without deleting any of them?

But, if the delete invokes the destructor of the object the pointer points to and destroys that object, then it will also destroy the data and pointer in the object too, since the object is destroyed. Then how does it find the next object in the linked list which were pointed by the pointer in the destroyed object?

I mean
node A
( data + pointer to node B)
node B ( data + pointer to node C)

When node A is destroyed, then the pointer to node B is removed too. And since there's no pointer to node B, how does it reach node B?

Originally Posted by CppProgrammer88

But, if the delete invokes the destructor of the object the pointer points to and destroys that object,

True, the order of execution is what makes this work. In pseudo code, delete would look something like

Code:

  //InVar is the variable that holds the p_next pointer.
  inVar->~LinkedListNode ();// this one execute delete p_next, until it returns, invar is not yet destroyed.
  free(invar);

Do you see the recursion?

Huh, I know you're not supposed to use a linked list for a large number of elements (when comparing it to other containers) but I think it's odd that the destruction of a container would be recursive. Especially when C++ is a language that's used to handle relatively large amounts of data and is also one that encourages separation of algorithm implementation from container type. I only say that because of `std::iterator_traits`. Container-agnostic algorithms are a pillar of the STL and its algorithm header in particular.

You should be iteratively destructing your list to avoid the ever so dreaded and famous stack overflow.

Edit:

It's terrible actual code but it's amazing educational material though. If you didn't understand destructors before, you will now.