Like Tree3Likes

Writing a deconstructor for a linked list

This is a discussion on Writing a deconstructor for a linked list within the C++ Programming forums, part of the General Programming Boards category; HI i am trying to write a deconstructor for a linked list but it keeps giving me errors. Code: LinkedListCollection::~LinkedListCollection() ...

  1. #1
    Registered User
    Join Date
    Nov 2011
    Posts
    118

    Writing a deconstructor for a linked list

    HI i am trying to write a deconstructor for a linked list but it keeps giving me errors.
    Code:
    LinkedListCollection::~LinkedListCollection() {
        intListElement *current= this->head_;
        intListElement *next1=current;
        while(current!=0){
            next1->next=current->next;
            delete current;
            current = next1;
        }
    
    
    }

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,803
    Maybe...
    Code:
    LinkedListCollection::~LinkedListCollection() {
        intListElement *current= this->head_;
        intListElement *next1;
        while(current!=0){
            next1=current->next;
            delete current;
            current = next1;
        }
    }
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  3. #3
    Registered User
    Join Date
    Nov 2011
    Posts
    118
    Quote Originally Posted by hk_mp5kpdw View Post
    Maybe...
    Code:
    LinkedListCollection::~LinkedListCollection() {
        intListElement *current= this->head_;
        intListElement *next1;
        while(current!=0){
            next1=current->next;
            delete current;
            current = next1;
        }
    }
    Thanks.

  4. #4
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Also, it's called a destructor (or dtor), not a deconstructor.
    iMalc and laserlight like this.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  5. #5
    Registered User
    Join Date
    Jun 2005
    Posts
    6,433
    I wouldn't directly use a loop in the destructor at all. Doing that will delete some objects more than once (since operator delete invokes destructors as well) and that is undefined behaviour.

    Code:
    LinkedListCollection::~LinkedListCollection()
    {
        delete head_;
        delete next;
    }
    Since operator delete does nothing for a NULL pointer, this will effectively delete the list. All it requires is that head and next are pointers to objects created with operator new or NULL otherwise. And since operator delete invokes the destructor, this will recursively delete the whole list.

    I don't quite understand why every element in your linked list has a "head". That implies a tree structure, not a simple linked list.
    VirtualAce likes this.
    Right 98% of the time, and don't care about the other 3%.

  6. #6
    Registered User
    Join Date
    Nov 2011
    Posts
    118
    Quote Originally Posted by grumpy View Post
    I wouldn't directly use a loop in the destructor at all. Doing that will delete some objects more than once (since operator delete invokes destructors as well) and that is undefined behaviour.

    Code:
    LinkedListCollection::~LinkedListCollection()
    {
        delete head_;
        delete next;
    }
    Since operator delete does nothing for a NULL pointer, this will effectively delete the list. All it requires is that head and next are pointers to objects created with operator new or NULL otherwise. And since operator delete invokes the destructor, this will recursively delete the whole list.

    I don't quite understand why every element in your linked list has a "head". That implies a tree structure, not a simple linked list.
    every node in my linked list does not have a head.I just add my nodes at the beginning of the linked list

  7. #7
    Registered User
    Join Date
    Jun 2005
    Posts
    6,433
    Quote Originally Posted by sigur47 View Post
    every node in my linked list does not have a head.I just add my nodes at the beginning of the linked list
    If so, that doesn't change my point. It appears your design is not as clean as it might be.

    And lack of cleanliness in a design tends to mean it is harder to get right, harder to debug, and harder to clean up.
    Right 98% of the time, and don't care about the other 3%.

  8. #8
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Presumably LinkedListCollection has the head_ of type pointer-to-intListElement, and the intListElement type has the next pointer (and data). The full code hasn't been shown.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  9. #9
    Registered User
    Join Date
    Nov 2011
    Posts
    118
    Quote Originally Posted by grumpy View Post
    If so, that doesn't change my point. It appears your design is not as clean as it might be.

    And lack of cleanliness in a design tends to mean it is harder to get right, harder to debug, and harder to clean up.
    Your right ,in your opinion how would you prefer i implement it to make it cleaner

  10. #10
    Registered User
    Join Date
    Jun 2005
    Posts
    6,433
    Based on the information you have provided, I wouldn't have a clue. All I have, from information you have given, is reason to question the design.

    However, it appears you are using two types (LinkedListCollection and intListElement) to, collectively, represent a linked list - LinkedList collection contains the head, and intListElement manages links going down from the head.

    Why can't that be done using a single class? Why doesn't intListElement have a destructor that, if invoked, deletes next? And, if it does, what does LinkedListCollection do that intListElement (with suitable renaming) could not?
    Right 98% of the time, and don't care about the other 3%.

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Quote Originally Posted by grumpy View Post
    I wouldn't directly use a loop in the destructor at all. Doing that will delete some objects more than once (since operator delete invokes destructors as well) and that is undefined behaviour.

    Code:
    LinkedListCollection::~LinkedListCollection()
    {
        delete head_;
        delete next;
    }
    Since operator delete does nothing for a NULL pointer, this will effectively delete the list. All it requires is that head and next are pointers to objects created with operator new or NULL otherwise. And since operator delete invokes the destructor, this will recursively delete the whole list.

    I don't quite understand why every element in your linked list has a "head". That implies a tree structure, not a simple linked list.
    Whilst I very much always respect grumpy's advice, (probably more than just about anyone else's here in fact), I thoroughly despise using recursion to perform linked-list deletion.
    **cough** "stack overflow"
    "Tail-recursion elimination optimisation" I hear you say...
    "Debug build" you'll hear me reply...

    If you want my advice here, definitely use recursion for any problem that involves O(log n) deep recursive calls, or maybe even O(sqrt n).
    BUT, don't use it for O(n) deep recursive calls!

    You may want to double check the code posted because nothing in it suggests that every element in the linked-list has a head. There are two classes involved, LinkedListCollection and intListElement, not just one.
    Edit: Oh you noticed that in a later post. Alright, I now have no idea where you are coming from. How is hk_mp5kpdw's corrected code any different to something the likes of std::list?
    Last edited by iMalc; 01-26-2012 at 12:29 AM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    Registered User
    Join Date
    Jun 2005
    Posts
    6,433
    Quote Originally Posted by iMalc View Post
    Whilst I very much always respect grumpy's advice, (probably more than just about anyone else's here in fact), I thoroughly despise using recursion to perform linked-list deletion.
    **cough** "stack overflow"
    "Tail-recursion elimination optimisation" I hear you say...
    "Debug build" you'll hear me reply...
    The tail recursion optimisation is often, in practice, performed by compilers even in the debug build ..... particularly by C++ compilers, because a lot of code (such as destructor calls) is recursive. It is a reasonably simple optimisation for a compiler, and also not something that can be readily detected in an IDE or debugger (you will always have the illusion of executing a line again and again if you step through).
    Right 98% of the time, and don't care about the other 3%.

  13. #13
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Tail recursion aside, in a linked list, the linked list object is the master, and node objects should be a small internal implementation detail. Having the node destructor delete its successor is, IMO, the wrong approach. In fact, having the node be anything but a simple struct without any member functions is probably the wrong approach. All the work should be done in the actual linked list class.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  14. #14
    C++まいる!Cをこわせ! Elysia's Avatar
    Join Date
    Oct 2007
    Posts
    22,781
    Though I am not sure if I agree on that a node must be a struct and no more, deleting the next pointer in a node destructor seems silly. Why would deleting a node delete the next? It often happens that we must rearrange nodes, and insert and removes references, hence this makes no sense. A node is a separate object.
    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.

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,308
    Yeah now you mention it, the other feeling I have about this is that you should never have to do more work to make less happen. Where the deletion is done recursively, if you want to delete a single item from the middle of the list you are forced to NULL the next pointer before deleting that node.
    That to me, goes against the principles of C++ where you only pay for what you use.

    At the same time, the simplicity and elegance of the recursive delete means it does have its place somewhere.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. single linked list to double linked list (help)
    By Countfog in forum C Programming
    Replies: 8
    Last Post: 04-29-2008, 08:04 PM
  2. Must I always use a deconstructor?
    By markcls in forum C++ Programming
    Replies: 22
    Last Post: 03-25-2007, 03:57 PM
  3. is Recursion ok in a deconstructor?
    By Syneris in forum C++ Programming
    Replies: 14
    Last Post: 01-03-2006, 10:58 PM
  4. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 05:37 PM
  5. Replies: 6
    Last Post: 03-02-2005, 01:45 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21