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

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.

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

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.