CODEWITHSUNDEEP
javalinked-list
Joker
Joker

Reputation: 11146

LinkedList's indexOf() vs lastIndexOf() methods optimization

Really want to know why linked list indexof() does not take advantage of the fact that "header" entry has a null element for increased performance when it is passed a null "target" :

public int indexOf(Object o) {
    int index = 0;
    if (o==null) {
        // header.element guaranteed null, no chance of looping past header
        for (Entry e = header.next; e.element != null; e = e.next) {
            index++;
        }
        // if index < size, null was found, else we looped to header
        return (index < size) ? index: -1;
    } else {
        for (Entry e = header.next; e != header; e = e.next) {
            if (o.equals(e.element))
                return index;
            index++;
        }
    }
    return -1;
}

If we apply a similar transformation to lastIndexOf() it yields very pretty results:

public int lastIndexOf(Object o) {
    int index = size - 1;
    if (o==null) {
        for (Entry e = header.previous; e.element != null;
             e = e.previous, index--);
    } else {
        for (Entry e = header.previous; e != header && !o.equals(e.element);
             e = e.previous, index--);
    }
    return index;
}

Is it intentional ?

Upvotes: 1

Views: 218

Answers (1)

Jiri Tousek
Jiri Tousek

Reputation: 12440

I'm not sure what JRE are you referring to, but apart of syntactic sugar the only relevant difference I see is this:

// if index < size, null was found, else we looped to header
return (index < size) ? index: -1;

The reason for this is, for lastIndexOf() we start at last element and upon miss, we end up at header with index -1. But for indexOf(), we start at 0-th element and upon miss we end up at header with index == size - however, we want to return -1 upon miss, so we have to add the extra condition.

Upvotes: 1

Related Questions