java - 从 LinkedList 最快获取条目/节点

Question

来自LinkedList.java我找到了这个获取条目的方法。

/**
 * Returns the indexed entry.
 */
private Entry<E> entry(int index) {
    if (index < 0 || index >= size)
        throw new IndexOutOfBoundsException("Index: "+index+
                                            ", Size: "+size);
    Entry<E> e = header;
    if (index < (size >> 1)) {
        for (int i = 0; i <= index; i++)
            e = e.next;
    } else {
        for (int i = size; i > index; i--)
            e = e.previous;
    }
    return e;
}

让我烦恼的是:

    if (index < (size >> 1))

为什么这里要进行位移操作呢？这样的事情不是最优的吗？

if (index < (size / 2)) {
    for (int i = 0; i <= index; i++)
        e = e.next;
} else {
    for (int i = size; i > index; i--)
        e = e.previous;
}

自从

if (index < (size / 2))

保证我们请求的索引位于列表的前半部分。

Answer 1

在代码示例中没有理由右移一位:除以二将具有相同的性能，并且可能比移位具有更好的可读性。这种微优化在过去的 C 语言中非常常见，但现在每个称职的优化器都会为您做这种替代。