java - 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 是私有(private)方法。 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;
}

如您所见，如果索引大于列表的中点，它会从末尾倒数。