Removing nodes from linked lists

[Con]

I'm working on a Java assignment and we have to create a linked list of nodes, each containing one field as a double. For the remove(double d) method, we have to remove every node containing the element equal to d from the linked list. I was able to accomplish this, and my testing program verifies the results and that head and tail references are good, but I'm sure someone here can show me a better way of doing it.

http://img651.imageshack.us/img651/9441/capturehg.png

e: I just realized, on line 51 it should say count instead of size(), but it doesn't make a difference anyway since size() just returns the field count. size() exists because it's required by the interface provided to us.

[Donut]

reading code makes me :downs:
so what you have there does work, but you want a more efficient way to do what you did there?

[Dwood]

If you're making java... use Eclipse, Java IDE. Makes devving in Java much easier.

[Con]

If you're making java... use Eclipse, Java IDE. Makes devving in Java much easier.
I used Eclipse for a bit, but I prefer the simplicity of TextPad. It forces me to be more careful and to look things up on the Java API site rather than relying on the IDE to do it for me, which I suppose is better for someone learning the language still.


reading code makes me :downs:
so what you have there does work, but you want a more efficient way to do what you did there?
yuppers

I have a few if statements that I feel are like band-aids and that I could somehow generalize the code to handle more of these cases.

[Rob Oplawar]

Your code is not completely correct. If the head is equal to d, it will be removed, but if the next one after that is also equal to d it remains in the list.

I recommend you make a remove function that handles the boundary cases of removing the head, tail, or anything inbetween, then iterate over the whole list and call remove on anything that equals d.

[Con]

bump

I went with a different approach that seems to cover all cases now. It's similar to what Rob suggested, but all within one function. I step through the list until I find something that required some attention, then with some code underneath the nested while it makes some changes based on the case. I found it was easier to keep a previous pointer as well--they told us we could use a doubly linked list if we want, but not to rely on it.

http://img686.imageshack.us/img686/9828/capturelb.png

Can anyone spot anything wrong?

I know some things in if (current.getElement() == d) is kinda confusing, but it's to cover those boundary cases that Rob mentioned.

[Rob Oplawar]

:ugh: Nested whiles do not belong in this algorithm. Here's how I would do it:


public void remove throws Exception ( double d ) {
DoubleNode current = this.head, previous = null;
while ( current != null ) {
//if any element in the list is d
if ( current.getElement() == d ) {
//if it's head, bump the head up to the next one
if ( current == this.head ) {
head = current.getNext();
}
//otherwise, we better have a reference to prev or else something weird is going on. this should be impossible, but just to be on the safe side...
elseif ( prev == null ) {
throw new Exception("Invalid data- if 'current' is not head, we should have a 'prev' here...");
}
//if it's the tail, set the tail back
elseif ( current == this.tail ) {
this.tail = prev;
prev.setNext(null);
}
//otherwise, have prev skip the current node
else {
prev.setNext(current.getNext());
}
//regardless, we've removed something
this.count--;
}
//advancing works the same way no matter where we are
prev = current;
current = current.getNext();
}
}