Java的LinkedList是否经过优化以在必要时反向获取(索引)？

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大于列表的中点,它将从末尾开始倒计时.