removes last instance of val from list C++

[Josh]

I am trying to remove the last (farthest from head) instance of val found. Also,am trying to implement printReverse which I think I got done right. This is a doubled linked listed and this is what I have so far:

Done


Hopefully someone can help me out. Thanks

[Jordan]

Just start at the back and remove the first one you encounter. This should work, but it's not tested.

bool LList::remove(int val) {
    if(head == NULL)
        return false;

    Node *cur = tail;

    while(cur) {
        if(cur.val == val) {

            if(cur->prev)
                cur->prev->next = cur->next;
            if(cur->next)
                cur->next->prev = cur->prev;

            if(cur == head)
                head = cur->next;
            else if(cur == tail)
                tail = cur=>prev;

            delete cur;
            return true;
        }
        cur = cur->prev;
    }
    return false;
}

Your print reverse looks good.

[Josh]

That code will remove a item in the middle of list from the back, but it errors out when it tries to move the first one in the list or the last one in the list from the back...

[Jordan]

Are you running several tests in a row or are you running each test separately?

For example, are you doing:

list.remove(1);
list.remove(2);
list.remove(3);

If so, the error you are getting could be caused by something else. The reason I say this is because it should work when removing the first and last, but I could still be wrong. I do see a problem when removing the last item however, and that's due to not setting head to NULL.

Also, my code will only work if you are setting all your node pointers to NULL (such as next and prev) whenever they are initialized.

[Josh]

Sept 23, 2010 15:23:58 GMT -8 Jordan said:

Are you running several tests in a row or are you running each test separately?

For example, are you doing:

list.remove(1);
list.remove(2);
list.remove(3);

If so, the error you are getting could be caused by something else. The reason I say this is because it should work when removing the first and last, but I could still be wrong. I do see a problem when removing the last item however, and that's due to not setting head to NULL.

I am running 1 test at a time like this:

void main (){
LList LL;
LL.insert(10);
LL.insert(20);
LL.insert(30);
LL.insert(40);
LL.insert(20);
LL.insert(50);
LL.printReverse();
LL.remove(10);
LL.printReverse();

}

When I tried to remove the 10, which is the very first I get this popup error:

Debug Assertion Failed!

...

Expression: _BLOCK_TYPE_IS_VALID(pHead->nBlockUse)
...


and when I tried to remove the 50, which is the very last I get a really long negative number and this it crashes...

[Jordan]

What's the output for that test case?

[Josh]

Sept 23, 2010 15:29:13 GMT -8 Jordan said:

What's the output for that test case?

Well, if I remove a item from the middle which works correctly it will look like this(This is with the 20 removed)

50 20 40 30 20 10
50 40 30 20 10
Press any key to continue . . .

[Jordan]

You'll have to post your class definition because there's probably something I'm doing that's not compatible with your code.

[Josh]

Ok here it is:

done

[Jordan]

Run it in debug mode and see which line it crashes on. I don't see anything from just reading the code.

[Josh]

Sept 23, 2010 15:46:55 GMT -8 Jordan said:

Run it in debug mode and see which line it crashes on. I don't see anything from just reading the code.

I think it may be line 18 the return true statement. It crashes their when it gets to the head and tries to remove it.

[Jordan]

Yeah, I think you need to add an if statement.

if(cur == head)
        head = cur->next;
else if(cur == tail)
        tail = cur=>prev;

delete cur;
return true;

[Josh]

Yup, that was it!!! Man you are good, I sure wish I was!!! Now let me run through that code and see if I can understand everything that is happening. Thanks So much!!

[Jordan]

Glad to help. If there is something I did that you don't understand just let me know, but it's basically just updating addresses. The reason the program was crashing was I forgot to update the head and tail pointers when the nodes they pointed were deleted so when the program tried to access the data referenced by those pointers it would crash.

[Josh]

Sept 23, 2010 16:12:43 GMT -8 Jordan said:

Glad to help. If there is something I did that you don't understand just let me know, but it's basically just updating addresses. The reason the program was crashing was I forgot to update the head and tail pointers when the nodes they pointed were deleted so when the program tried to access the data referenced by those pointers it would crash.

Yeah, I think I understand it now...This is the first time I have every dealt with double linked list. Thanks again!