Bdtjtk

Since Java implementation of the LinkedList is a doubly linked list. Would it not make more sense if say an index passed to the get get(int index) method was past the middle of the linkedlist, That the value was obtained using the descending iterator from the tail of the list?

Does this happen?

If it does not why?

Example say I have a linkedList like below:

head                                 tail

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

And I said linkedList.get(5) to get the second the last element in the linkedList. Would java use the decending iterator (start from the tail) internally to retrive F, or not? Since 5 is past the middle of the linkedlist.

It would be more fun and perhaps easier to fire up the debugger and verify the behavior. Alternatively, refer to the documentation of Linked List, in particular

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.

Looking at the source code answers the question pretty quickly (the answer is yes):

/**

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

    }

}