If you assign one Node to a second Node, does that second Node have the same data address as what was assigned to it?

[vaderboi]

Say I have this Node struct:

struct Node
{
    int data;
    Node *prev;
    Node *next;
}

I then create my first Node and my second Node:

Node *firstNode = new Node;
Node *secondNode = new Node;

If I assigned firstNode to secondNode, does *secondNode and *firstNode now point to the same memory address? Like if you change secondNode is firstNode also changed? If you delete secondNode, is firstNode also deleted?

[coder777]

If I assigned firstNode to secondNode, does *secondNode and *firstNode now point to the same memory address?

Yes. And you have a memory leak.

Like if you change secondNode is firstNode also changed?

There is no 'also'. They are pointing to the same memory address.

If you delete secondNode, is firstNode also deleted?

Again: there is no 'also'. The memory both pointing to is deleted and hence invalid. Accessing data of this memory or deleting it twice will raise undefined behavior and most likely a crash.

[vaderboi]

Why do you have a memory leak if two pointers point to the same place in memory?

[keskiverto]

int x;
int y;
int* foo = &x; // foo points to x
int* bar = &y; // bar points to y

foo = bar; // foo points to y
// no pointer points to x

*foo = 7;  // effectively: y = 7;
*bar = 42; // effectively: y = 42; 

Lets replace the local with dynamic:

int* foo = new int; // foo points to "x"
int* bar = new int; // bar points to "y"

foo = bar; // foo points to "y"
// no pointer points to "x"

delete foo; // the "y" is deallocated
// foo still has address, where "y" was
// bar still has address, where "y" was
delete bar; // error: trying to deallocate memory that is no allocated

// the "x" still exists. You don't have it's address
// You can't deallocate "x". That is the memory leak 

[vaderboi]

Ah. Okay. I get it. How can I avoid a memory leak if I have to have a function take a Node as a parameter? Especially when it comes to my printLots() function. I need to pass Nodes there to compare them, right? Here is my code as an example:

struct Node
{
	int data;
	Node *next;
	Node *prev;
};


#include <iostream>
#include <vector>

void fillList( const std::vector<int> &initialVec, Node *listToBuild );
void insertAtEnd( int value, Node *tail );
void printLots( Node *positionListBegin, Node *printListBegin );
void deleteAll( Node *firstNode );

int main()
{
	const std::vector<int> vecP = {1, 3, 4, 6, 7, 11};
	const std::vector<int> vecL  = {0, 7, 4, 3, 2, 1, 9, 8, 10, 40, 32, 31};
	
	Node *headP = new Node;
	Node *tailP = new Node;
	headP->next = tailP;
	headP->prev = nullptr;
	tailP->prev = headP;
	tailP->next = nullptr;


	Node *headL = new Node;
	Node *tailL = new Node;
	headL->next = tailL;
	headP->prev = nullptr;
	tailL->prev = headL;
	tailP->next = nullptr;

	fillList( vecP, tailP );
   	fillList( vecL, tailL );	

	printLots( headP, headL );
	
    deleteAll( headP );
	deleteAll( headL );

	return 0;
}


void fillList( const std::vector<int> &initialVec, Node *listToBuild )
{
	for( int i = 0; i < initialVec.size(); ++i )
	{
		insertAtEnd( initialVec[i], listToBuild );	
	}
}

void insertAtEnd( int value, Node *tail )
{
	Node *toInsert = new Node;
	toInsert->data = value;

	tail->prev->next = toInsert;

	toInsert->prev = tail->prev;
	toInsert->next = tail;

	tail->prev = toInsert;

}

void printLots( Node *positionListBegin, Node *printListBegin )
{
	Node *positionNode = new Node;
	positionNode = positionListBegin->next;

	Node *printNode = new Node;
	printNode = printListBegin->next;

	int dataIndexValue = 0;

	bool hasMoreToPrint = false;

	while( positionNode->next != nullptr && printNode->next != nullptr )
	{	
		hasMoreToPrint = false;

		if( positionNode->data == dataIndexValue )
		{
			std::cout << printNode->data << " ";
			positionNode = positionNode->next;
			hasMoreToPrint = true;

		}
		else
		{
			printNode = printNode->next;
			++dataIndexValue;
		}
	}
	
	if( hasMoreToPrint == false )
	{
		std::cout << "\n";
		std::cout << "No matching index value " 
<< positionNode->data <<
 " found in print list. Terminating printLots function" << std::endl;
	}

	delete positionNode;
	delete printNode;

	std::cout << "\n";
}


