Removing a node from a doubly linked list

Question

I have looked at other threads here on the topic, but have no been able to use them to solve my problem.

this is the main class definition of a node in the linked list:

class node {  

public:

    // default constructor
    node() {name = ""; prev = NULL; next = NULL;};

    // default overloaded
    node(string s) {name = s; prev = NULL; next = NULL;};

    // item in the list
    string name; 

    // links to prev and next node in the list
    node * next, * prev;

};

the above is the node class definition, which is used in another class that generates a linked list. the linkedlist code was given to us, which we had to modify, so I know it works. I have gone through and tested the addition of new nodes in the doubly linked list to be working, and I am now working on removing nodes from this same doubly linked list.

The function to remove a node: http://pastebin.com/HAbNRM5W

^ this is the code I need help with, there is too much to retype

I was told by my instructor that the code that is the problem is the line 56, which reads:

tmp->prev = prev;

I am trying to set the link to the previous node to be the correct one. the case I am trying to work from with the similar if/else loops is whether or not the current node is the last item in the list. if it is the last item (aka curr->next = NULL), then don't set a link using curr->next and stop the loop iteration.

any help / ideas / suggestons / feedback will be greatly appreciated!

void linkedList::remove(string s) 
{
        bool found = false;
        node * curr = getTop(), * prev = NULL;
        node * tmp = new node();
        while(curr != NULL) 
        {
                 // match found, delete
                 if(curr->name == s) 
                 {
                        found = true;
                        // found at top
                        if(prev == NULL) 
                        {
                            node * temp = getTop();
                            setTop(curr->next);
                            getTop()->prev = NULL;
                            delete(temp);
                        } // end if
                        else 
                        {
                            // determine if last item in the list
                            if (curr->next = NULL) 
                            {
                                // prev node points to next node
                                prev->next = curr->next;
                                // delete the current node
                                delete(curr);
                            } // end if
                            // if not last item in list, proceed as normal
                            else 
                            {
                                // prev node points to next node
                                prev->next = curr->next;
                                // set the next node to its own name
                                tmp = prev->next;
                                // set prev-link of next node to the previous node (aka node before deleted)
                                tmp->prev = prev;
                                // delete the current node
                                delete(curr);
                            } // end else
                        } // end else
                    } // end if

                // not found, advance pointers
                if(!found) 
                {
                    prev = curr;
                    curr = curr->next;
                } // end if

                // found, exit loop
                else curr = NULL;
        } // end while

        if(found)
            cout << "Deleted " << s << endl;
        else 
            cout << s << " Not Found "<< endl;
} // end remove

zac, i need this method to remove the node of a doubly linked list in C++. i was told by my instructor that "tmp->prev = prev;" is NULL and that if i fixed this line, the code/program should work. i can't figure out what is null / why it is null so that i may fix it. thanks. — opticks
– opticks, Commented Nov 25, 2013 at 2:13
At the place where you are doing the deletes, it might be a good idea to do a printof the nameas for each of prev, curr and curr->next(if !null). Can be handy for sorting out pointer mixups. — RichardPlunkett
– RichardPlunkett, Commented Nov 25, 2013 at 2:20

ninMonkey · Accepted Answer · 2013-11-25 01:56:28Z

2

NULL should be replaced with nullptr

