Thread: Doubly Linked List Deletion Issue

Hey everyone, I've been working with linked lists for a little while now, and I have them implemented in several of my programs, however... I never really took the time to optimize my node deletion functions, and since I am doing so I am looking closer at memory usage during operation, and I noticed that not everything is being cleared. Usually after I "delete" all of my nodes, I am still left with 10-15% memory usage.

For instance, when I create 5,000,000 nodes, (roughly 434.4MB), and I delete them, at the end I am left with around 46.4MB.

Now, when I repeat the process, it leaks even more memory, so I'm thinking it isn't something weird with the windows memory manager caching stuff, but rather something about the 'delete' operator that I am overlooking.

Here is my code stripped down and simplified:

Code:

struct Internal
{
	unsigned long NodeCount;
};

Internal I;

struct Node
{
	Node *Forward, *Backward;
	string Handle;
	unsigned long Ident;
};
Node *NodeStart, *NodeEnd, *NodeRecent;

Node* CreateNode(void)
{
	Node *new_node = new Node;
	if(NodeStart==NULL)
	{
		if(I.NodeCount==0)
		{
			NodeStart = new_node;
			NodeStart->Backward=NULL;
			NodeEnd=NodeStart;
		}
	}
	else
	{
		(NodeEnd->Forward) = new_node;
		(new_node->Backward) = NodeEnd;
	}
	(new_node->Forward) = NULL;
	(new_node->Ident) = I.NodeCount;
	NodeEnd = new_node;
	NodeRecent = new_node;
	I.NodeCount++;
	return (new_node);
}

void CreateNodes(unsigned long n){for(n;n>0;n--){CreateNode();}}

Node* ApplyHandleToNode(Node* target, string handle)
{
	if(target!=NULL)
	{
		target->Handle=handle;
		return (target);
	}
	return (NULL);
}

void DeleteNodeStart(void)
{
	if(NodeStart!=NULL)
	{
		if((NodeStart->Forward)!=NULL)
		{
			Node *temp = NodeStart;
			NodeStart = (NodeStart->Forward);
			I.NodeCount--;
			delete temp;
		}
	}
}

void DeleteNodeEnd(void)
{
	Node *temp;

	if(NodeStart!=NodeEnd)
	{
		temp=NodeEnd->Backward;
		delete NodeEnd;
		NodeEnd=temp;
		I.NodeCount--;
		//cout << I.NodeCount << endl;
	}
	else
	{
		delete NodeEnd;
		NodeStart=NULL;
		I.NodeCount--;
	}

}

short DeleteNodeIdent(unsigned long ident)
{
	Node *target=NodeStart;
	if(NodeStart!=NULL)
	{
		while(target!=NULL)
		{
			if((target->Ident)==ident)
			{
				((target->Forward)->Backward)=(target->Backward);
				((target->Backward)->Forward)=(target->Forward);
				delete target;
				I.NodeCount--;
				return (1);
			}
			target=(target->Forward);
		}
	}
	return (-1);
}

Node* Ident(unsigned long ident)
{
	Node *target=NodeStart;
	if(NodeStart!=NULL)
	{
		while(target!=NULL)
		{
			if((target->Ident)==ident){return (target);}
			target=(target->Forward);
		}
	}
	return (NULL);
}

// (DEBUG)
void PrintNodesForwards(void)
{
	Node *target=NodeStart;
	while(target!=NULL)
	{
		cout << target->Ident << endl;
		if((target->Forward)!=NULL){target=(target->Forward);}
		else{return;}
	}
}

// (DEBUG)
void PrintNodesBackwards(void)
{
	Node *target=NodeEnd;
	while(target!=NULL)
	{
		cout << target->Ident << endl;
		if((target->Backward)!=NULL){target=(target->Backward);}
		else{return;}
	}
}

void DeconstructList(void)
{
	while(I.NodeCount>0)
	{
		DeleteNodeEnd();
	}
}

int main()
{
	cout << "Creating Nodes..." << endl;
	CreateNodes(5000000);
	getchar();

	cout << "Deconstructing list..." << endl;
	DeconstructList();
	getchar();
	
        cout << "Creating Nodes..." << endl;
	CreateNodes(5000000);
	getchar();

	cout << "Deconstructing list..." << endl;
	DeconstructList();
	getchar();

	cout << "Creating Nodes..." << endl;
	CreateNodes(5000000);
	getchar();

	cout << "Deconstructing list..." << endl;
	DeconstructList();
	getchar();

	cout << "Creating Nodes..." << endl;
	CreateNodes(5000000);
	getchar();

	cout << "Deconstructing list..." << endl;
	DeconstructList();
	getchar();

	return (0);
}

I would monitor via the task manager the amount of memory usage at each stage, for instance a typical cycle would look use memory as follows:

Create 5,000,000 (434.4MB used)
Delete 5,000,000 (46.4MB remain)
Create 5,000,000 (437.3MB used)
Delete 5,000,000 (60.2MB remain)
Create 5,000,000 (436.6MB used)
Delete 5,000,000 (68.9MB remain)
Create 5,000,000 (437.3MB used)
Delete 5,000,000 (72.3MB remain)
Create 5,000,000 (436.7MB used)
Delete 5,000,000 (78.1.9MB remain)

Note... after each "deleting" all of the nodes, slightly more memory is leaked than the previous cycle.

So, any thoughts as to what this might be? I assumed that by deleting or freeing a structure, it dealt with all of its members as well, but should I be doing something with them before I just free/delete the structure?

btw, any constructive criticism is welcome about any other portion of the code, if anyone has any pointers, please lemme hear 'em.

Thanks, Joseph.