Delete linked list

Question

Hey I wonder about I have written a C++ linked list, where I call a destructor to go through an allocated linked list and delete every node found. However what I found is that although it goes through the linked list and delete every occurance it will still print out values. Although just some scrap values.

But shouldn't it be when I delete the linked_list it shouldn't be printable next time? I'm create a linked list by using the new, and delete when I remove the list

sorted_list::~sorted_list()
{
    // Destructor implementation
    destroy(this->first);
    cout << "Destructor called sorted_list" << endl;
}

void sorted_list::destroy(list_link* item)
{
  if (item)
  {
    destroy(item->next);
    delete item;
  }
}

print function

void sorted_list::print() {

    if(this->first)
    {
        iteratorn *traverse = new iteratorn(this->first);
        while( !traverse->iterator_end() )
        {
            cout << traverse->iterator_get_key() << " ";
            traverse->iterator_next();
        }
        delete traverse;
    }
    else
        cout << "list empty" << endl;
}

Not enough code. Show the code that builds the list, and show the code that prints out values that it shouldn't. — Björn Pollex
– Björn Pollex, Commented Nov 6, 2010 at 11:32
You don't need to assign NULL (or even 0) to this->first in the destructor. The list is released, it's gone, utterly inaccessible. — wilhelmtell
– wilhelmtell, Commented Nov 6, 2010 at 14:21
@Roger Pate @wilhelmtell thanks for input I remove the double delete of this->first now — starcorn
– starcorn, Commented Nov 6, 2010 at 21:23

Vlad · Accepted Answer · 2010-11-06 12:54:15Z

14

When you access a destructed object, the behaviour is undefined. In fact, deleting an object doesn't clear the memory, just marks it available, so if you execute some operations on already deleted object, they may do something reasonable. But again, the object is destructed, so you must not access it.

Of course, you should not retain any pointers to the object belonging to the linked list after it's destructed, because those objects will be destructed as well.

By the way, your sorted_list::destroy is recursive, which is quite inefficient. You would need perhaps to replace it with iterative approach:

void sorted_list::destroy(list_link* item)
{
    while (item)
    {
        list_link* old = item;
        item = item->next;
        delete old;
    }
}

(And you should take into account @Roger Pate's comment and not delete this->first the second time after calling destroy(this->first);.)

edited Nov 6, 2010 at 12:54

answered Nov 6, 2010 at 11:35

Vlad

35.7k7 gold badges82 silver badges205 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Timo Over a year ago

Yeah, always destroy lists iteratively, because the recursive method might run out of stack space if the list is too large.

wilhelmtell Over a year ago

@Vlad @Timo this is not accurate. Any modern C++ compiler should know how to optimize away at least tail-recursions. Here it is actually straight-forward to convert the recursion to a tail-recursion, and the result object-code should be identical to that of a loop: if( ! item ) return; list_link* next = item->next; delete item; destroy(next);

Vlad Over a year ago

@wilhelmtell: it's a dangerous practise to assume that the optimizer will optimize the recursion out for you. Unless such an optimization is guaranteed by C++ standard, I would not rely on it.

starcorn Over a year ago

I've been trying around, and still can't get why I still retain scrap values. I actually want the program to crash when I try to access an already deleted linked list, but instead it will print out some scrap values. I have added in my print function also.

Vlad Over a year ago

@starcom: you cannot get a guaranteed crash, the behaviour is just undefined. Look, when you destruct the object, the memory gets freed, and returned to the global memory pool. So it may be overwritten with any values at any time, or it may as well still have its old values, you never know. If it happens to have the old values, your print function may not crash. And you cannot guarantee that the function will crash, because this needs the memory to be filled with some special values--but that is not possible, because the memory can be reused by other objects. You see?

|

Kostas · Accepted Answer · 2018-05-02 17:38:01Z

0

When declaring the link, which probably looks more or less like this:

struct list_link {
    int data;
    list_link *next;
};

You could slip a destructor in:

struct list_link {
    int data;
    list_link *next;
    ~list_link() { delete next; }  // MAKE SURE NULL-TERMINATED LIST
};

This way if you want to delete the list you can simply:

delete first;

MAGIC!!

edited May 2, 2018 at 17:38

answered Dec 29, 2017 at 4:01

Kostas

4,1841 gold badge16 silver badges32 bronze badges

Comments

Red.Wave · Accepted Answer · 2018-05-02 19:03:35Z

0

Missing part is nullifying. After deleting, you must nullify the first node at least. I would nullify every node after delete.

answered May 2, 2018 at 19:03

Red.Wave

4,77814 silver badges21 bronze badges

Collectives™ on Stack Overflow

Delete linked list

print function

3 Answers 3

6 Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

print function

3 Answers 3

6 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related