CODEWITHSUNDEEP
c++c++11
opticks
opticks

Reputation: 59

Removing a node from a doubly linked list

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

Upvotes: 1

Views: 250

Answers (4)

Zac Howland
Zac Howland

Reputation: 15870

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

Upvotes: 0

AFM
AFM

Reputation: 44

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;

Upvotes: 1

RichardPlunkett
RichardPlunkett

Reputation: 2988

Should look like:

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

Upvotes: 0

ninMonkey
ninMonkey

Reputation: 7511

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.

Upvotes: 2

Related Questions