Delete a node from a linkedlist

Discussion in 'C++' started by mathon@gmx.at, Oct 21, 2006.

  1. Guest

    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:

    Code:
    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.
     
    , Oct 21, 2006
    #1
    1. Advertising

  2. David Harmon Guest

    On 21 Oct 2006 14:25:40 -0700 in comp.lang.c++, 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?
     
    David Harmon, Oct 22, 2006
    #2
    1. Advertising

  3. Guest

    wrote:
    > 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.
     
    , Oct 22, 2006
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    0
    Views:
    1,648
  2. Tohru Kao
    Replies:
    3
    Views:
    472
    Neil Masson
    Jul 14, 2003
  3. Tohru Kao
    Replies:
    1
    Views:
    428
    Chris
    Jul 8, 2003
  4. Tjerk Wolterink
    Replies:
    2
    Views:
    1,507
    Dimitre Novatchev
    Aug 24, 2006
  5. sangram
    Replies:
    16
    Views:
    2,081
Loading...

Share This Page