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是私有方法。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 大于列表的中点，它会从末尾开始倒计时。