f



Stack Overflow

All right, now here's a hard one:

I was making a class which implements a linked list, and I need it to have a
destructor (for obvious reasons). Unfortunately, if there's too many items
in the linked list, I get a stack overflow (because the destructor is
recursive, as you will see in a minute). Anyone see a way around this?

(Simplified Example)

class LinkedList
{
public:
     LinkedList *next;
     LinkedList *prev;
     int value;
     LinkedList();
     ~LinkedList();
};

LinkedList::LinkedList()
{
     next = prev = NULL;
}

LinkedList::~LinkedList()
{
     if (next!=NULL)
         delete next;

     prev->next = NULL;
}

This destructor ensures that if the first element is deleted, none of the
later elements will be "lost to the void." Is there any other destructor you
guys can see that isn't recursive and ensures that memory leaks won't occur?

Thanks for any help
-- MiniDisc_2k2


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]
0
MiniDisc_2k2
6/28/2003 12:45:24 PM
comp.lang.c++.moderated 10738 articles. 1 followers. allnor (8509) is leader. Post Follow

7 Replies
746 Views

Similar Articles

[PageSpeed] 40


MiniDisc_2k2 schrieb:

> All right, now here's a hard one:
>
> I was making a class which implements a linked list, and I need it to have a
> destructor (for obvious reasons). Unfortunately, if there's too many items
> in the linked list, I get a stack overflow (because the destructor is
> recursive, as you will see in a minute). Anyone see a way around this?

The answer is very, very simple:

just use std::list<int>.

If you are not familiar with the standard containers, I strongly suggest you to
study them.


regards,

Thomas

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]
0
Thomas
6/28/2003 11:26:10 PM
MattDelB@nospam.com (MiniDisc_2k2) wrote (abridged):
> LinkedList::~LinkedList()
> {
>      if (next!=NULL)
>          delete next;
> 
>      prev->next = NULL;
> }
> 
> This destructor ensures that if the first element is deleted,
> none of the later elements will be "lost to the void." Is there
> any other destructor you guys can see that isn't recursive and
> ensures that memory leaks won't occur?

You can keep the recursion to 1 level by removing nodes from the
list before deleting:

    LinkedList::~LinkedList() {
        while (next != NULL) {
            LinkedList *nextNext = next->next;
            next->next = NULL;
            delete next;
            next = nextNext;
        }
        prev->next = NULL;
    }

But is this what you want to do anyway? Perhaps deleting a node
should not delete all the following ones, but merely unhook itself?

    LinkedList::~LinkedList() {
        if (next != NULL)
            next->prev = prev;
        if (prev != NULL)
            prev->next = next;
    }

Now the following nodes will not be "list to the void". They'll
still be in the list.

-- Dave Harris, Nottingham, UK

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]
0
brangdon
6/28/2003 11:27:49 PM
MiniDisc_2k2 wrote:

> All right, now here's a hard one:
> 
> I was making a class which implements a linked list, and I need it to
have a
> destructor (for obvious reasons). Unfortunately, if there's too many
items
> in the linked list, I get a stack overflow (because the destructor is
> recursive, as you will see in a minute). Anyone see a way around this?
> 
> (Simplified Example)
<snip>
> 
> LinkedList::~LinkedList()
> {
>      if (next!=NULL)
>          delete next;
> 
>      prev->next = NULL;
> }

You forgot to test prev before you assign to it.

This method will truncate the list at the item you're deleting.  While 
there may be advantages to doing so, wouldn't it be better to just 
delete the item and leave the list otherwise intact?  You can still 
write a Truncate() method to do the above (or a non-broken version of 
the above at least :>) when needed.

Try this instead:

LinkedList::~LinkedList()
{
   if (next)
     next->prev = prev;
   if (prev)
     prev->next = next;
}

// delete all items after this in list
void LinkedList::Truncate()
{
   if (!next)
     return;
LinkedList* work = next;
   while (work->next)
     work = work->next;

   while (work != this)
   {
   LinkedList* temp = work->prev;
     delete work;
     work = temp;
   }
// NB: this->next will be cleared by destructor above
}

This is more normal for a linked list implementation I think.

-- 
Corey Murtagh
The Electric Monk
"Quidquid latine dictum sit, altum viditur!"


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]
0
Corey
6/29/2003 12:04:06 AM
MiniDisc_2k2 wrote:

> LinkedList::~LinkedList()
> {
>      if (next!=NULL)
>          delete next;
>
>      prev->next = NULL;
> }

Well, write an iterative one (but see my notes below):

LinkedList::~LinkedList()
{
  LinkedList *current = next,*keep;

  while(current) {
        keep = current->next;
        current->next = NULL;
        delete current;
        current = keep;
  }
}

Will recurse at most once per loop because it unlinks the elements
before they get deleted.

However: Do you think your design is sane? The problem here is that you
need the caller to desctruct the head of the list to destruct all of it.
If you delete erraneously an element in the middle of the list, the
"next" pointer of the previous element remains "dangling".
Recommendation: Introduce a "node" (list element) class that only
destructs itself, and a "head" (list header node) class that destructs
itself, and all its children.

Greetings,
        Thomas



      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]
0
Thomas
6/29/2003 11:21:34 AM
Hi,

First, if you are doing this for more than just a learning exercise, you
should
consider using std::list instead--it's doubly-linked just as yours is, and
interacts
well with the standard algorithms.

