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

  1. #1
    Registered User
    Join Date
    Apr 2016
    Posts
    6

    Question 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?

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,312
    Quote Originally Posted by CppProgrammer88
    Does it just call the next and next constructor until it reaches NULL wtihout deleting the nodes?
    No, the delete invokes the destructor of the object that the pointer points to, hence destroying that object. Thus, every node will be destroyed.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Apr 2016
    Posts
    6
    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?

  4. #4
    Registered User
    Join Date
    Oct 2006
    Posts
    3,445
    Quote Originally Posted by CppProgrammer88 View Post
    then it will also destroy the data and pointer in the object too, since the object is destroyed.
    All class member objects are considered in-scope and valid until the destructor returns.
    What can this strange device be?
    When I touch it, it gives forth a sound
    It's got wires that vibrate and give music
    What can this thing be that I found?

  5. #5
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,312
    Quote Originally Posted by CppProgrammer88
    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?
    The pointer to node B is only destroyed afterwards. Let's take a look at the destructor for a node:
    Code:
    LinkedListNode::~LinkedListNode()
    {
        delete p_next;
    }
    As you can see, you can validly refer to p_next within the body of the destructor. Therefore, it stands to reason that while the destruction of the LinkedListNode object has started, its members have not been destroyed yet, otherwise delete p_next must be invalid since p_next no longer exists.

    I recommend that you add print statements to observe this clearly:
    Code:
    LinkedListNode::~LinkedListNode()
    {
        std::cout << "destructor for LinkedListNode @ " << this << " has started" << std::endl;
        delete p_next;
        std::cout << "destructor for LinkedListNode @ " << this << " is about to end" << std::endl;
    }
    You will see a sequence of lines of output with "destructor ... has started", and then "destructor ... is about to end" in reverse order of appearance.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  6. #6
    Registered User taazz's Avatar
    Join Date
    May 2016
    Posts
    50
    Quote Originally Posted by CppProgrammer88 View Post
    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?

  7. #7
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    2,665
    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.

  8. #8
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    The memory is freed only after the destructor is called. So LinkedList's destructor calls the first LinkedListNode's destructor, which calls the destructor on the object pointed to by its next member which is also a LinkedListNode. And so it continues until it finds a next member that's null. Then the recursion stops and every object is destroyed. Try laserlight's example and you'll see the recursion calls. Only AFTER the destructor has finished running will the memory be freed, so the pointer contents is safe.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Splitting in a linked list class
    By FloatingButter in forum C++ Programming
    Replies: 14
    Last Post: 03-17-2013, 08:59 AM
  2. Linked list of a class object?....
    By chadsxe in forum C++ Programming
    Replies: 6
    Last Post: 12-08-2005, 03:15 PM
  3. Basic Linked List class
    By ExCoder01 in forum C++ Programming
    Replies: 3
    Last Post: 09-14-2003, 02:15 AM
  4. traversing a linked list with a node and list class
    By brianptodd in forum C++ Programming
    Replies: 2
    Last Post: 04-24-2003, 11:57 AM
  5. STL Linked List of class within class
    By NixPhoeni in forum C++ Programming
    Replies: 3
    Last Post: 11-30-2001, 10:17 AM

Tags for this Thread