LinkedList查询问题

Question

若在LinkedList 存放100万条数据，那么要拿到第50万条，需要查询几次？

Answer 1

看一下Linkedlist的源代码不就一清二楚了？
它会检查你要取第N条记录是在上半区还是下半区， size >> 1 就是相当于除以2，然后遍历N次或者size - N次。

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