[Solved] remove node in doubly linked class in C++

by


You should not execute delete on a node that is still in the linked list. First you need to rewire any references to it. That is to say, the node before should have its nextPtr redirected to the node after the one that is to be deleted, and that node should have its beforePtr redirected as well.

Also, your code deletes the next node when it has found the matching value, and not that node itself. Moreover, there is no provision to delete more nodes in case the value occurs in more than one node.

I would also suggest to split the algorithm into two, as the part to delete the current node is useful as a method on its own.

So then we get this:

/* New method for deleting the current node. After deletion the current pointer 
 * will reference the next node if there is one, and otherwise the preceding 
 * one, or if there is none there either, it will be set to null -- the list is
 * empty then.
 */
void MyList::removeCurrent() {
    if (currentPrt == nullptr) return; // Nothing to do
    Node *temp = currentPrt;
    // Rewire the previous and next node so they reference eachother
    if (temp->getBeforePtr() != nullptr) {
        temp->getBeforePtr()->setNextPtr(currentPrt->getNextPtr());
    }
    if (currentPrt->getNextPtr() != nullptr) {
        currentPrt = currentPrt->getNextPtr();
        currentPrt->setBeforePtr(temp->getBeforePtr());
    } else {
        currentPrt = temp->getBeforePtr();
    }
    // Now the temp node is isolated and no more part of the list:
    // It is safe to delete it now.
    delete temp;
}

void MyList::remove(int value) {
    if (currentPrt == nullptr) return; // Nothing to do
    // Go to the right as long as the current node's data is smaller
    while (value > currentPrt->getData() && currentPrt->getNextPtr() != nullptr) {
        currentPrt = currentPrt->getNextPtr();
    }
    // Go to the left as long as the previous node's data is not smaller
    while (currentPrt->getBeforePtr() != nullptr && value <= currentPrt->getBeforePtr()->getData()) {
        currentPrt = currentPrt->getBeforePtr();
    }
    // Arrived at left most node that could have the value we look for.
    // Remove all occurrences
    while (currentPrt != nullptr && value == currentPrt->getData()) {
        removeCurrent();
    }
}

0

solved remove node in doubly linked class in C++