The simple answer to your stack overflow problem is to replace recursion
with iteration.  To do so, your best bet (in my opinion) is to have a
separate
"ListNode" class whose destructor is a no-op.  Then, in the LinkedList
class,
you just iterate over the nodes & delete them one by one (make sure that you
get a pointer to the next node before you delete the current one,
obviously).
But that's about all there is to it--no stack overflow problems anymore.

Good luck!

Drew


"MiniDisc_2k2" <MattDelB@nospam.com> wrote in message
news:bB%Ka.29587$pH3.16521@news2.east.cox.net...
 > All right, now here's a hard one:
 >
 > I was making a class which implements a linked list, and I need it to have
a
 > destructor (for obvious reasons). Unfortunately, if there's too many items
 > in the linked list, I get a stack overflow (because the destructor is
 > recursive, as you will see in a minute). Anyone see a way around this?
 >
 > (Simplified Example)
 >
 > class LinkedList
 > {
 > public:
 >      LinkedList *next;
 >      LinkedList *prev;
 >      int value;
 >      LinkedList();
 >      ~LinkedList();
 > };
 >
 > LinkedList::LinkedList()
 > {
 >      next = prev = NULL;
 > }
 >
 > LinkedList::~LinkedList()
 > {
 >      if (next!=NULL)
 >          delete next;
 >
 >      prev->next = NULL;
 > }
 >
 > This destructor ensures that if the first element is deleted, none of the
 > later elements will be "lost to the void." Is there any other destructor
you
 > guys can see that isn't recursive and ensures that memory leaks won't
occur?
 >



      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]
0
Drew
6/29/2003 11:22:14 AM
"MiniDisc_2k2" <MattDelB@nospam.com> wrote in message news:<bB%Ka.29587$pH3.16521@news2.east.cox.net>...
 > All right, now here's a hard one:
 >
 > I was making a class which implements a linked list, and I need it to have a
 > destructor (for obvious reasons). Unfortunately, if there's too many items
 > in the linked list, I get a stack overflow (because the destructor is
 > recursive, as you will see in a minute). Anyone see a way around this?
 >
 > (Simplified Example)
 >
 > class LinkedList
 > {
 > public:
 >      LinkedList *next;
 >      LinkedList *prev;
 >      int value;
 >      LinkedList();
 >      ~LinkedList();
 > };
 >
 > LinkedList::LinkedList()
 > {
 >      next = prev = NULL;
 > }
 >
 > LinkedList::~LinkedList()
 > {
 >      if (next!=NULL)
 >          delete next;
 >
 >      prev->next = NULL;
 > }
 >
 > This destructor ensures that if the first element is deleted, none of the
 > later elements will be "lost to the void." Is there any other destructor you
 > guys can see that isn't recursive and ensures that memory leaks won't
 > occur?

   I think that your destructor will enter infinite loop for every non-empty
list.  It will never find a NULL 'next' ptr because the assignment is put
AFTER deletion of the next item. Try to change the condition used
to stop the loop, e.g.

LinkedList::~LinkedList()
{
   if (next != this)  // next is different from current
    {
      // exclude the current item; prev might be == next
      prev->next = next;
      next->prev = prev;
      delete next;
    }
}

   If you want an iterative destructor, you can prevent all the other destructors
from entering the loop with modification of their data, e.g.

LinkedList::~LinkedList()
{
   while(next != this) // next is different from current, otherwise nothing to do
    {
     // prepare the next step
     LinkedList * next_step = next->next;  // will be invalid after deletion
     next->next = next;                      // makes 'next == this' in 'next'
     delete next;
     next = next_step;
    }
}

BTW, you have a problem that your 'LinkedList' is never empty.
Most of containers (including your pockets and bank accounts)
allow themselves to be empty.  The solution can be to make
an internal class/struct of a node, and to keep a ptr to a head
node of a list. When the head is null, the list is empty.
Another solution can be to use a dummy node as a head of the list.
As usual, we have the space/time problem here: the first solution
needs less memory, but the second solution runs faster -
the iterators are much simpler.
An example of the first solution is given below.  I think you can
find an example of the second solution in your STL implementation
of double linked list.

class LinkedList
{
   private:
    struct node
     {
      node *next;
      node *prev;
      int            value;
     };
    node *head;

   public:

    LinkedList()  { head = 0;}
    ~LinkedList()
     {
      while (head)
       {
        node * next = head->next;
        delete head;
        head = next;
       }
     }

   ... insert/delete/find a value ...
};

   Good luck!

   Michael

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]
0
tmk
6/29/2003 11:30:42 AM
>    I think that your destructor will enter infinite loop for every
non-empty
> list.  It will never find a NULL 'next' ptr because the assignment is
put
> AFTER deletion of the next item. Try to change the condition used
> to stop the loop, e.g.

Uh, I have no idea what you're talking about, but the NULL condition
works.

>
> LinkedList::~LinkedList()
> {
>    if (next != this)  // next is different from current

this will _never_ be true. I never initialized it to this.


> BTW, you have a problem that your 'LinkedList' is never empty.

Here's how it's empty:

int main()
{
    LinkedList* first_element = NULL;
}

It's empty. It's not really a container but more a bunch of addresses
strung
together. This class should NEVER be used as a non-pointer type (unless
dereferencing it to get the data out). I didn't want to make a
full-blown
container because it's just more coding and what I had done was
sufficient.


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]
0
MiniDisc_2k2
6/29/2003 10:14:56 PM
Reply: