CODEWITHSUNDEEP
c++linked-list
Connor Black
Connor Black

Reputation: 7181

C++ deleting node from middle of list

So I'm in a summer OO class and we need to write a function to delete a node from the middle of a linked list. I'm really close but there are a few problems. My code iterates through the linked list successfully but there is trouble actually deleting the node once the loop finds the node. Here's my function so far:

template< class NODETYPE >
bool List< NODETYPE >::removeMiddle( NODETYPE &value, int i )
{
    ListNode <NODETYPE> * tempPtr = firstPtr;
    ListNode <NODETYPE> * prevPtr ;
    int counter=1;

    if ( isEmpty() )
        return false;
    if (i <= 0)
        return false;

    while (tempPtr != 0 && counter < i){
        counter++;
        if ( firstPtr == lastPtr )
        firstPtr = lastPtr = 0;
    else
        firstPtr = firstPtr->nextPtr;
            prevPtr = tempPtr;
            tempPtr = tempPtr->nextPtr;
        }

        if (counter == i){
            value = tempPtr->data;  // data being removed
            delete tempPtr;
        }
    }

    return true;
    RecordCounter--;
}

Upvotes: 0

Views: 973

Answers (3)

Cheers and hth. - Alf
Cheers and hth. - Alf

Reputation: 145457

You're forgetting to adjust the links in the list. The node is still there after the delete, but now it's invalid. Ooops!

This function is useful:

NODETYPE* unlink( NODETYPE*& pNode )
{
    NODETYPE* const result = pNode;

    pNode = pNode->nextPtr;
    return result;
}

Call it passing in the nextPtr that points to the node you want to delete. You get back a pointer to the node, with the list relinked so the node is no longer in the list. Now you can delete that node.

What to do if you only have a pointer directly to the node that you want to delete, and the list is singly linked? Well, Donald Knuth once asked that as an exercise in his The Art of Computer Programming (if I recall correctly). One solution is to swap the data with the next node, then delete the next node.

Upvotes: 0

Jonathan Houston
Jonathan Houston

Reputation: 171

My first guess without any more specifics is that you are not maintaining the list integrity. Though I'm very rusty at C++.

You are removing the tempPtr and tracking the prevPtr... but not re-linking the two halves of the list after the delete.

prevPtr->nextPtr = tempPtr->nextPtr

Upvotes: 2

Luchian Grigore
Luchian Grigore

Reputation: 258698

You forgot to change the previous node so that it no longer points to the node you delete.

You want something (largely) similar to:

if ( counter == i-1 ) //next node is the one you want to delete
{
    aux = tempPtr->nextPtr->nextPtr;   //retain next next node
    delete tempPtr->nextPtr;           //delete next node
    tempPtr->nextPtr = aux;            //current node now points to the node after the deleted one
}

Upvotes: 3

Related Questions