Pointers and Memory Allocation

[JasBeckC]

Hello everyone,

I'm working on a linked list implementation. However, in implementing the AddAt method (in the file List.cpp), i allocate memory for pointers but don't know how to free the allocated memory in my exemple. can anyone help? You'll find my code below.

Thanks

Node.h

#ifndef _NODE_H_
#define _NODE_H_


class Node{
	int mData;
	Node* nextNode;

public:
	Node();
	void setData(int data);
	void setNextNode(Node* node);
	int getData(void);
	Node* getNextNode(void);
	Node* operator =(Node* node);
};

#endif 

Node.cpp

#include "Node.h"
#include<iostream>

using namespace std;

Node::Node(){
	mData=0;
	nextNode==NULL;
};

void Node::setData(int data){
	mData=data;
}

void Node::setNextNode(Node* node){
	nextNode=node;
}

int Node::getData(void){
	return mData;
}

Node* Node::getNextNode(void){
	return nextNode;
}

Node* Node::operator=(Node* node){
	this->setData(node->getData());
	this->setNextNode(node->getNextNode());
	return this;
}

List.h

#ifndef _LIST_H_
#define _LIST_H_

#include "Node.h"

class List{
	Node* head;
public:
	List();
	void Add(int data);
	void AddAt(int index, int data);
	void Print();
	void DeleteAt(int index); // A little tricky
	int getEndList();
};
#endif 

List.cpp

#include "List.h"

#include<iostream>
using namespace std;

List::List(){
	head=NULL;
}

void List::Print(){
	Node* tmp=head;
	if(tmp==NULL){
		cout <<"The List is Empty" << endl;
	}
	if(tmp->getNextNode()==NULL){
		cout <<tmp->getData();
		cout <<"-->NULL" << endl;
	}
	else{
		while(tmp->getNextNode()!=NULL){
			cout<<tmp->getData();
			cout<<"-->";
			tmp=tmp->getNextNode();
		}
		cout <<tmp->getData();
		cout<<"-->NULL" << endl;
	};

	delete tmp;
}

void List::Add(int data){
	Node* newNode = new Node;
	newNode->setNextNode(NULL);
	newNode->setData(data);

	Node*temp = head;

	if(temp==NULL){
		head=newNode;
	}
	else{
		while(temp->getNextNode()!=NULL)
		{
			temp=temp->getNextNode();
		}
		temp->setNextNode(newNode);
	}

}

void List::AddAt(int index, int data){
//Get end of List
		int endList(1);
		endList=this->getEndList();

		if(index>endList){
			cout<< "Your index is out range" << endl;
		}

		Node* newNode=new Node;
		Node* temp=new Node;

		newNode->setData(data);
		temp=head;

	if (index==1){
		newNode->setNextNode(temp);
		head=newNode;
	}

	if (index==2){
		Node* nodeAfter;
		Node* nodeBefore;

		nodeBefore=temp;
		nodeAfter=temp->getNextNode();
		nodeBefore->setNextNode(newNode);
		newNode->setNextNode(nodeAfter);
	}

	if (index==endList){
		Node* nodeBefore;

		for(int j(1); j<index-1;j++){
			temp=temp->getNextNode();
		}
		nodeBefore=temp;
		nodeBefore->setNextNode(newNode);
		newNode->setNextNode(NULL);
	}
	else if (index>2){
		Node* nodeAfter;
		Node* nodeBefore;

		for(int j(1); j<index-1;j++){
			temp=temp->getNextNode();
		}
		nodeBefore=temp;
		nodeAfter=temp->getNextNode();
		nodeBefore->setNextNode(newNode);
		newNode->setNextNode(nodeAfter);
	}

};

