How to find the minimum element of a doubly linked list in Java

Question

This is my code for the getMin() method. I cannot get the method to enter the while loop.

public E getMin() {

    Node<E> curr = header;
    Node<E> min = curr;
    E temporaryMinimum = header.getElement();
    if (isEmpty()) {
        return curr.getElement();
    }

    while (curr != null) {
        if (curr.getElement() != null) {
            if (temporaryMinimum.compareTo(curr.getElement()) > 0) {
                min = curr;
                temporaryMinimum = curr.getElement();
            }
            curr = curr.getNext();
        }
    }
    return curr.getElement();
}

Answer 1

Looks like there is a bug/typo in your while loop. Try this instead (I also improved some minor aspects as well):

if (isEmpty()) { return null; }

Node<E> curr = header;
Node<E> min  = curr;
E minElement = curr.getElement();

while (curr != null) {
    if (curr.getElement() != null) {
        if (minElement.compareTo(curr.getElement()) > 0) {
            min = curr;
            minElement = curr.getElement();
        }
    }
    curr = curr.getNext();
}
return minElement;

In the general case, you can’t do better than a linear search even for doubly-linked lists ;)