if (curr->next = NULL) { ...

That is an assignment, you want:

if (curr->next == nullptr) { ...

On line 47 I think you say: if prev == nullptr and next is not nullptr , but you use

prev->next = curr->next;

Which doesn't work since prev is nullptr.

answered Nov 25, 2013 at 1:56

ninMonkey

7,5418 gold badges41 silver badges72 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

opticks Over a year ago

thank you so much, i'm going to look into this asap. i am not sure how to change the implementation so that prev is actually the previous node and not a nullptr. i will make the nullptr changes right now.

opticks Over a year ago

I tried changing NULL to nullptr, but my code would not compile. the iostream library provides support for NULL, i don't know about nullptr.

opticks Over a year ago

as to the last part of your first reply: i am trying to say that there are three nodes: previous node, current node, and next node. if the next node (curr->next) isn't nullptr, then point the previous node to this node (prev->next = curr->next) and delete the current node. i am not sure how previous is defined as null/nullptr. i guess this is something that i need to fix.

ninMonkey Over a year ago

nullptr is added in c++11. I mentioned it because the question was tagged. If it doesn't work, then it means it's not set to compile c++11.

AFM · Accepted Answer · 2013-11-25 02:02:43Z

1

For your code, I suggest several things. Isolate the code to find the node with the name you are looking for. The remove method SHOULD only remove a doubly linked node, provided that it is given one.

I know that your remove method takes in a string parameter, but pass that to another function and have that function return the node you are looking for.

It should look something like this:

Node *cur = find("abcd");
Node *prev = cur->prev;
prev->next = cur->next;

Node *n = cur->next;
n->next = cur->prev;

cur->next = NULL; //or nullptr
cur->prev = NULL; //or nullptr

delete cur;

edited Nov 25, 2013 at 2:02

answered Nov 25, 2013 at 1:56

AFM

443 bronze badges

3 Comments

opticks Over a year ago

thank you for your suggestions, and feedback! i agree with you about what you are suggesting, namely rewriting the method/function, but the outline / entire program was given to us by the professor as a singly linked list, and we have to convert it for doubly linked. normally, if i was working on this myself, i would have done it the other way, but at this point it would be way more work than it's worth / i have time for.

AFM Over a year ago

@user2766542 - couldn't you just add in a private function? I don't think any professors would forbid additional private members. For your find function, you should use a for loop to automate the search (use ptr = ptr->next to iterate).

AFM Over a year ago

I don't know how you handle the destruction of the nodes, but I am assuming you delete the two pointers: prev and next. If this is the case, you must EXPLICITLY set the prev and next of the node you are trying to delete to NULL or nullptr. This is because if you don't, you risk deleting not only that node, but the nodes that is connected to it as well!

RichardPlunkett · Accepted Answer · 2013-11-25 02:00:18Z

0

Should look like:

prev->next = curr->next;
prev->next->prev = prev;
delete (curr);

answered Nov 25, 2013 at 2:00

RichardPlunkett

2,98817 silver badges14 bronze badges

4 Comments

opticks Over a year ago

wow, awesome, i had no idea i could do something like "prev->next->prev = prev;"

RichardPlunkett Over a year ago

The things is, you dont need a tmp at all. You need to make 2 assignment, the prev needs to skip the curr, and then, the thing it points at now, needs to point back at it.

RichardPlunkett Over a year ago

optionally this second one could be in an if statement, that check prev->next is now null_ptr, and that would reduce the need for the full separate end-of-list you have above.

opticks Over a year ago

that is what i was trying to w/o the tmp pointer, but didn't know how to do it. You need to delete the node in the middle, and make sure the ->next of the previous, and ->prev of the next point to each other.

Zac Howland · Accepted Answer · 2013-11-25 03:23:22Z

I got lost in all your different conditionals. All you need to do is this:

void linkedList::remove(const std::string& s)
{
    node* current = getTop(); // get head node
    while (current != nullptr) // find the item you are trying to remove
    {
        if (current->name == s)
        {
            break; // when you find it, break out of the loop
        }
    }

    if (current != nullptr) // if found, this will be non-null
    {
        if (current->prev) // if this is not the head node
        {
            current->prev->next = current->next;
        }
        else
        {
            // update head node
        }

        if (current->next) // if this is not the tail node
        {
            current->next->prev = current->prev;
        }
        else
        {
            // update tail  node
        }

        // at this point, current is completely disconnected from the list
        delete current;
    }
}

Collectives™ on Stack Overflow

Removing a node from a doubly linked list

4 Answers 4

4 Comments

3 Comments

4 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

4 Comments

3 Comments

4 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related