Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Writing a LinkedList destructor?

Is this a valid LinkedList destructor? I'm still sort of confused by them.

I want to make sure I'm understanding this correctly.

 LinkedList::~LinkedList()
 {
   ListNode *ptr;

   for (ptr = head; head; ptr = head)
   {
     head = head->next
     delete ptr;
   }
}

So at the beginning of the loop, pointer ptr is set to hold the address of head, the first node in the list. head is then set to the next item, which will become the beginning of the list once this first deletion takes place. ptr is deleted, and so is the first node. With the first iteration of the loop, pointer is set to head again.

The thing that concerns me is reaching the very last node. The condition "head;" should check that it is not null, but I'm not sure if it will work.

Any help appreciated.

like image 222
kevin Avatar asked Feb 15 '10 12:02

kevin


3 Answers

Why not do it much much simpler - with an elegant while-loop instead of trying to carefully analyze whether that overcompilcated for-loop is correct?

ListNode* current = head;
while( current != 0 ) {
    ListNode* next = current->next;
    delete current;
    current = next;
}
head = 0;
like image 130
sharptooth Avatar answered Nov 14 '22 23:11

sharptooth


You can run it through a debugger or you can run it through that bit of wetware inside your skull - both will show you that it works fine. For example, let's start with the list:

head(47) -> [47]single_node -> [NULL]end-of-list.

Running that list through your statements:

  • ptr = head sets ptr to 47.
  • head is non-zero so enter loop.
  • head = head->next sets head to NULL.
  • delete ptr will delete the single_node.
  • ptr = head sets ptr to NULL.
  • head is now NULL (0) so exit loop.

There you go, you've deleted the only entry in the list and head is now set to NULL. That's all you need to do.

You can do a similar thing with a longer list or an empty list, you'll find it's still okay (there's no real difference between a one-element list and a fifty-element list).

As an aside, I'm not a big fan of treating pointers as booleans - I'd rather write it as something like:

for (ptr = head; head != NULL; ptr = head)

It makes the code read better in my opinion and you don't really sacrifice any performance (unless you have a brain-dead compiler). But that's a matter of taste.

Re your comment:

The thing that concerns me is reaching the very last node. The condition "head;" should check that it is not null, but I'm not sure if it will work.

It will work. A value of zero will be treated as false so you'll find that you never dereference head->next when head is NULL simply because you will have exited the loop body before that point (or not even entered the body if the list is empty).

Any other pointer value will be treated as true and you will enter or continue the loop body.

like image 5
paxdiablo Avatar answered Nov 14 '22 22:11

paxdiablo


The condition "head;" should check that it is not null, but I'm not sure if it will work.

Yes, "head" by itself is the same as "head != null" -- but why use a meaningless typing shortcut if even you find it confusing? It's only 6 more keystrokes (and generates identical machine code), so go for the long form.

Additionally, your code is a bit more complicated than necessary because you are using a for() construct. Why not use a while()? Your code will be much cleaner.

Finally, I realize you are doing this as a learning exercise, but keep in mind that list<> is in the standard library --- Linked lists are official a "Solved Problem".

like image 3
James Curran Avatar answered Nov 14 '22 22:11

James Curran