remove node in doubly linked class in C++

Question

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?

You should add driver code that creates a list, calls the remove method and demonstrates the issue. Also provide the information you got from debugging. — trincot, Dec 10 '22 at 12:00
No, that will not be appreciated by the community and will lead to downvotes. I edited your question more... But still you should focus on the version of the main code that produces the problem. Now you have presented a sequence that seems to work, and then say something about replacing a call, ... but that is not clear. Better present the **smallest** possible sequence of calls that produces the problem, and only that. — trincot, Dec 10 '22 at 12:35
So you mean only do calls to the remove that causes the problem and shrink the test list right? — Yusuf Halim, Dec 10 '22 at 12:46
Yes, this looks better. But now it will take some time to get it reopened — trincot, Dec 10 '22 at 12:57
What's wrong with my code [is not a real question](https://meta.stackoverflow.com/questions/284236/why-is-can-someone-help-me-not-an-actual-question). You should make an effort to [debug your code](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems). You'll have a much better chance to write a better question and get more meaningful answers. — Evg, Dec 10 '22 at 15:18
@Evg, it is clear what they ask. The "what's wrong" comes in a context of a clear question of where the desired behaviour is known, the wrong behaviour is demonstrated, and the asker has provided their attempt. It might not be a good attempt, and effort may be lacking, but all that is relative. This question is narrow enough, and can be answered. — trincot, Dec 10 '22 at 16:04
@trincot There is no specific question about posted code, it is not clear what kind of difficulties OP has and what kind of help OP needs. "What's wrong with my code" together with no demonstrated debugging effort is not a good question for SO and we should not encourage people to post such questions. The link above clearly explains why. — Evg, Dec 10 '22 at 16:21
@Evg, I will not agree, but I'm currently trying a new method an will update this question if it still didn't work — Yusuf Halim, Dec 10 '22 at 18:16
@trincot, I appreciate your help and effort to reopen the question — Yusuf Halim, Dec 10 '22 at 18:30
@trincot found the issue within my question and gave me the answer. However I didn't use his exact code, I only needed the concept to know what I did wrong. — Yusuf Halim, Dec 10 '22 at 19:04
*and that I'm just here for the answer without trying* - Then let me ask you why you shared no details about your attempts? We don't have a crystal ball and can only see what you shared with us in your question. The only thing that I see right now is a bunch of code and the question "what's wrong with it". — Evg, Dec 11 '22 at 00:31
If you actually look at the code, you can see a REMOVE function and the tests of the REMOVE function with its outputs. So I don't know why you're arguing right now. the extra code is to make others understand that I made my own Node class — Yusuf Halim, Dec 11 '22 at 01:00

score 1 · Accepted Answer · answered Dec 10 '22 at 18:44

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

Michael Schmitt · Answer 2 · 2022-12-10T14:18:14.060

0

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;

edited Dec 10 '22 at 14:18

answered Dec 10 '22 at 11:25

Michael Schmitt

149
9

The assignment doesn't want a head ptr – Yusuf Halim Dec 10 '22 at 12:13
The current pointer always points to the number where it is was first created – Yusuf Halim Dec 10 '22 at 12:14
It might, if you would assign it in the constructor. Like MyList::MyList(Node *currentPrt_) : currentPtr(currnetPrt_) {} – Michael Schmitt Dec 10 '22 at 12:20
I was asked to make the constructor to always assign currentPrt to nullptr – Yusuf Halim Dec 10 '22 at 12:23
i forgot to update my constructor, I updated it now but nothing changes – Yusuf Halim Dec 10 '22 at 12:24
Is it possible to show an example? do I need to create a new Node to hold the values and then reassign them after I delete? – Yusuf Halim Dec 10 '22 at 12:29
Get the successor and predecessor of the node to delete and set them as the predecessor and successor of each other, if they are not null. It is your assignment, not mine ;) – Michael Schmitt Dec 10 '22 at 12:37
Ok it works but not with 7 or 5, How do you check if a node has a certain value before doing any operations? does my iteration while loop look correct? – Yusuf Halim Dec 10 '22 at 18:44
Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/250315/discussion-between-michael-schmitt-and-yusuf-halim). – Michael Schmitt Dec 10 '22 at 18:48

remove node in doubly linked class in C++

2 Answers2