Java 的内部 LinkedList 实现是否根据传递给 get() 的索引适当地从头部或尾部开始遍历？

Question

因为Java LinkedList 的实现是一个双向链表。如果说传递给 get get(int index) 方法的索引超过了链表的中间，那么该值是使用尾部的降序迭代器获得的，这不是更有意义吗在列表中？

会发生这种情况吗？

如果没有，为什么？

例如我有一个如下所示的链表：

head                                 tail
  A <-> B <-> C <-> D <-> E <-> F <-> G

然后我说 linkedList.get(5) 来获取 linkedList 中的第二个最后一个元素。 java 是否会在内部使用降序迭代器（从尾部开始）来检索 F？因为 5 超过了链表的中间。

Answer 1

启动调试器并验证行为会更有趣，也许更容易。或者，参考链接列表的文档，特别是

All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the beginning or the end, whichever is closer to the specified index.

Answer 2

看源代码很快就回答了这个问题（答案是肯定的）：

/**
 * Returns the element at the specified position in this list.
 *
 * @param index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

/**
 * Returns the (non-null) Node at the specified element index.
 */
Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

Java 的内部 LinkedList 实现是否根据传递给 get() 的索引适当地从头部或尾部开始遍历？

Does Java's internal LinkedList implementation traverse starting from the head or tail appropriately depending on the index passed to get()?

java

linked-list

doubly-linked-list