Java 的 LinkedList 是否经过优化以在必要时反向执行 get(index)? [英] Is Java's LinkedList optimized to do get(index) in reverse when necessary?

问题描述

我一直在研究优化 LinkedList 的一些方法.有谁知道 Java 默认的双向链接 LinkedList 类是否经过优化以反向执行 get() 操作?例如:

I've been working on some ways to optimize LinkedList's. Does anyone know if the Java default doubly-linked LinkedList class is optimized to do get() operations in reverse? For example:

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

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

Would the call to list.get(half + 1) optimize the search and go in reverse since it is a doubly-linked list? It would make more sense to do the search from the end and go towards the center if you know the element is in the second half of the list.

我知道使用 get(index) 是 O(n) 时间，并且在遍历 LinkedList 时应该使用迭代器，但我只是很好奇.>

I know using get(index) is O(n) time and that you should use an iterator when traversing a LinkedList, but I am just curious.

推荐答案

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

Yes it is. You can inspect the source code yourself: 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 的定义是:

where entry is a private method. entry's definition is:

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;
}

如您所见，如果索引大于列表的中点，则从末尾开始倒计时.

As you can see, it counts down from the end if index is greater than the midpoint of the list.

这篇关于Java 的 LinkedList 是否经过优化以在必要时反向执行 get(index)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！