Skip to main content
gamedev.net
🔒 Locked

delete

Started by Hamlet 9 replies 500+ views
Original Post
Hamlet
Hamlet
I am trying to do this with a linked list: 
  
struct node
{
    typedef int data_type;
    data_type data;
    node* next;

}

int main()
{

node *head;
head = new node;
head->data = 10;
head->next = next_node;

delete head;

}
If i delete head like this does it get rid of data and next as well or does it only get rid of the memory address and leave the info floating out there with nothing poining to it( a memory leak )? or do i have to do this: delete * head; Thanks for any help mates!
"... thats the rub...
CWizard
CWizard
You will suffer a memory leak if you do so. You''ll need to iterate through your list and delete each node individually. The last suggestion you made won''t work either.

---------------------------------------------
"VB is a disease"
Hamlet
Hamlet
so should i do something like:

delete head->date;
delete head->next;

As if it was the destructor for a class?
"... thats the rub...
CWizard
CWizard
Hmmm, I think I missread your code somewhat. Your code does work as it is, and do not cause a memory leak (hmm, you set the next to be next_node, that isn't declared here, so perhaps it do leak). But if you added more nodes, and just deleted the head node, none of the others would be deleted.

An example:

int main()
{
    node *pHead;
 
    // Create a linked list
    head = new node;
    head->next = new node;
    head->next->next = new node;
    head->next->next->next = new node;
    // you get the idea...
 
    // Delete all nodes (not very nice done, but should work)
    node *pNode;
    while(pNode = pHead) {
        pHead = pNode->next;
        delete pNode;
    }
}


EDIT: Corrected some serious flaws
---------------------------------------------
"VB is a disease"

[edited by - CWizard on October 26, 2002 6:24:13 PM]
Hamlet
Hamlet
Ok ill mess with it some more thanks for the help!
"... thats the rub...
CWizard
CWizard
quote:
Original post by Hamlet
so should i do something like:

delete head->date;
delete head->next;

As if it was the destructor for a class?
Is this for a class? Yeah, you''ll need to to individually delete any "newed" objects besides the node itself. But, unless you are deleting backwards, you shouldn''t delete node->next, as then you wouldn''t be able to delete its next, and so on...



---------------------------------------------
"VB is a disease"
CWizard
CWizard
As you seem interested in study of this subject, i''ll give you my double linked class, which isn''t really finished, and some OO-fanatics would probably flame me because it isn''t templated. Use it at will, but I would recommend only to study it.

File: CDoubleLinkedList.h

  //=============================================================================

#ifndef	_CDOUBLELINKEDLIST_H
#define _CDOUBLELINKEDLIST_H
//=============================================================================

 
/*
CLASS: CDoubleLinkedList
========================
A minimal implementation of a simple double linked list class, capable of
keeping one pointer to an object or anything of your choice.
 
Usage:
	Create an instance of the object, which will serve as the list''s "base".
	To add a "Node", call AddNode() with a pointer to your data. You will be
	returned a structure of type CDoubleLinkedList::NODE, which holds the data
	pointer in its member pObject. The Node will be inserted last in the list.
	To remove a Node, call RemoveNode() with a pointer to the NODE strucure.
	To search the list, follow this simple procedure:
	- Initialize a NODE pointer with the result of FirstNode(), ie:
		CDoubleLinkedList::NODE *pNode = List->FirstNode();
	- Have a while loop, which loops as long as pNode is true, and have pNode
	  loaded with the return value of the return value of NextNode(), ie:
		while(pNode) {
			// ...
			pNode = List->NextNode(pNode);
		}
	- Find the Node''s data from pNode->pObject.
	- Another, complete, example is this: (assuming data is string pointer)
		CDoubleLinkedList::NODE *pNode;
		if(pNode = List->FirstNode()) do {
			printf("Node data: %s\n", (char *)pNode->pObject);
		} while(pNode = List->NextNode());
	Note, however, that no NODEs our the data pointing by them will be freed,
	you must search and free all NODEs yourself.
	If your data is a structure of type SOMETHING, you can free everything so:
		CDoubleLinkedList::NODE *pNode;
		while(pNode = List->FirstNode()) {
			if(pNode->pObject) delete (SOMETHING *)pNode->pObject;
			List->RemoveNode(pNode);
		}
 
Future:
	- Enable full positioning when Adding a Node
	- Adding method for moving a Node, relative to another Node
	- Callback Method(s) for sorting the mode
	- Searching Method(s) for finding a particualr pObject value
	- Callback searching method
	- DestroyList() method with callback function
*/
 
 
class CDoubleLinkedList {
 
public:
	// A Node, which is used by most methods

	struct NODE {
		NODE	*pNextNode;
		NODE	*pPrevNode;
		void	*pObject;
	};
	 
	// Constructor/Destructor methods

	CDoubleLinkedList();
	~CDoubleLinkedList();
 
	// Adding/Removing methods

	NODE * AddNode(void *pObject, int nPos);
	void RemoveNode(NODE *pNode);
 
	// Scanning methods

	inline NODE * FirstNode();
	inline NODE * LastNode();
	inline NODE * NextNode(NODE *pCurrentNode);
	inline NODE * PrevNode(NODE *pCurrentNode);
 
private:
	// Base data

	NODE	*pFirstNode;
	NODE	*pLastNode;
	int		nNodeCount;
};
 
//=============================================================================

#endif	// _CDOUBLELINKEDLIST_H


File: CDoubleLinkedList.cpp

  
#include "CDoubleLinkedList.h"
 
 
CDoubleLinkedList::CDoubleLinkedList()
{
	// Clear all vars

	this->pFirstNode	= 0;
	this->pLastNode		= 0;
	this->nNodeCount	= 0;
}
 
CDoubleLinkedList::~CDoubleLinkedList()
{
	NODE	*pNode;
 
	// Delete all nodes

	while(pNode = this->FirstNode())
		this->RemoveNode(pNode);
}
 
CDoubleLinkedList::NODE * CDoubleLinkedList::AddNode(void *pObject, int nPos)
{
	NODE	*pNode	= new NODE;
 
	// Initialize node, and add the object/data pointer

	pNode->pNextNode	= 0;
	pNode->pPrevNode	= 0;
	pNode->pObject		= pObject;
 
	// If the first node, add stuff

	if(!this->nNodeCount) {
		this->pFirstNode	= pNode;
		this->pLastNode		= pNode;
	}
	// If requested to put it first we do that

	else if(nPos == 0) {
		pNode->pNextNode	= this->pFirstNode;
		this->pFirstNode	= pNode;
	}
	// Otherwise we put it last

	else {
		pNode->pPrevNode	= this->pLastNode;
		this->pLastNode		= pNode;
	}
 
	// Increase number of node

	this->nNodeCount++;
 
	// Give back the new node

	return pNode;
}
 
void CDoubleLinkedList::RemoveNode(NODE *pNode)
{
	// If we have a next, we need to change its prev. Otherwise this was the last and a new one is

	if(pNode->pNextNode)
		pNode->pNextNode->pPrevNode	= pNode->pPrevNode;
	else
		this->pLastNode		= pNode->pPrevNode;
	// If we have a prev, we need to change its next. Otherwise this was the first and a new one is

	if(pNode->pPrevNode)
		pNode->pPrevNode->pNextNode	= pNode->pNextNode;
	else
		this->pFirstNode	= pNode->pNextNode;
 
	// This Node is now unlinked from the list, and we can delete it

	delete pNode;
 
	// Decrease number of nodes

	this->nNodeCount--;
}
 
inline CDoubleLinkedList::NODE * CDoubleLinkedList::FirstNode()
{
	return this->pFirstNode;
}
 
inline CDoubleLinkedList::NODE * CDoubleLinkedList::LastNode()
{
	return this->pLastNode;
}
 
 
inline CDoubleLinkedList::NODE * CDoubleLinkedList::NextNode(CDoubleLinkedList::NODE *pCurrentNode)
{
	return pCurrentNode->pNextNode;
}
 
inline CDoubleLinkedList::NODE * CDoubleLinkedList::PrevNode(CDoubleLinkedList::NODE *pCurrentNode)
{
	return pCurrentNode->pPrevNode;
}


---------------------------------------------
"VB is a disease"
Beer Hunter
Beer Hunter 

  
#ifndef	_CDOUBLELINKEDLIST_H

#define _CDOUBLELINKEDLIST_H

#include <list>

template <class T> class CDoubleLinkedList : public std::list<T> { };

#endif //_CDOUBLELINKEDLIST_H

CWizard
CWizard
I know I really should learn using templates, but I like rolling my own; I always have. Anyway, nice way to, in a single line, make all my "hard" work worthless

---------------------------------------------
"VB is a disease"
Oluseyi
Oluseyi
quote:
Original post by CWizard
...some OO-fanatics would probably flame me because it isn''t templated.

There is no relation between OO and templates. Templates are a mechanism for generic programming, a trait that is desirable in most code, including object-oriented.
CWizard
CWizard
quote:
Original post by Oluseyi
There is no relation between OO and templates. Templates are a mechanism for generic programming, a trait that is desirable in most code, including object-oriented.
Yeah, I know. I thought of refrasing that, but let it be. Although, I think it is correct that most of the coders I was refering to, "would probably flame me because it isn''t templated"


---------------------------------------------
"VB is a disease"

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.