java - LinkedList的indexOf()与lastIndexOf()方法优化

Question

真的想知道为什么链表indexof()不利用“header”条目具有空元素的事实来提高性能，当它传递一个空“目标”时:

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

如果我们对lastIndexOf()应用类似的转换，它会产生非常漂亮的结果:

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

是故意的吗？

Answer 1

我不确定您指的是什么 JRE，但除了语法糖之外，我看到的唯一相关区别是:

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

这样做的原因是，对于lastIndexOf()，我们从最后一个元素开始，一旦错过，我们最终会到达索引为-1的 header 。但是对于 indexOf() ，我们从第 0 个元素开始，一旦错过，我们最终会到达 index == size 的 header - 然而，我们想要返回 -1 错过了，所以我们必须添加额外的条件。