Java的LinkedList是否经过优化以在必要时反向执行get（index）？

Question

我一直在研究优化LinkedList的方法。有人知道Java默认的双向链接LinkedList类是否经过优化以进行get()反向操作吗？例如：

// Some LinkedList list that exists with n elements;
int half = list.size() / 2;
list.get(half + 1);

将调用list.get(half + 1)优化搜索和走在相反，因为它是一个双向链表？如果您知道该元素位于列表的后半部分，则从末尾开始搜索并向中心搜索会更有意义。

我知道用的get(index)是O(n)时间，遍历LinkedList时应该使用迭代器，但是我很好奇。

Answer 1

是的。您可以自己检查源代码：http
:
//grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/LinkedList.java#LinkedList.entry%28int%
29

LinkedList#get(int) 被实现为

return entry(index).element;

entry私有方法在哪里。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;
}

如您所见，如果index大于列表的中点，则从末尾开始递减计数。