void deleteAll( Node *firstNode )
{
	Node *moveNode = new Node;

	moveNode = firstNode;

	while( moveNode->next != nullptr )
	{
		moveNode = moveNode->next;
		delete moveNode->prev;
	}

	delete moveNode;
}

[keskiverto]

Ah. Okay. I get it. How can I avoid a memory leak

You have to first understand the memory leak.

Lets do it again.
* You get an address, when you allocate&create object dynamically
* You need that address in order to access the object
* You need that address in order to deallocate the object
* If you lose the address, then you have a memory leak

How can you lose it?
1. The lifetime of only/last pointer ends.

{
  int* foo = new int; // foo points to "x"
  // use "x" via foo
} // end of scope, end of foo, not end of "x"
// address of "x" is not stored anywhere 

2. You assign/overwrite the pointer

int* foo = new int; // foo points to "x"
// use "x" via foo
foo = nullptr; // foo stores a different address
// address of "x" is not stored anywhere 

How can you avoid those?
1. You ensure that you have at least one pointer that stores the address as long as you need the dynamically created object
2. You deallocate the object before the last address is lost

int* foo = new int; // foo points to "x"
// use "x" via foo
delete foo; // deallocate "x"
// foo is used for something else or dies 

In your program:

void printLots( Node *positionListBegin, Node *printListBegin )
{
	Node *positionNode = new Node;
	delete positionNode;
	positionNode = positionListBegin->next;

	Node *printNode = new Node;
	delete printNode;
	printNode = printListBegin->next;

However, what is the point in creating Nodes that you never use (and have to immediately destroy)?

[coder777]

Just because you have a pointer you don't need new. Just assign the other pointer directly. E.g.:

void deleteAll( Node *firstNode )
{
	Node *moveNode = new Node;

	moveNode = firstNode;

	Node *moveNode = firstNode;

	while( moveNode->next != nullptr )
	{
		moveNode = moveNode->next;
		delete moveNode->prev;
	}
	delete moveNode;
}

[vaderboi]

Oh okay. So if I assign firstNode to *moveNode that means both firstNode AND moveNode are pointing to "x". If I delete moveNode in the end, there is still a pointer to "x" because firstNode exists and therefore there is no memory leak. Do I understand that correctly?

[MikeyBoy]

So if I assign firstNode to *moveNode that means both firstNode AND moveNode are pointing to "x".

moveNode is a pointer. *moveNode is therefore an object, and a temporary one. So you can't assign anything to *moveNode.

You want to assign firstNode to moveNode.

This may sound like pedantry, but it's not. It's important that you understand what the impact is of putting an asterisk in a declaration, and of using the asterisk as an operator, and how they differ.

If I delete moveNode in the end, there is still a pointer to "x" because firstNode exists and therefore there is no memory leak.

Whether or not there's a memory leak has nothing to do with whether there's a pointer to x. It depends on whether or not you've deleted x. If you still have a pointer to x, but haven't deleted it, then you still have a memory leak.

Of course, if you no longer have a pointer to x, then there's no way to delete it, which is the issue keskiverto was pointing out.

[keskiverto]

A pointer is a variable that stores a value, just like every variable does.

The value stored in a pointer is an address of an another variable.

The pointer does not have to have a valid address in it. If the value is nullptr, then it is clear that the address is not valid.

both firstNode AND moveNode are pointing to "x". If I delete moveNode in the end, there is still a pointer to "x" because firstNode exists and therefore there is no memory leak. Do I understand that correctly?

No, you don't.

Lets write that as code:

int* firstNode = new int {42};
int* moveNode = firstNode;
// yes, both firstNode AND moveNode are pointing to
// dynamically allocated integer that has value 42

delete moveNode; // no. This does not delete the moveNode. It deletes the
// dynamically allocated integer that had value 42

// both firstNode AND moveNode still have the same value as before
// but the value is now invalid

// END: the was no memory leak, because the dynamically allocated int
// was deallocated 

[jonnin]

and totally aside, you can define the assignment operator yourself to do something different if you needed to. Its not useful for this program, but if you had something with a pointer-array of data inside, you could loop and copy the data rather than copy the pointer in your over-ride if you wanted a true copy instead. This is not useful for what you are doing, but keep it in mind that you can control the behavior.

that over-rides node = node, not node*=node*, though. as already said, that * is critical!

as an example, you could make a copy of the whole left and right sub-trees when you assign node=node by doing this. Again, not very useful for your program...

[vaderboi]

Thank you all.

Would any and/or all of you take a look at my printLots() and deleteAll() functions? I wrote comments describing what I think is happening with memory allocation and I just want to make sure I understand it. This code is unaltered from earlier except for the comments. Before I change it, I want to understand what I did wrong.

struct Node
{
	int data;
	Node *next;
	Node *prev;
};


#include <iostream>
#include <vector>

void fillList( const std::vector<int> &initialVec, Node *listToBuild );
void insertAtEnd( int value, Node *tail );
void printLots( Node *positionListBegin, Node *printListBegin );
void deleteAll( Node *firstNode );

int main()
{
	const std::vector<int> vecP = {1, 3, 4, 6, 7, 11};
	const std::vector<int> vecL  = {0, 7, 4, 3, 2, 1, 9, 8, 10, 40, 32, 31};
	
	Node *headP = new Node;
	Node *tailP = new Node;
	headP->next = tailP;
	headP->prev = nullptr;
	tailP->prev = headP;
	tailP->next = nullptr;


	Node *headL = new Node;
	Node *tailL = new Node;
	headL->next = tailL;
	headP->prev = nullptr;
	tailL->prev = headL;
	tailP->next = nullptr;

	fillList( vecP, tailP );
   	fillList( vecL, tailL );	

	printLots( headP, headL );
	
    deleteAll( headP );
	deleteAll( headL );

	return 0;
}


void fillList( const std::vector<int> &initialVec, Node *listToBuild )
{
	for( int i = 0; i < initialVec.size(); ++i )
	{
		insertAtEnd( initialVec[i], listToBuild );	
	}
}

void insertAtEnd( int value, Node *tail )
{
	Node *toInsert = new Node;
	toInsert->data = value;

	tail->prev->next = toInsert;

	toInsert->prev = tail->prev;
	toInsert->next = tail;

	tail->prev = toInsert;

}


void printLots( Node *positionListBegin, Node *printListBegin )
{	
	//points to "x"
	Node *positionNode = new Node;
	//positionNode now points to positionListBegin->next and NOT "x"; memory leak
	positionNode = positionListBegin->next;

	//points to "y"
	Node *printNode = new Node;
	//printNode now points to printListBegin->next and NOT "y"; memory leak
	printNode = printListBegin->next;

	int dataIndexValue = 0;

	bool hasMoreToPrint = false;

	while( positionNode->next != nullptr && printNode->next != nullptr )
	{	
		hasMoreToPrint = false;

		if( positionNode->data == dataIndexValue )
		{
			std::cout << printNode->data << " ";
			/*positionNode now points to the next node in the chain;
			the previous node positionNode pointed to still exists.
			So there is no memory leak here*/
			positionNode = positionNode->next;
			hasMoreToPrint = true;

		}
		else
		{
			printNode = printNode->next;
			++dataIndexValue;
		}
	}
	
	if( hasMoreToPrint == false )
	{
		std::cout << "\n";
		std::cout << "No matching index value "
 << positionNode->data << " found in print list. Terminating printLots function" << std::endl;
	}

	//going to delete whatever element they are currently pointing to
	delete positionNode;
	delete printNode;

	std::cout << "\n";
}


void deleteAll( Node *firstNode )
{
	//memory leak here too
	Node *moveNode = new Node;

	moveNode = firstNode;

	while( moveNode->next != nullptr )
	{
		moveNode = moveNode->next;
		//this should be fine to delete entire list
		delete moveNode->prev;
	}

	//and then the final node in the list
	delete moveNode;
}

[MikeyBoy]

You've correctly identified three memory leaks; the Node objects you create on lines 75, 80 and 127 are never deleted. Furthermore, they cannot be deleted, because you no longer have their addresses stored anywhere.

[jonnin]

it looks like you want to create pointers and initialize them immediately using new.

Node *positionNode = new Node;
positionNode = positionListBegin->next;

all you need to do is not use new when you don't need a new item.
if you want a pointer that is going to pick up existing memory, you don't need new:

Node *positionNode = nullptr; //this is a good default initialization for such a pointer.
positionNode = positionListBegin->next; //no leak now.


once you get past the new/delete memory hands-on study section in school you won't use new and delete much, if at all. The vast majority of your pointers will pick up existing memory as seen here, so get used to this pattern.

[vaderboi]

Yeah I think I understand this a lot better now. I think I got confused about what "new" did but yeah I realize that if I just want a pointer to a Node (like for iterating through a linked list to print) I need to just assign whatever node I want pointed at to to the new pointer I am creating.

Thank you all for the help!