Delete a node from a linkedlist

[mathon]

hello,

i thought i create a new topic for that because i deal with a certain
problem. I have implemented all methods for a LinkdeList (for my
sequence class) and tested all correct. Now i only have problems with
the remove method to delete a certain node from the list. my remove
method looks like this:

void sequence::remove_current( )
{
	if(!(is_item()))
		return;

	node *target_ptr;

	if(cursor != tail_ptr && many_nodes > 1)
	{
		cout << "Cursor != tail_ptr" << endl;
		target_ptr = cursor;
		cursor = cursor->link();
		precursor->set_link(cursor);
		delete target_ptr;
		node* cursor1;
		node* precursor1;
		for(cursor1 = head_ptr; cursor1 != NULL; cursor1 = cursor1->link())
		{
			precursor1 = cursor1;
		}
		tail_ptr = precursor1;
		--many_nodes;
		return;
	}

	else if(cursor == tail_ptr)
	{
		delete cursor;

		--many_nodes;
		return;
	}
	else if (many_nodes == 1)
	{
		list_head_remove(head_ptr);
		start();
		--many_nodes;
		return;
	}
}

So I used three cases - when the node should be deleted from the middle
of the list, when the node which should be deleted is at the end of the
list and when there is only one more node in the list. Unfortunately
the second case causes an error where the last node of the list should
be deleted:

The error occurs at the following statement:
delete cursor;

A popup window is displayed with the following error message:
Fehler:
Debug Assertion Failed!
Program: ...
File: dbgdel.cpp
Line: 52

Expression: _BLOCK_TYPE_IS_VALID(pHead->nBlockUse)

For information on how your program can cause an assertion failure, see
the Visual C++ documentation on asserts.

Why can't I use the delete cursor statement to delete the last node?
(the cursor points to the last node) - has anybody an idea how to
define that correctly. The specification says when the last node is
deleted the cursor pointer should be then null again, thats why i tried
it with delete cursor.

matti

PS: The cursor pointer points to the actual node of the list, the
precursor to the previous node and the tail_ptr points every time to
the last node.

 

[David Harmon]

On 21 Oct 2006 14:25:40 -0700 in comp.lang.c++, (e-mail address removed) wrote,

else if(cursor == tail_ptr)
{
delete cursor;

--many_nodes;
return;
}

Then tail_ptr and cursor both contain an invalid value, the former
pointer to the deleted node. The job here is half done.

Why can't I use the delete cursor statement to delete the last node?
(the cursor points to the last node) - has anybody an idea how to
define that correctly. The specification says when the last node is
deleted the cursor pointer should be then null again, thats why i tried
it with delete cursor.

I think it's because your code still has a few bugs in it and
deleting nodes leaves the list messed up. Write a simple function
to dump the list content, and call it after every operation... or at
lease after every delete while that is the part you are debugging.

Simplify!

By the way, "delete cursor" does not leave cursor as NULL, but
instead the old value is now invalid. Worse, tail_ptr has the same
value and is also invalid. "Invalid" here means you cannot
legitimately even compare it with another value.

In the simple case you write

cursor = cursor->link();

You should let the same line do that part also when deleting the
last node; not some special case. cursor->link() is NULL, the
assignment says in that case the result should be NULL, it all
works. I DO NOT mean to copy the line; I mean to fix the program
logic.

The loop,

for(cursor1 = head_ptr; cursor1 != NULL; cursor1 = cursor1->link())

is unnecessary and should be eliminated. The thing needed there is
something along the lines of
if(cursor == NULL)
tail_ptr = precursor;

Have you noticed yet that the only purpose of tail_ptr is to make
your task more difficult?

 

[gw7rib]

hello,

i thought i create a new topic for that because i deal with a certain
problem. I have implemented all methods for a LinkdeList (for my
sequence class) and tested all correct. Now i only have problems with
the remove method to delete a certain node from the list.

I don't know what people have against double linked lists - ie each
element of the list contains a pointer to the element before as well as
the element after. Then deleting a node can be done as:

if (N == first) first = N -> next; else N -> prior -> next = N -> next;
if (N == last) last = N -> prior; else N -> next -> prior = N -> prior;
delete N;

with no need for precursors, counts of elements, or anything like that.
Paul.