remove node in doubly linked class in C-CodePudding

I'm developing a doubly linked list class that uses a Node class in C .

I'm trying to make a remove function that deletes the desired node if it exist.

But if the value is greater than currentPrt it just exits without doing anything, and if it is less, it deletes the node and the program gets into an endless loop of printing weird values.

Code of Node class:

// Node.h

class Node {
public:

    explicit Node(int data = 0, Node *nextPtr = nullptr, Node *beforePtr = nullptr);

    int getData() const;

    void setData(int data);

    Node *getNextPtr() const;

    void setNextPtr(Node *nextPtr);

    Node *getBeforePtr() const;

    void setBeforePtr(Node *beforePtr);

    void print() const;

private:
    int data;
    Node *nextPtr;
    Node *beforePtr;


};

// Node.cpp

Node::Node(int data, Node *nextPtr, Node *beforePtr) : data(data), nextPtr(nextPtr), beforePtr(beforePtr) {}

int Node::getData() const {
    return data;
}

void Node::setData(int data) {
    Node::data = data;
}

Node *Node::getNextPtr() const {
    return nextPtr;
}

void Node::setNextPtr(Node *nextPtr) {
    Node::nextPtr = nextPtr;
}

Node *Node::getBeforePtr() const {
    return beforePtr;
}

void Node::setBeforePtr(Node *beforePtr) {
    Node::beforePtr = beforePtr;
}

void Node::print() const {

    cout << getData() << endl;

}

// MyList.h

class MyList {

public:
    MyList(Node *currentPrt = nullptr);

    void insert(int value);

    void print() const;


private:
    Node *currentPrt;

};

// MyList.cpp

MyList::MyList(){
    currentPrt = nullptr;
}

void MyList::insert(int value) {

    if(currentPrt == nullptr){
        currentPrt = new Node;
        currentPrt->setData(value);
        currentPrt->setNextPtr(nullptr);
        currentPrt->setBeforePtr(nullptr);

    }
    else{
        if(value > currentPrt->getData()){
            while (currentPrt->getNextPtr() != nullptr && currentPrt->getNextPtr()->getData() < value){
                currentPrt = currentPrt->getNextPtr();
            }

            Node *newPtr = new Node(value);
            newPtr->setNextPtr(currentPrt->getNextPtr());
            if (currentPrt->getNextPtr() != nullptr) // <---
                currentPrt->getNextPtr()->setBeforePtr(newPtr); // <---
            currentPrt->setNextPtr(newPtr);
            newPtr->setBeforePtr(currentPrt);
        }
        else{
            while (currentPrt->getBeforePtr() != nullptr && currentPrt->getBeforePtr()->getData() > value){
                currentPrt = currentPrt->getBeforePtr();
            }
            Node *newPtr = new Node(value);
            if (currentPrt->getBeforePtr() != nullptr){
                currentPrt = currentPrt->getBeforePtr();
                newPtr->setNextPtr(currentPrt->getNextPtr());
                currentPrt->getNextPtr()->setBeforePtr(newPtr); // <---
                currentPrt->setNextPtr(newPtr);
                newPtr->setBeforePtr(currentPrt);
            }
            else{
                currentPrt->setBeforePtr(newPtr);
                newPtr->setNextPtr(currentPrt);
            }
        }
    }




}

void MyList::remove(int value) {

    if (currentPrt != nullptr){
        if(value > currentPrt->getData()){
            while (currentPrt->getNextPtr() != nullptr && currentPrt->getBeforePtr()->getData() > value){
                currentPrt = currentPrt->getNextPtr();
            }
            if (currentPrt->getNextPtr()->getData() == value){
                delete currentPrt->getNextPtr();
            }
        }
        else{
            while (currentPrt->getBeforePtr() != nullptr && currentPrt->getBeforePtr()->getData() > value){
                currentPrt = currentPrt->getBeforePtr();
            }
            if (currentPrt->getBeforePtr()->getData() == value){
                delete currentPrt->getBeforePtr();
            }
        }
    }

}

void MyList::print() const {
    Node *ptr;
    ptr = currentPrt;
    while(ptr->getNextPtr() != nullptr){
        ptr = ptr->getNextPtr();
    }
    for (ptr; ptr != nullptr; ptr = ptr->getBeforePtr()){
        cout << ptr->getData() << endl;
    }

}

Main:

    MyList test;
    test.insert(5);
    test.insert(3);
    test.insert(7);
    test.insert(6);
    test.printAscending();
    std::cout<<endl;
    test.remove(7); // doesn't work but doesn't cause infinit print
    test.remove(5); // doesn't work but doesn't cause infinit print
    test.remove(6); // causes infinit prints
    test.remove(3); // causes infinit prints
    test.printAscending();

Ouput of only remove(5), remove(7):

if I put remove(6), (or 3), it gets into and endless print of numbers like this:

What is wrong with my remove implementation?

CodePudding user response：

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();
    }
}

CodePudding user response：

Let me suggest one thing: Since you assert that the list is ordered when inserting and store the first Node, you never have to search in the descending direction - only ascending.

In your implementation, you modify what you are pointing to, to the last inserted node. I don’t see the benefit of that. Just store the head of the list, and keep the other pointers as local variables. That will make things easier for you.

The bug in remove is probably that you don't reassign next an previous pointers from the successor and the predecessor of the deleted node. Calling delete just frees the memory. That is also why it behaves funny when trying to read unallocated memory.

Node* before = nodeToDelete->getBeforePtr();
Node* next = nodeToDelete->getNextPtr();
before->setNextPtr(next);
next->setBeforePtr(before);
delete nodeToDelete;