Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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();
}
share|improve this question
    
+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. –  maaartinus 11 hours ago
    
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. –  Sillicon Touch 11 hours ago
    
OK, your choice. There's nothing wrong with it. –  maaartinus 11 hours ago

3 Answers 3

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);
}
share|improve this answer
1  
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. –  tim 13 hours ago
    
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. –  Sillicon Touch 12 hours ago
    
oh, but still +1 for this solution. It's pretty much how oracle implemented this. –  tim 12 hours ago
    
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. –  sha 12 hours ago

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.

share|improve this answer

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.
share|improve this answer
1  
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--; –  Brythan 13 hours ago
    
@Brythan oh thanks. Yes, size should be decremented everywhere, I overlooked that. –  tim 13 hours ago
    
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. –  Sillicon Touch 12 hours ago
    
@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. –  tim 12 hours ago
    
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. –  Sillicon Touch 12 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.