Thread: Doubly Linked List Deletion Issue

  1. #1
    Registered User
    Join Date
    May 2007
    Posts
    15

    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.

  2. #2
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    1. You should change the code to create a class and remove usage of all Globals
    2. Your indent Idea is very strange - after deleting some node in the middle the idents will not be continues, after inserting new node - you will have duplicated indents
    3. DeleteNodeStart does not deletes node if it is last node in the list
    4. DeleteNodeEnd does not resets the *Forward pointer for the last node - it still points to the already deleted node
    5. When Start is resetted to NULL and is still pointing to the deleted node

    This can result in crashes, when nodes will be used from this pointers...

    Hope now - you have some issues to start with
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  3. #3
    Registered User
    Join Date
    May 2007
    Posts
    15
    Quote Originally Posted by vart View Post
    1. You should change the code to create a class and remove usage of all Globals
    Well, as I mentioned, this is a simplified revision of my code (which was encapsulated within a class with only a few necessary global variables)

    Quote Originally Posted by vart View Post
    2. Your indent Idea is very strange - after deleting some node in the middle the idents will not be continues, after inserting new node - you will have duplicated indents
    Well, I do have working node insertion and random delete code, this was a rewrite of previous code, and so I haven't even gotten to the point of testing that particular function yet, I should have just left it out for simplicity, but thanks for pointing it out.

    Quote Originally Posted by vart View Post
    3. DeleteNodeStart does not deletes node if it is last node in the list
    Typically I would leave the first node intact since I would attach various bits of meta-data to it (required code not present), so that isn't a biggie. But since you mention it, for this purpose I think it is appropriate to get rid of it.

    Quote Originally Posted by vart View Post
    4. DeleteNodeEnd does not resets the *Forward pointer for the last node - it still points to the already deleted node
    We'll since it isn't a circularly linked-list I can just leave it as such, I don't have any need to ever call it, all it would do is take a few more cpu cycles to reset it per delete, and I'd rather just leave it out.

    Quote Originally Posted by vart View Post
    5. When Start is reset to NULL and is still pointing to the deleted node
    Hmm... I'll check that out, thanks.


    I've tried to further simplify the code and I removed several of the functions unrelated to the problem (I've also altered my method for deconstructing the list), but the problem still remains:

    Code:
    unsigned long NodeCount;
    
    struct Node
    {
    	Node *Forward, *Backward;
    };
    Node *NodeStart, *NodeEnd, *NodeRecent;
    
    Node* CreateNode(void)
    {
    	Node *new_node = new Node;
    	if(NodeStart==NULL)
    	{
    		if(NodeCount==0)
    		{
    			NodeStart = new_node;
    			NodeStart->Backward=NULL;
    			NodeEnd=NodeStart;
    		}
    	}
    	else
    	{
    		(NodeEnd->Forward) = new_node;
    		(new_node->Backward) = NodeEnd;
    	}
    	(new_node->Forward) = NULL;
    	NodeEnd = new_node;
    	NodeRecent = new_node;
    	NodeCount++;
    	return (new_node);
    }
    
    void CreateNodes(unsigned long n){for(n;n>0;n--){CreateNode();}}
    
    void DeconstructList(void)
    {
    	Node* temp;
    	while(NodeEnd!=NULL)
    	{
    		temp=(NodeEnd->Backward);
    		delete NodeEnd;
    		NodeEnd=temp;
    	}
    }
    
    int main()
    {
    	cout << "Creating Nodes..." << endl;
    	CreateNodes(5000000);
    	getchar();
    
    	cout << "Deconstructing list..." << endl;
    	DeconstructList();
    	getchar();
    	return (0);
    }
    With this code, I am still left with roughly a 14.8&#37; memory leak.... and I don't see it

    Any further ideas?
    Last edited by josephjah; 07-21-2007 at 01:06 AM. Reason: Typo

  4. #4
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    Now you're not resetting NodeCount in DeconstructList(). So if you called CreateNodes() a second time, this if() would not be true:
    Code:
    		if(NodeCount==0)
    I don't see any functions that are called in main() in your first post which would cause a memory leak. It may be the case that some memory isn't actually reclaimed until the program finishes.

  5. #5
    Registered User MacNilly's Avatar
    Join Date
    Oct 2005
    Location
    CA, USA
    Posts
    466
    Run "valgrind --tool=memcheck" myprog

  6. #6
    Registered User
    Join Date
    May 2007
    Posts
    15
    Swoopy, Updated, thank you. Do you know of any way to reclaim this memory myself rather than relying on windows to do it for me? because if I have this running for possibly days without exiting I will have cycled through far more than 5 million nodes and I will have several hundred MB of memory locked up that I can't use. [or that other apps can't use]

    MacNilly, I don't have access to a linux box currently But thanks anyway

  7. #7
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    >Do you know of any way to reclaim this memory myself rather than relying on windows to do it for me?
    It might only reclaim it when another application needs a large amount of memory. Or it might reclaim it after a certain period of time. You could try starting another memory intensive appication after you've started the program, and see if this affects the memory usage that task manager displays. Something like a photo editor, or maybe a 3D game.

  8. #8
    Registered User
    Join Date
    Jul 2007
    Posts
    36
    Sometimes windows doesn't delete memory until the program is closed. This is true to arrays of pointers which point to memory.

  9. #9
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    But allocating and deallocating in cycle the same amount of memory should not increase the memory usage of the process... All iterations should use the same already retreived from the OS memory on the first iteration instead of asking for more...
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    It's "Destruct" not "Deconstruct"! Haven't you ever seen "Mission Impossible"...

    Why the excessive bracketing: ((target->Forward)->Backward)=(target->Backward);
    None of those brackets are required. You certainly don't need to bracket lvalues!

    In the last code sample you posted, nothing is initialised at all! I can't spot the problem because it's a case of can't see the forest for the trees. (too many bugs to find the bug)
    For that matter, nothing is reset after deletion either, which is just as important.

    Where in the list is CreateNode supposed to be sticking the new node? At the end I presume? It is unclear though. If we know what it is supposed to be doing then it will be easier to see if it is correct. Picking better function names or adding comments would make it clearer.

    NodeRecent serves no useful purpose - should get rid of it.

    (void) is not required in the function parameter list in C++.

    Looks like a lot more code in general than there should be for this. E.g. Why two if's in CreateNode? What if one is true and the next is false! Goes back to the uninitialised variables perhaps...
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  11. #11
    Registered User
    Join Date
    May 2007
    Posts
    88
    Is std::list<> not good enough?

  12. #12
    Registered User
    Join Date
    May 2007
    Posts
    15
    Swoopy, I tried your suggestion, but it doesn't seem to work, when I start up a program to try to steal back some memory it has no effect, (or simply begins to write to my page file when it has consumed all of my system's memory)... I am doubting it is any issue with windows, because it releases all of the memory upon exit, it is how I deleting nodes that is the problem... I am not doing something right.

    Quote Originally Posted by iMalc
    Why the excessive bracketing: ((target->Forward)->Backward)=(target->Backward);
    None of those brackets are required. You certainly don't need to bracket lvalues!
    Lol. Yes, I know... but sometimes since I have lines stretching across the screen and it helps to break them up with paranthesis, and I just end up using it throughout the program.

    Quote Originally Posted by iMalc
    In the last code sample you posted, nothing is initialised at all! I can't spot the problem because it's a case of can't see the forest for the trees. (too many bugs to find the bug)
    For that matter, nothing is reset after deletion either, which is just as important.

    Where in the list is CreateNode supposed to be sticking the new node? At the end I presume? It is unclear though. If we know what it is supposed to be doing then it will be easier to see if it is correct. Picking better function names or adding comments would make it clearer.
    I don't see what you mean. The list begins at NodeStart, and ends on NodeEnd, I have Forward and Backward links throughout the list for navigation. And, I am deleting nodes the same way I have seen in *every single* LL tutorial/reference I have ever seen, using free()/delete.

    As for comments, I figured the operation was pretty straight forward here... if you can't understand my deletion function without comments, you can't help me. Simple as that.

    Quote Originally Posted by iMalc
    Picking better function names or adding comments would make it clearer
    Better function names... *laughs* what would you suggest? Those are pretty easy buddy.

    Quote Originally Posted by iMalc
    NodeRecent serves no useful purpose - should get rid of it.
    NodeRecent does serve a purpose, just the functions that use it are not present in the code posted.

    Quote Originally Posted by iMalc
    (void) is not required in the function parameter list in C++.
    Thanks, I'll be sure to keep that out from now on.

    Quote Originally Posted by UMR_Student
    Is std::list<> not good enough?
    Nope. I need a little more flexibility
    Last edited by josephjah; 07-21-2007 at 07:55 PM. Reason: Typo

  13. #13
    Registered User
    Join Date
    May 2007
    Posts
    15
    Quote Originally Posted by vart
    But allocating and deallocating in cycle the same amount of memory should not increase the memory usage of the process... All iterations should use the same already retreived from the OS memory on the first iteration instead of asking for more...
    Yeah... That's what's puzzling me, I don't see anything else I could release.

    It seems that I am leaving something behind in each node that is roughly 10-15% of the size of the node, and when I perform a second cycle the memory is still unusable since it is still taken up.

  14. #14
    Registered User
    Join Date
    May 2007
    Posts
    15
    Quote Originally Posted by http://www.yolinux.com/TUTORIALS/C++MemoryCorruptionAndMemoryLeaks.html
    Inheritance, polymorphism and the wrong delete:

    BaseClass* obj_ptr = new DerivedClass; // Allowed due to polymorphism.
    ...
    delete obj_ptr; // this will call the destructor ~Parent() and NOT ~Child()

    If you are counting on the destructor to delete memory allocated in the constructor beware of this mistake as it will cause a memory leak. Use a virtual destructor to avoid this problem. The ~BaseClass() destructor is called and then the destructor ~DerivedClass() is chosen and called at run time because it is a virtual destructor. If it is not declared virtual then only the ~BaseClass() destructor is called leaving any allocated memory from the DerivedClass to persist and leak. This assumes that the DerivedClass has extra memory allocated above and beyond that of the BaseClass which must be freed.

    The same ill effect can be achieved with a C style cast to a class of less scope which will dumb down the destructor to that which may not execute all the freeing of the original class. A C++ style dynamic cast may prevent this error as it will recognize the loss of translation and not allow the cast to take place resulting in a traceable crash rather a tough to find memory leak.
    I'm thinking this might have something to do with it, but I don't entirely understand what they mean... I'm going to keep trying new things to see if I can get this to work, but as of now the prospect looks grim.

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by josephjah View Post
    I don't see what you mean. The list begins at NodeStart, and ends on NodeEnd, I have Forward and Backward links throughout the list for navigation. And, I am deleting nodes the same way I have seen in *every single* LL tutorial/reference I have ever seen, using free()/delete.
    Right, you don't see what I mean at all. What I mean is that none of your pointers or counters are being set to NULL or zero before adding items to the list. That means that they would begin with a random address. Okay your real program more likely has them initialised, but we can't tell that from a mocked-up code snippet. You need to do your best to make sure that what you post is what you have actually been running. Setting the NodeCount back to zero afterwards is also important because otherwise you can't reuse the list properly.

    As for comments, I figured the operation was pretty straight forward here... if you can't understand my deletion function without comments, you can't help me. Simple as that.

    Better function names... *laughs* what would you suggest? Those are pretty easy buddy.
    I understand your deletion just fine. That much is very straight forward. The problem is with CreateNode and CreateNodes. Again I know this isn't the real program, but if it were, the function name and signature say nothing about where those nodes go (what points to them), nor does it say in what order they are linked. a name like push_back tells you that the node goes on the back end of the list; CreateNode does not. It is also obvious what list it goes into because push_back is a member function. Yes your other names aren't really that bad, once you correct your spelling of destruct.


    NodeRecent does serve a purpose, just the functions that use it are not present in the code posted.
    I figured as much, but when posting a snippet that reproduces a problem it is best to trim out as much irrelevant stuff as possible. Not just for our benefit, but because it may also help you to more clearly see the problem.

    Nope. I need a little more flexibility
    Really?! I'm intriegued as to how any home-baked list could be more flexible that a std::list! Care to elaborate?
    Last edited by iMalc; 07-21-2007 at 09:56 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked List Not Saving Value as Int
    By bar338 in forum C Programming
    Replies: 4
    Last Post: 05-04-2009, 07:53 PM
  2. WIP Borland C Doubly linked list
    By BCWarrior in forum C Programming
    Replies: 41
    Last Post: 09-25-2007, 12:06 AM
  3. doubly linked list error.
    By noob2c in forum C++ Programming
    Replies: 12
    Last Post: 09-01-2003, 10:49 PM
  4. Contest Results - May 27, 2002
    By ygfperson in forum A Brief History of Cprogramming.com
    Replies: 18
    Last Post: 06-18-2002, 01:27 PM
  5. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 09:07 PM