C++ Linked Lists delete function

boyracer87

Hey guys,

Iv got a project to do for collage and im trying to make a delete function but i keep getting this message:

"error C2440: 'delete' : cannot convert from 'class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >' to ''
No user-defined-conversion operator available that can perform this conversion, or the operator cannot be called."

Heres the piece of code im using:

[HTML]
void del(entry * H,string Name)
{ entry*pos=H;
while (pos != NULL){
if(pos->data==Name){
delete pos->data;
}else{
pos=pos->next;
}

}

}[/HTML]

Anyone got any ideas as to whats wrong?

Thanks in advance,
Ray

theexis

If you're removing the entry from the list, you should delete pos itself (delete pos;). Looks like your data member is something like a string/wstring: this manages its own memory so there is no need to try and clean it up as you're doing.

Smellyirishman

Yeah, just deconstruct the pos node (entry) if you find it.

So when you find it

NodePreviousToPos->next = pos->next //Node previous to the one you want to delete now points to the node after the one you wish to delete)
Pos->~entry(); //Deconstruct pos

boyracer87

Thanks guys,

it works but it will not delete the first item in the list because there is no previous. iv hacked and hacked at it but i still can't get it to work. heres the code as it stands now:

[HTML]
void del(entry * H,string OldName)
{ entry*pos=H, *prev;
while (pos != NULL){
if(pos->data==OldName){
prev->next=pos->next;
pos->~entry();
}else{
prev=pos;
pos=pos->next;

}
}
}
[/HTML]

Ray

Smellyirishman

void del(entry * H,string OldName)
{
	entry*pos=H, *prev;
	while (pos != NULL)
	{
		if(pos->data==OldName)
		{
			if(pos == firstEntry)
			{
				firstEntry = pos->next;
				pos->~entry();
			}
			else
			{
				prev->next=pos->next;
				pos->~entry();
			}
		}
		else
		{
			prev=pos;
			pos=pos->next;
		}
	}
}

Something rough like that should do the trick, you may need to swap some things around depending on how you represent the first node in the list but the basic idea is there.
Of course, it all depends on some other basics like if you represent the last node in the list or if you always point to null if there is nothing to follow.

PhantomBeaker

boyracer87 wrote:

Thanks guys,

it works but it will not delete the first item in the list because there is no previous. iv hacked and hacked at it but i still can't get it to work.
[/HTML]

the way I tend to handle linked lists is that if it's a singly linked list I create an empty node that I call my head. So an 'empty' list still has one node... the head. Then you neatly sidestep the sort of issues you're finding... i.e. you have less special cases for your del function.

Similarly if I have a doubly linked list, I put on a tail node for exactly the same reason.

Hope that helps a bit.

dob99

In general, you shouldn't call destructors directly. The only time you would really do this is if you were handling the memory allocation yourself (by providing your own new operator). Explicitly calling an object's destructor does not free the memory used by that object. So, in the code above, the entry object being deleted still exists, although it's members don't.

Istead of

pos->~entry();

you should simply do

delete pos;

See section 10.4.11 in Stroustrup's C++ Language for more details.

Also, the compiler error you were getting originally is a bit misleading. The problem is that entry::data is not a pointer, so you can't delete it - it gets destroyed when it goes out of scope (i.e. when the object containing it is destroyed).

boyracer87

Yea, the deconstruction was just making gaps in the list. if i deleted the first item then there would be a gap at the front of the list. then when i went to put another item in, that gap would stay and the new item would go in before it.

But now im back to the problem of deleting the first in the list. i can go through the delete command but when i try and list the items, it will crash. i am asumming it is a problem with the head.

Heres the new bit of code:

void del(entry * H,string OldName)
{	entry*pos=H, *prev, *firstEntry=H, *first;
	firstEntry=pos;
	while (pos != NULL){
		if(pos->data==OldName){
			if(pos == firstEntry){
				firstEntry = pos->next;
				delete pos;
				first=firstEntry;
				first=H;
				break;
			}else{
				prev->next=pos->next;
				delete pos;
				break;
			}
		}else{
			prev=pos;
			pos=pos->next;
		}
	}
}

dob99

Since, you're passing in the pointer to the first item (H) as the list, you should return a pointer to entry, since you may be deleting H. Essentially, you'll be passing back a pointer to the list from the del function. However, you must make sure to update your local variable that points to the list (see below). If you delete H, but don't reinitialise the variable you're passing in (as H), the pointer will be invalid and the program could well crash!

The following should work:

entry* del(entry* H, string Name)
{
	entry* pos=H, *prev;
	while (pos != NULL)
	{
		if(pos->data == Name)
		{
			if(pos == H)
			{
				H = pos->next;
			}
			else
			{
				prev->next = pos->next;
			}
			
			delete pos;
		}
		else
		{
			prev = pos;
			pos = pos->next;
		}
	}
	
	return H;
}

extern entry* list; // assume it has some values in it

list = del(list, "Hello");