java - 链表中的节点(int索引)

Question

有人可以解释一下LinkedList中方法node(int index)的逻辑吗？什么使位偏移量为 1:

(index < (size >> 1))

方法:

Node<E> node(int 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;
    }
}

感谢您的解答!

Answer 1

size >> 1相当于 size / 2

我猜这个函数找到了 node在索引x .

基本上，它的作用是比较 index与节点总数。

如果index < size/2然后它从0开始搜索至size/2

如果index > size/2然后它从size开始搜索至size/2

例如，如果您不比较 index与 size/2 ，您可能会循环整个列表，即 O(n) 。通过这样做，您可以将迭代次数减少一半。 (O(n/2))