Double Linked List remove method

Question

I am implementing some basic data structures to freshen up my memory and I wanted my DoubleLinkedList remove method to be reviewed. I feel like it has extra checks but I could not think of another way to implement.

My implementation holds both the head and the tail of the list making things a bit more complex.

remove method:

public void remove(T data) {
 if (isEmpty()) {
 throw new NoSuchElementException();
 }
 for (Node<T> current = this.head; current != null; current = current.getNext()) {
 if (current.getData().equals(data)) {
 Node<T> previous = current.getPrevious();
 Node<T> next = current.getNext();
 if (this.size == 1) { // At head with size == 1
 this.head = this.tail = null;
 } else if (previous == null) { // At head with size > 1
 this.head = next;
 next.setPrevious(previous);
 } else if (next == null) { // At tail
 previous.setNext(next);
 this.tail = previous;
 } else { // Rest of cases
 previous.setNext(next);
 next.setPrevious(previous);
 }
 this.size--;
 return;
 }
 }
 throw new NoSuchElementException();
}

• maaartinus: +1 Just some notes: 1. Note that Java collections don't throw in remove. 2. Instead, they return the removed element, if any. 3. I'm unsure, if NoSuchElementException is appropriate, if you really want to throw. 4. Using a cycle with a dummy element would reduce all four cases to one, but I'm not claiming you should waste the memory for it.
• Aki K: I did not make it so it returns the element (or null) because I wanted to keep it as simple as I could. Also in the official implementation it does throw a NoSuchElementException that is why I did it like that.
• maaartinus: OK, your choice. There's nothing wrong with it.

Answer 1

I feel like it has extra checks

You could remove the isEmpty check (which probably just checks this.head == null), as in that case, the for loop will not be entered and the exception at the end will be thrown.

And I think that your if cases are fine as they are. If you want to, you could pull one or more of them out of the loop:

public void remove(T data) {
 if (isEmpty()) {
 throw new NoSuchElementException();
 }
 if (this.size == 1 && this.head.getData().equals(data)) {
 this.head = this.tail = null; // removing only item from list
 this.size--;
 return;
 }
 if (this.head.getData().equals(data)) { // removing head
 this.head = this.head.getNext();
 this.head.setPrevious(null);
 this.size--;
 return;
 }
 if (this.tail.getData().equals(data)) { // removing tail
 this.tail = this.tail.getPrevious();
 this.tail.setNext(null);
 this.size--;
 return;
 }
 for (Node<T> current = this.head; current != null; current = current.getNext()) {
 if (current.getData().equals(data)) {
 Node<T> previous = current.getPrevious();
 Node<T> next = current.getNext();
 previous.setNext(next);
 next.setPrevious(previous);
 this.size--;
 return;
 }
 }
 throw new NoSuchElementException();
}

If you do this, you would need the isEmpty check.

This approach would also speed up your code (less checks in loop) and I think it might also be more readable.

You could probably remove the size == 1 case with some restructuring, but I think the resulting code would be worse than what you have.

Misc

• if (next == null) { previous.setNext(next); }: this works, but I would make it explicit that you are setting next to null: if (next == null) { previous.setNext(null); }, same with the previous == null check.

• Brythan: Don't you need to decrement the size still when you are outside the loop? I.e. everywhere there's a return, there should be a this.size--;
• tim: @Brythan oh thanks. Yes, size should be decremented everywhere, I overlooked that.
• Aki K: I didn't put them outside the loop because I thought the code was less readable since I would have multiple return; and multiple size--. Also the "removing tail" if, would not work because if I had a list with: {2, 3, 15, 89, 3} and I did remove(3) then the first 3 should have been removed not the last therefore I would have to move that if inside the for loop making my code seem a little bit fragmented.
• tim: @SilliconTouch I think that it is a lot more readable, and also makes more sense (in the loop, your checking it each time, even though you know that it can only happen on the first/last loop). Good point with the duplicate entries though. To solve that, you could move the tail check to the end of the method, and let the loop run up to current.getNext() == null.
• Aki K: I think I will implement the separate logic like you said on the other answer's comment and that way I can just "dump" the removal and checks there and have a separate search function.

Answer 2

I have couple suggestions:

Separate Logic

I would separate lookup and modify logic. Add a function to remove element and call it from this one leaving in this one only logic to lookup an item.

public void remove(Node<T> data) {
 if (!data) {
 throw new NoSuchElementException();
 }
 // Removing logic here
 ...
}
public void remove(T data) {
 return remove(search(data));
}
public Node<T> search(T data) {
 for (Node<T> current = this.head; current != null; current = current.getNext()) {
 if (current.getData().equals(data)) {
 return current;
 }
 }
 return null; 
}

Simplify Checks

I think this should work and cover all your cases, no?

// If this is head of the list
if (previous == null) { 
 this.head = next;
}
else {
 previous.setNext(next);
}
// If this is tail of the list
if (next == null) { 
 this.tail = previous;
}
else {
 next.setPrevious(previous);
}

• tim: Your simplified checks should work, but I think they are a bit harder to understand (and technically, it's still four cases). I also wouldn't split the method, but if you do, I would do it like this: Change your void remove(T) method to Node<T> search(T), then add a new remove(T) method which uses search and remove. That way, you can reuse search for other operations (like contains). Oh, and make all methods containing Node in the signature private, as it shouldn't be exposed.
• Aki K: I agree with @tim that your ifs even though they look better they do not convey as well what they are for I think. The separation of the logic though is something that I might do.
• tim: oh, but still +1 for this solution. It's pretty much how oracle implemented this.
• sha: I agree that we better separate search into its own function. As for readability - I think adding comments would solve it. I will update the answer.

Answer 3

A lot of those here try to avoid nesting. In your case, this would mean switching the equality check to an inequality check.

If you move your head and tail checking outside of the for loop, you could make the loop much simpler:

for (Node<T> current = this.head.getNext(); current != this.tail; current = current.getNext()) {
 if ( ! current.getData().equals(data) ) {
 continue;
 }

Note that the prior checks (as shown in Tim's answer) ensure that the list is at least of size 2 and that you aren't removing either the head or the tail. The start and end conditions ensure that you only remove things between the head and the tail.