I have this small piece of code in my IntList implementation to push_back nodes. My question is if the *pnode cause memory leak or do I need to delete it at the end.
void IntList::push_back(int data){
if (first){
IntNode *pNode = first;
while(pNode->next!=0){pNode = pNode->next;}
pNode->next = new IntNode(data);
} else
first = new IntNode(data);
}
No you don't need to call delete on pNode. You only call delete on things created with new. With the code as it is now pNode is a stack object and will automatically be destroyed when it goes out of scope at the end of the function.
You have to delete the IntNodes created with new eventually, likely in the destructor of the container and the pop_back function. pNode itself (the pointer) was allocated on the stack, and not with new, so does not need to be deleted.
You don't need delete pNode. Moreover, you can't do it in this particular case.
After you create something with new you must delete it exactly one time - once you'll never use it.
After removing the object with delete, attempt to read its contents is an undefined behavior. The pointers are generally one of the most bug generating part of the c++, so it is good that you are trying to understand it better.
You can visualize yourself this way: You can buy a house (house is a piece of memory) with new. It returns you address if it. It is your house now and can do with it what you want. You can also sell it with delete. Until this is done, you can give your friend your home address so that they can come to you. Distribution of the address, causing copying it (e.g. IntNode *pNode = first;). However, you still have only one house. So no matter how many times you copy your home address, you can sell the house only once.
I would advise using smart pointers (e.g. std::unique_ptr), but I think this program is for learning programing, so don't do it ;)
You need delete nodes on each function that removes nodes from the list, not when inserting. Not doing so would cause a leak.
If there are still allocated nodes when you destruct the object you need to iterate the whole list to remove all the nodes too. Not doing so would cause a leak too.
I suppose that this is a college assignment, as there are millions of battle-tested linked list implementations out there.
You'd do better if you maintain a tail node up to date on all functions, so you could avoid iterating the whole list to insert a node on the tail.
The code you show is not sufficient to tell if you're leaking memory or not. You show the routine responsible for allocation, but not the code where you're performing deallocation.
If you don't have any code performing deallocation, then yes, obviously that leaks. C++ does not perform automatic garbage collection as you may be used to in some other languages.
You are using naked new, so even if you do have some other code attempting to do deallocation, there's a good change it's being done incorrectly.
In C++ you generally shouldn't be using the new operator directly, and you should learn to use RAII to handle resources instead. IntList presumably uses owning raw pointers, which is another thing to be avoided. In this case you should probably be using unique_ptr<IntNode>. For example:
struct IntList {
struct IntNode {
unique_ptr<IntNode> next;
int data;
IntNode(int data) : data(data) {}
};
unique_ptr<IntNode> first;
// returns a reference to the null pointer which terminates the linked list
unique_ptr<IntNode> &get_tail() {
if (!first) {
return first;
}
IntNode *pNode = first.get(); // pNode is a non-owning pointer
while (pNode->next) {
pNode = pNode->next.get();
}
return pNode->next;
}
void push_back(int data) {
get_tail() = make_unique<IntNode>(data);
}
};
There actually is a problem with the above code, but the issue is unrelated to memory leaks. When the list is destroyed, first is automatically destroyed, which automatically destroys first->next, and so on. It's possible to insert so many elements into the list that this chain of destruction 'smashes' the function stack, leading to undefined behavior.
The problem can be fixed with an IntList destructor that destroys the nodes in the opposite order:
IntList::~IntList() {
while (first) {
unique_ptr<IntNode> tmp = std::move(first);
first = std::move(tmp->next);
}
}
It's interesting that this is an example of an exception to the Rule of Three.
