Destructor for a linked list

Question

The full code is located here: https://gist.github.com/4521540

It's a dummy List in C++. My concern is with freeing up memory. It doesn't crash when I run my code. It looks like my if/else covers everything.

1. It starts by deleting the second item if there is. That's what the while loop does.
2. If there is only one present (or left with one), delete startNode.

startNode is a pointer points to the first item in the list. endNode always points to the last item in the list.

Am I deleting the pointer or the underlying object?

I do mostly Python. Last time I wrote a serious C++ homework was about 2 years ago in my algorithm class so I really can't remember everything off my head.

~List()
{ 
 // there is at least one item
 if(startNode != 0)
 { 
 // release memory starting from the second item
 ListNode *current, *soon;
 current = this->startNode->next;
 while(current != 0) // if there are at least two items
 {
 /* When there is no more items after current,
 * delete current and leave.
 * Otherwise, free up current and move on to
 * the next item.
 */
 if(current->next != 0)
 {
 soon = current->next;
 delete current;
 current = soon;
 }
 else
 {
 delete current;
 break;
 }
 }
 }
 delete this->startNode;
 delete this->endNode;
}

Also, do I need to delete the myList in my main program? I think when I exit the program, the destructor is automatically called.

• Harald Scheirich: You also might want to read up on smart pointers. You can protect against memory leaks and double deletes by using std::unique_ptr.
• Toby Speight: Do you have a test suite for this? And have you run it under Valgrind (or other memory checker of your choice)?

Answer 1

First, to answer your questions about new/delete: Everything you new, you must delete at some point, or you leak memory. When you new, you are given a pointer to the object that has been allocated. Similarly, when you use delete, you must use a pointer to that same object, and the memory that was allocated will be freed. After doing this, the pointer will be pointing at freed memory and you should not delete this again. It doesn't matter where you use new, in main() or otherwise, you need to delete it at some point.

Now to your code: Your code will double-delete either the first node when the list size is 1, or the last node, when the list size is greater than 1. Double deletes cause undefined behaviour including crashes.

Let's look at list of size 1 first. Your while loop won't be entered, and you basically skip down to the end where you do

delete this->startNode;
delete this->endNode;

Since startNode and endNode should both be pointing to the only node in the list, it will get deleted twice!

If you have a list of more items, the loop will delete every item except the first. Then the last two statements occur. In this case, this->endNode will be the original end of the list (since you never alter it here) and so it will be deleted twice.

Here is a simpler version that just deletes every node, starting from the first.

~List
{
 ListNode* current = startNode;
 ListNode* next;
 while (current != NULL) {
 next = current->next;
 delete current;
 current = next;
 }
}

• Deduplicator: That can be shortened: for (auto p = startNode; p;) delete std::exchange(p, p->next);

Answer 2

A cleaner way would be to go iteratively through the list.

I would do something like:

~List()
{ 
 if(startNode == NULL)
 return;
 if(startNode->Next != 0)
 { 
 delete this->startNode->Next;
 }
 delete this->startNode;
}

This will go through your list, and startNode->Next will be the new startNode (this), thus it should delete the whole list just fine.

• CppLearner: You meant while (startNode->next != 0)?Also, correct me if I am wrong: I only need to provide a destructor if there's new in the class/struct implementation, right? Do I need to delete anything in main? Thanks.
• MahlerFive: This code will only delete the first and second node. Even if you change the if to a while, you would need to add a temporary variable in there to keep track of the next before deleting it, and then re-assigning startNode.
• SinisterMJ: It depends what type startNode is actually. I would do it like a listNode, and have in that listNode a reference to the Next node. Then a delete on the first node would go through to every single one.
• Konrad Rudolph: -1, this doesn’t work – you’re confusing List and ListNode here. This won’t iterate through the list nodes.
• SinisterMJ: Clearly each node saves the next node. So you can just iterate through the list. I don't get what you are trying to point here, with proper implementation this works. List object stores the first Node, and each node points to the next, so you can pass the delete from one node to the next.