void List::DeleteAt(int index){

	int endList=this->getEndList();
	
	if (index>endList){
		cout << "Index of Delete Out of Range" << endl;
	}

	Node* temp;
	temp=head;
	if (index==1){
		head=temp->getNextNode();
	}
	if (index==2){
		temp=temp->getNextNode();
		temp=temp->getNextNode();
		head->setNextNode(temp);
	}

	if (index==endList){
		Node* nodeBefore;
		for(int j(1); j<index-1;j++){
			temp=temp->getNextNode();
		}
		nodeBefore=temp;
		nodeBefore->setNextNode(NULL);
	
	}
	if (index>2){
		Node* nodeBefore;
		Node* nodeAfter;
		for(int j(1); j<index-1;j++){
			temp=temp->getNextNode();
		}
		nodeBefore=temp;
		temp=temp->getNextNode();
		nodeAfter=temp->getNextNode();
		nodeBefore->setNextNode(nodeAfter);
	}

}
int List::getEndList(){
	
		int endList(1);
		Node* nodeEndList;
		nodeEndList=head;
		while(nodeEndList->getNextNode()!=NULL){
			nodeEndList=nodeEndList->getNextNode();
			endList++;
		}
		endList++;
		return endList;
}

[dhayden]

in implementing the AddAt method (in the file List.cpp), i allocate memory for pointers but don't know how to free the allocated memory

You're allocating a new node and adding it to the list. The list takes ownership of the memory. It shouldn't get deleted until you delete the list or the specific item.

In other words, what you are missing is a destructor for the List, which should delete all items in the list. Also, DeleteAt should delete the node that it removes. Finally, List::Print should not delete anything (line 29).

Some other comments:

Your addAt and deleteAt methods say that position 1 is the beginning of the list. In C++, objects usually start at position 0.

Your addAt and deleteAt methods are inefficient. Consider what happens with the list has 100,000 items and execute addAt(27). Since you always call getEndList(), you run a loop 100,000 times when you only needed to loop 27 times. See if you can code it so you only use one loop (inside addAt or deleteAt). Note that you'll still need an exception for adding to the beginning of the list.

[JasBeckC]

Hello, thanks for the reply,

okay so the destructor will be in charge of deleting all the pointers for which memory has been allocated by the methods. But I still have a question:

like in my exemple, in several methods I allocated memory for pointers that have the same name (temp or tmp). this is not a problem of names since they are located in distinct scopes. So how will the destructor of List will know which is te pointer temp created by Add and the pointer temp allocated by AddAt? I mean to make it clear:

In:

void List::AddAt(int index, int data){
       Node* temp=new Node;
       //Code
};

and :

void List::Add(int data){
       Node* temp=new Node;
       //code
}

two memory allocations have been done. But each time it was by temp. how will the destructor know temp from temp?

In addAt and deleteAt I need to get the end of the list, that's why i'm calling each time the getEndList(). what would be a better way to get end of list?

thanks again!!

[dhayden]

The reason you don't need to worry about who allocated the memory is because both Add() and AddAt() put the allocated memory into the list. In other words, either head or some node's next pointer will point to the allocated memory. The destructor will use that pointer to delete it. Make sense?

In addAt and DeleteAt, you don't need to go to the end of the list, only to the index'th item:

void List::AddAt(int index, int data){
	Node* newNode=new Node;
	Node *tmp;

	newNode->setData(data);
	if (index <= 1) {
		newNode->setNextNode(head);	// special case for first node
		head = newNode;
	} else if (head == nullptr) {
		// error. List too short
	} else {
		// set tmp to point to the (index-1)'th item, or NULL
		for(index-=2, prev=head; index && prev; --index, prev = prev->next)
			;
		if (prev == nullptr) {
			// error. List is too short
		} else {
			newNode->setNextNode(prev->getNextNode());
			prevNode->setNextNode(newNode);
		}
	}
}

[JasBeckC]

Sorry again, it's abstract for me.

suppose we have this:

class List{
public:
	 void Method1(){
		 if (/*some condition*/){
			 Node* temp1= new Node;
		 }
	 }
	 void Method2(){
		 if (/*some condition*/){
			 Node* temp2= new Node;
		 }
	 }
	 ~List(){
		 //what code to be inserted?
	 }
};

How would the destructor look like for this simplified class?

Aha I see, thanks for the AddAt method!!

thanks again for the help

[dhayden]

For the exact code that you posted above, the memory is leaked. But for the real list methods, the new nodes get inserted into the list, so there is still something pointing to them. At that point, the list "owns" the memory - meaning that the list is responsible for deleting it:

List::~List()
{
    Node *tmp;
    while (head) {
         tmp = head->getNextNode();
        delete head;
        head = tmp;
    }
}